BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Good locally testable codes - Alex Lubotzky (Hebrew University of 
 Jerusalem)
DTSTART:20220725T090000Z
DTEND:20220725T095000Z
UID:TALK175064@talks.cam.ac.uk
DESCRIPTION:An error-correcting code is locally testable (LTC) if there is
  a random tester that reads only a small number of bits of a given word an
 d decides whether the word is in the code\, or at least close to it.\nA lo
 ng-standing problem asks if there exists such a code that also satisfies t
 he golden standards of coding theory: constant rate and constant distance.
 &nbsp\;Unlike the classical situation in coding theory\, random codes are 
 not LTC\, so this problem is a challenge of a new kind.&nbsp\;\nWe constru
 ct such codes based on what we call (Ramanujan) Left/Right Cayley square c
 omplexes.&nbsp\; These objects seem to be of independent&nbsp\;group-theor
 etic interest. The&nbsp\;codes built on them are 2-dimensional versions of
  the expander codes constructed by Sipser and Spielman (1996).&nbsp\;\nThe
  main result and lecture will be self-contained. But we hope also to expla
 in how the seminal work of Howard Garland ( 1972) on the cohomology of quo
 tients of the Bruhat-Tits buildings of p-adic Lie group has led to this co
 nstruction ( even though it is not used at the end).&nbsp\;\nBased on join
 t work with I. Dinur\, S. Evra\, R. Livne\, and S. Mozes.
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR