Carol Wang

SODA Conference 2017 Conference Paper

Maximally Recoverable Codes for Grid-like Topologies

• Parikshit Gopalan
• Guangda Hu
• Swastik Kopparty
• Shubhangi Saraf
• Carol Wang
• Sergey Yekhanin

SODA Conference 2015 Conference Paper

Limitations on Testable Affine-Invariant Codes in the High-Rate Regime

• Venkatesan Guruswami
• Madhu Sudan 0001
• Ameya Velingker
• Carol Wang

Locally testable codes (LTCs) of constant minimum (absolute) distance that allow the tester to make a nearly linear number of queries have become the focus of attention recently due to their connections to central questions in approximability theory. In particular, the binary Reed-Muller code of block length N and absolute distance d is known to be testable with O ( N/d ) queries, and has a dimension of  N – (log N ) log d. The polylogarithmically small co-dimension is the basis of constructions of small set expanders with many “bad” eigenvalues, and size-efficient PCPs based on a shorter version of the long code. The smallest possible co-dimension for a distance d code (without any testability requirement) is, achieved by BCH codes. This raises the natural question of understanding where in the spectrum between the two classical families, Reed-Muller and BCH, the optimal co-dimension of a distance d LTC lies — in other words the “price” one has to pay for local testability. One promising approach for constructing LTCs is to focus on affine-invariant codes, whose structure makes testing guarantees easier to deduce than for general codes. Along these lines, the authors of [HRZS13] and [GKS13] recently constructed an affine-invariant family of high-rate LTCs with slightly smaller co-dimension than Reed-Muller codes. In this work, we show that their construction is essentially optimal among linear affine-invariant LTCs that contain the Reed-Muller code of the appropriate degree.