Seminar • Algorithms and Complexity • New Codes on High Dimensional ExpandersExport this event to calendar

Wednesday, November 29, 2023 — 12:00 PM to 1:00 PM EST

Please note: This seminar will take place in M3 4206 and online.

Rachel Yun Zhang, PhD student
CSAIL, Massachusetts Institute of Technology

A code, which is a set of strings called codewords, is locally testable if one can test whether a given word is close to a codeword by reading only a few bits. Locally testable codes have been studied since the 1990s as key ingredients in the construction of probabilistically checkable proofs.

In this talk, I’ll describe a new construction of locally testable codes implemented on high dimensional expanders. It has been known for several years that high dimensional expanders give rise to locally testable codes assuming the existence of a compatible base code. Our main contribution is the construction and analysis of such a base code compatible with the coset complex of Kaufman and Oppenheim.


To attend this seminar in person, please go to M3 4206. You can also attend virtually using Zoom at https://uwaterloo.zoom.us/j/93451507468.

Location 
M3 - Mathematics 3
Hybrid: M3 4206 | Online seminar
200 University Avenue West

Waterloo, ON N2L 3G1
Canada
Event tags 

S M T W T F S
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
  1. 2024 (119)
    1. May (5)
    2. April (37)
    3. March (27)
    4. February (25)
    5. January (25)
  2. 2023 (296)
    1. December (20)
    2. November (28)
    3. October (15)
    4. September (25)
    5. August (30)
    6. July (30)
    7. June (22)
    8. May (23)
    9. April (32)
    10. March (31)
    11. February (18)
    12. January (22)
  3. 2022 (245)
  4. 2021 (210)
  5. 2020 (217)
  6. 2019 (255)
  7. 2018 (217)
  8. 2017 (36)
  9. 2016 (21)
  10. 2015 (36)
  11. 2014 (33)
  12. 2013 (23)
  13. 2012 (4)
  14. 2011 (1)
  15. 2010 (1)
  16. 2009 (1)
  17. 2008 (1)