Seminars & Colloquia Calendar

Download as iCal file


The C^3 problem: locally testable codes with constant rate and constant distance

Alex Lubotzky (Hebrew University and IAS)

Location:  Hill Center Room 705
Date & time: Wednesday, 17 November 2021 at 3:30PM - 4:30PM

Abstract:  An error-correcting code ( LTC) is locally testable if there is a random tester that reads only a constant number of bits of a given word and decides whether the word is in the code, or at least close to it.  A long-standing problem asks if there exists such a code that also satisfies the golden standards of coding theory: constant rate and constant distance. Random codes are not LTC !

 We construct such codes based on what we call (Ramanujan) Left/Right Cayley square complexes. These 2-dimensional objects seem to be of independent interest.  Joint work with I. Dinue, S.Evra, R. Livne and S. Mozes. The talk will be self-contained. 

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.