Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: A Sheaf-theoretic Approach to Constructing Locally Testable Codes
event speaker icon
Uriya First (Haifa university)
event date icon
Wednesday, 24.05.2023, 12:30
event location icon
Taub 201
I will discuss a new approach towards constructing good locally testable codes (LTCs) with better qualities than the recent constructions of good LTCs. This approach continues the trend of using high dimensional expanders (HDXs) for constructing LTCs, but introduces a new ingredient: a sheaf on the HDX at hand. We show that if one could find a single example of a sheaved HDX satisfying some local expansion conditions and a cohomological condition --- both of which can be checked in finite (constant) time ---, then this example could be propagated into an infinite family of good LTCs. We also propose a heuristic method for constructing the initial sheaved HDX. The LTCs arising from our framework are 2-query LTCs which also admit a stronger testability property called (T)-testability. This is a joint work with Tali Kaufman.