[Combprob] seminar Feb 5 and Feb 12

[Vu, Van]

Dear Mel,

Please post the following:

Comb/Prob Seminar: Feb 5, 4-5pm, LOM 215. Speaker: A. Lubotzky (Yale)

title:   Quantum error correcting codes and 4-dimensional hyperbolic manifoldds an

  Abstract:

 It is well known that there exist LDPC good error correcting codes (this was proved by Gallager using random methods while explicit constructions were given by  Sipser and Spielman ).
 The analogous problem for quantum error correcting codes, in spite being an elementary Z/2Z- linear algebra problem, is still open.

 Simplical complexes and their homology/cohomology give rise to LDPC  quantum error correcting codes ( QECC). But all known examples fail to be "good".

  In a joint work with Larry Guth   ( J. Math. Phys. 55, 082202 (2014)<https://urldefense.proofpoint.com/v2/url?u=http-3A__aip-2Dinfo.org_1XPS-2D33V7F-2DC9RS5X-2D1FC1OV-2D1_c.aspx&d=AwMFaQ&c=-dg2m7zWuuDZ0MUcV7Sdqw&r=sJ2GIybLuYHtneA1hCAmEw&m=w32UC_9MjSnqQjStzd12EyeKEZgHaCwxnneTCPYd5EA&s=dN1SqD5y_LxjsxjsatzKmfNrHeB9dj2tAdt_SjL3LLU&e=> ),     we constructed a family of  LDPC QECC out of congruence quotients of the 4- dimensional hyperbolic space.  Using methods of systolic geometry over Z/2Z, we evaluate the parameters of these codes and disprove a conjecture of Ze'mor who predicted  that such homological QECC do not exist. The existence of LDPC good QECC is still open.

  All notions will be defined and explained.

------------------------

Feb 12, 4-5pm, LOM 215 Speaker M. Krivelevich (Tel Aviv)

Title:   The Phase Transition in Site Percolation on Pseudo-Random Graphs

                          ABSTRACT

We establish the existence of the phase transition in site percolation
on pseudo-random d-regular graphs. Let G=(V,E) be an (n,d,lambda)-graph,
that is, a d-regular graph on n vertices in which all eigenvalues of
the adjacency matrix, but the first one, are at most lambda in their
absolute values. Form a random subset R of V by putting every vertex
v in V into R independently with probability p. Then for any small
enough constant epsilon>0, if p=(1-epsilon)/d, then with high
probability all connected components of the subgraph of G induced by R
are of size at most logarithmic in n, while for p=(1+epsilon)/d, if
the eigenvalue ratio lambda/d is small enough as a function of epsilon,
then typically R contains a connected component of size at least
epsilon n/d and a path of length proportional to epsilon^2n/d.



[X]
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.yale.edu/pipermail/combprob/attachments/20150128/affe8b48/attachment.html