Time: Sunday,
16:00-17:30
Place:
Math building, 3rd floor seminar room (216/201)
Abstracts
The Algebraic Eraser and short expressions of permutations as products
Boaz Tsaban, Bar-Ilan University
Abstract: On March 2004, Anshel, Anshel, Goldfeld, and Lemieux introduced the Algebraic Eraser scheme for key agreement over an insecure channel, using a novel hybrid of infinite and finite noncommutative groups. They also introduced the Colored Burau Key Agreement Protocol (CBKAP), a concrete realization of this scheme.
We present general, efficient heuristic algorithms, which extract the shared key out of the public information provided by CBKAP. These algorithms are, according to heuristic reasoning and according to massive experiments, successful for all sizes of the security parameters, assuming that the keys are chosen with standard distributions.
Our methods come from probabilistic group theory and expander graphs. In particular, we provide a simple and efficient heuristic algorithm for finding short expressions of permutations in S_n, as products of given random permutations. Our algorithm gives (heuristically and experimentally) expressions of length roughly n^2\log n, in time roughly n^3\log n and space roughly n^2\log n, and is the first practical one for n>128.
The talk is designed to be accessible also to undergraduate students. So, students are welcome.
Disclaimer: Our work does not make any claim concerning the security of the actual distributions used in the Algebraic Eraser (TM). These distributions are are proprietary and are not available to the authors.
Joint work with Arkadius Kalka and Mina Teicher (BIU).
On the rank of design matrices with applications
Amir Yehudaioff, Technion
Abstract: A design matrix is a matrix whose pattern of zeros/nonzeros satisfies a certain design-like condition. We will first prove that the rank of any design matrix is high.
We shall discuss two applications of this rank lower bound:
(1) Impossibility results for 2-query locally correctable codes over
real/complex numbers, and
(2) generalization of results in
combinatorial geometry, for example, a robust analog of the
Sylvester-Gallai theorem.
Joint work with Boaz Barak, Zeev Dvir and Avi Wigderson.
Percolation in interdependent and interconnected networks
Reuven Cohen, Bar-Ilan University
Abstract: I will discuss percolation in systems consisting of two Erdos-Renyi random graphs, such that the vertices of each depend, with some probability on the vertices of the other (i.e., there is partial or full identification of the vertex set). We will consider at the mutual giant component, consisting of vertices that belong to the giant component in both graphs. As the mutual dependence may lead to cascading failures of vertices, this model leads to rich phenomena, including first and second order transitions, as well as hybrid transitions.
Joint work with Yanqing Hu, Baruch Kesherim, and Shlomo Havlin
Approximate periodicity
Amihood Amir, CS, Bar-Ilan University and Johns Hopkins University
Abstract: Assume that a natural cyclic phenomenon has been measured, but the data is corrupted by errors. The type of corruption is application-dependent and may be caused by measurement errors, or natural features of the phenomenon. We assume that an appropriate metric exists, which measures the amount of corruption experienced. We study the problem of recovering the corrupted cycle under various error models, formally called the period recovery problem. Specifically, we identify a metric property which we call pseudo-locality and study the period recovery problem under pseudo-local metrics. Examples of pseudo-local metrics are the Hamming distance, the swap distance, and the interchange (or Cayley) distance.
We show that for pseudo-local metrics, periodicity is a powerful property allowing detecting the original cycle and correcting the data, under suitable conditions. Some surprising features of our algorithm are that we can efficiently identify the corrupted period, up to number of possibilities logarithmic in the length of the data string, even for metrics whose calculation is NP-hard.
We also study finding an approximate period of a string where a minimum number of errors is not guaranteed.
Joint work with Estrella Eisenberg, Avivit Levy, Noa Lewenstein, Ely Porat, and Natalie Shapira.
On the number of geodesics in a graph of perfect matchings
Roy Ben-Ari, Bar-Ilan University
Abstract: Consider the graph $G(n)$ whose vertices are all perfect matchings on $2n$ points; two perfect matchings are connected by an edge if their symmetric difference is a cycle of length four.
We compute the diameter of this graph, extending previous results of Hernando, Hurtado and Noy. We will then prove the following surprising result: The number of shortest paths between every two antipodes is equal to the number of labeled trees of order $n$. Finally, an explicit formula for the number of shortest paths between any two vertices in $G(n)$ will be given.
This is a part of an M.Sc. thesis carried under the supervision of Ron Adin and Yuval Roichman.
A solution of an equivalence problem for cyclic codes
Michael Muzychuk, Netanya College
Abstract: A linear (n,k)_q code is a k-dimensional subspace of an n-dimensional vector space F_q^n. Two linear codes C,D\leq F_q^n are called permutation equivalent if one of them can be obtained from another by permuting the coordinates. A cyclic code is an (n,k)_q code which is invariant under cyclic shift of its coordinates. A cyclic code is called semisimple if gcd(q,n)=1. In my talk I'll present a polynomial (in k,n,q) algorithm for equivalence testing of semisimple cyclic codes.
The upper bound on the length of synchronizing word and a graph visualization program
Avraham Trahtman, Bar-Ilan University
Abstract: The synchronizing word of a deterministic automaton is a word in the alphabet of colors on its edges that maps states of the automaton to a single state. A coloring of edges of a directed graph is synchronizing if the coloring turns the graph into a deterministic finite automaton possessing a synchronizing word. The study was encouraged by the well known Cerny conjecture. In 1964 Jan Cerny found a sequence of n-state complete DFA possessing a minimal synchronizing word of length (n-1)^2. He conjectured that it is an upper bound on the length of such words for complete DFA. Nevertheless, the best upper bound (n^3-n)/6 was found almost 30 years ago. We reduce the upper bound on the length of the minimal synchronizing word, although not very significantly.
The solution of the road coloring problem has stimulated a lot of generalizations, connected mostly with the Cerny conjecture. Results in this area also are a topic of the talk. The information will be illustrated by a linear graph visualization program.
Diameter of graphs of reduced words
Yuval Roichman, Bar-Ilan University
Abstract: There is a natural graph structure on the set of all reduced words for the longest element in a finite Coxeter group W, where edges are determined by braid relations. A classical theorem of Tits says that this graph is connected. Autord and Dehornoy showed that when W = S_n, the symmetric group on n letters, the diameter of this graph grows asymptotically as O(n^4).
The main result is that the diameter for W = S_n is exactly 1/24 n(n-1)(n-2)(3n-5). This result is then extended to W = B_n, the hyperoctahedral group. The proof idea is to rephrase the problem as a general question about hyperplane arrangements.
This is joint work with Victor Reiner.
On the diameter of the Tits graph of the longest element in Coxeter groups of classical type
Arkadius Kalka, Bar-Ilan University
Abstract:
Consider the Tits graph of the longest element of a finite
type Coxeter group. Its vertices are reduced words representing the
longest element, and edges correspond to one application of a
relation. By counting appropriate inversions Reiner and Roichman ([RR09], see:
http://arxiv.org/PS_cache/
computed lower bounds for the diameter of this Tits graph for all
finite type Coxeter groups. Using methods from the theory of
hyperplane arrangements they proved for the families of A and B-type
that these lower bounds are exact.
We give elementary proofs for the A and B-type by showing that the Tits posets (poset structure given by inclusion of these inversions) have unique maximal and minimal elements. For the D-type Coxeter group, we show for several ''natural'' candidate bottom words that there exist other local minimal elements in the Tits poset.
New representations of matroids and generalizations
Zur Izhakian, Bar-Ilan University
Abstract: Traditionally, matroids have been represented by using matrices defined over fields. We extend this notion by considering new representations of matroids by matrices over finite semirings, more precisely supertropical semirings. This idea of representations is applicable also for semigroups and is naturally generalized to include hereditary collections (also known as abstract simplicial complexes). We show that any matroid, and more generally any hereditary collection, is superboolean-representable.
Joint work with J. Rhodes.
A probabilistic Kesten theorem and counting closed circles in graphs
Yair Glasner, Ben-Gurion University
Abstract: This is joint work with Miklos Abert and Balint Virag.
I will present new asymptotic estimates on the number of closed circles in large d-regular graphs. These improve previous estimates that were obtained by Serre and McKay.
Our main statement was well known for Cayley graphs, where it follows from Kesten's famous spectral radius theorem (this was Kesten's dissertation). While Kesten's theorem is false for general graphs, we are able to prove a probabilistic version of the theorem which is enough to deduce the aforementioned estimates.
Time permitting, I will show also how to generalize the measurable Kesten theorem to finitely generated groups.
Littlewood-Richardson coefficients for reflection groups
Arkady Berenstein, University of Oregon
Abstract: The goal of my talk (based on a recent joint paper with Edward Richmond) is to compute the Littlewood-Richardson (LR) coefficients for semisimple or Kac-Moody groups G, that is, the structure constants of the cohomology algebra H(G/P), where P is a parabolic subgroup of G. These coefficients are of importance in enumerative geometry, algebraic combinatorics and representation theory.
Our formula for the LR coefficients is purely combinatorial and is given in terms of the Cartan matrix and the Weyl group of G. In particular, our formula gives a combinatorial proof of positivity of the LR coefficients in the cases when all off-diagonal Cartan matrix entries are less than or equal to -2.
Intriguing graph polynomials
Johann Makowsky, Technion
Abstract: Graph polynomials are uniformly defined families of graph invariants which are polynomials in some polynomial ring. The most prominent examples are the chromatic polynomials, the characteristic polynomials, various matching polynomials, the Tutte polynomials and its many variations, the interlace polynomials. These, and a few more, are well studied in the literature. However, they are studied for their own merit, and without a general framework. In this talk we sketch how a general theory of graph polynomials can be developed.
As time permits, we adress some of the following issues:
- Graph polynomials as generating functions;
- Graph polynomials as counting certain types of colorings;
- Graph polynomials defined by recurrence relations;
- Representability of graph polynomials;
- How to compare graph polynomials;
- The distinguishing power of graph polynomials;
- Universality properties of graph polynomials;
- Complexity of graph polynomials
This is based on joint work with Ilya Averbouch, Markus Bl\"aser, Holger Dell, Benjamin Godlin, Tomer Kotek, Klaus Meer, Elena Ravve, and Boris Zilber.