The Taub Faculty of Computer Science Events and Talks
Uriya First (Haifa university)
Wednesday, 24.05.2023, 12:30
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.