[Colloquium] Fernando Granha Dissertation Defense/Aug 30, 2021

[nitayack at cs.uchicago.edu]

This is an announcement of Fernando Granha's Dissertation Defense.
===============================================
Candidate: Fernando Granha

Date: Monday, August 30, 2021

Time: 11:30 am CST

Remote Location: Zoom link: https://uchicago.zoom.us/j/98390788486?pwd=cTZ0QXFPNjU3SUFieVNSYkt4OGVqdz09  Zoom password: 189225


Title: A Constrained Random Walk through Coding Theory

Abstract: We investigate some problems involving optimization, expansion, coding theory and pseudorandomness establishing some new connections among these fields.

Our first result is an approximation algorithm for constraint satisfaction problems (CSPs), where constraints are placed on the
edges of ``expanding" hypergraphs. This result (builds on and) generalizes known algorithms for graphs. Our algorithm is based on the
Sum-of-Squares semi-definite programming hierarchy and it is a natural higher-order generalization of the graph case.

Next, we observe that the task of decoding some well-known families of distance amplified codes using expanding structures can be reduced to approximating suitable ``expanding" CSPs. By enhancing the Sum-of-Squares hierarchy with an ``entropic" potential, we can, roughly speaking, obtain list decoding guarantees out of unique decoding. In this way, we obtain a new list decoding framework which is our second result.

In a breakthrough work, Ta-Shma [STOC 2017] found the first explicit family of $\epsilon$-balanced binary codes near the so-called
Gilbert--Varshamov bound (hence achieving nearly optimal distance versus rate trade-off). Put it simply, Ta-Shma's codes are distance
amplified codes using carefully desinged expanding structures. We obtain our third result by overcoming the far from optimal trade-offs
of our list decoding framework allowing us to provide the first polynomial time decoder for Ta-Shma's codes.

Finally, using pseudorandomness techniques based on our new weak regularity decomposition of sparse tensors (supported on expanding structures) we can also approximate the CSPs arising in the decoding tasks mentioned above. Thanks to the much faster computational time of finding weak regularity decompositions compared to solving Sum-of-Squares programs, we obtain our fourth result: a near-linear time decoder for Ta-Shma's codes.

Advisors: Madhur Tulsiani

Committee Members: Madhur Tulsiani, Janos Simon (Faculty Advocate), and Aaron Potechin