2:30-3:30 pm
September 28, Graduate Center: Georg Zetzsche (University of Kaiserslautern),
Valence automata as a generalization of automata with storage
Abstract: A valence automaton over a monoid M is a finite automaton in which
each edge carries an input word and an element of M. A word is then
accepted if there is a run that spells the word such that the product of
the monoid elements is the identity.
By choosing appropriate monoids M, one can obtain various kinds of
automata with storage as special valence automata. Examples include
pushdown automata, blind multicounter automata, and partially blind
multicounter automata. Therefore, valence automata offer a framework to
generalize results on such automata with storage.
This talk will present recent results on valence automata. The addressed
questions include: For which monoids can we accept non-regular
languages? For which monoids can we determinize automata? For which
monoids can we avoid silent edges (i.e., those which read no input
symbol)?
October 12, Graduate Center: Alexander Guterman (Moscow State University),
On the Polya permanent/determinant conversion problem
Abstract: Two important functions in matrix theory, determinant and permanent, look very similar. While
computation of the determinant can be done in polynomial
time, it is still an open question if there is a polynomial time
algorithm to compute the permanent. For this reason, starting from
the work by Polya, 1913, different approaches to converting the
permanent into the determinant were under the intensive
investigation.
Among our results we prove the following theorem: Suppose n \ge 3,
and let F be a finite field of characteristic \ne 2. Then no
bijective map T : M_n(F) \to M_n(F) satisfies per A= det T(A).
This talk is based on several joint works with Mikhail Budrevich,
Gregor Dolinar, Bojan Kuzma and Marko Orel.
October 26, Graduate Center: Alexander Ushakov (Stevens Institute of
Technology), Cryptanalysis of matrix conjugation schemes
Abstract: We cryptanalyze two protocols: Grigoriev-Shpilrain
authentication protocol and Wang et al. public key encryption protocols
that use computational hardness of some variations of the conjugacy search problem
in noncommutative monoids. We devise an efficient heuristic algorithm, similar to length based attacks for braid-based
schemes, solving those problems.
As a conclusion, we claim that these protocols are insecure for the proposed parameter values.
November 9, Graduate Center: Vladimir Shpilrain (City College), Nature-based
cryptography
Abstract:
We employ physical properties of the real world to design a secure
cryptographic protocol where one of the parties is able to transmit
secret information to another party over an insecure channel,
without any prior secret arrangements between the parties. The
distinctive feature of this protocol, compared to all known
public-key protocols, is that neither party uses a one-way function.
In particular, our protocol is secure against (passive)
computationally unbounded adversary.
This is joint work with Dima Grigoriev.
December 7, Graduate Center: Manhattan Algebra Day
To subscribe to the seminar mailing list, click here