7 papers
Low Soundness Linearity Testing on the Half-Slice
Haakon Larsen, Tushant Mittal, Silas Richelson +1
Let be a Boolean function on the Boolean half-slice, , \ie elements of with Hamming weight . We show that if holds with p…
A General Framework for Low Soundness Homomorphism Testing
Tushant Mittal, Sourya Roy
We introduce a general framework to design and analyze algorithms for the problem of testing homomorphisms between finite groups in the low-soundness regime. In this regime, we giv…
Pseudorandomness of Expander Walks via Fourier Analysis on Groups
Fernando Granha Jeronimo, Tushant Mittal, Sourya Roy
One approach to study the pseudorandomness properties of walks on expander graphs is to label the vertices of an expander with elements from an alphabet , and study the mean of…
Explicit Codes approaching Generalized Singleton Bound using Expanders
Fernando Granha Jeronimo, Tushant Mittal, Shashank Srivastava +1
We construct a new family of explicit codes that are list decodable to capacity and achieve an optimal list size of . In contrast to existing explicit constructions…
List Decodable Quantum LDPC Codes
Thiago Bergamaschi, Fernando Granha Jeronimo, Tushant Mittal +2
We give a construction of Quantum Low-Density Parity Check (QLDPC) codes with near-optimal rate-distance tradeoff and efficient list decoding up to the Johnson bound in polynomial…
Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification
Fernando Granha Jeronimo, Tushant Mittal, Sourya Roy +1
We give an efficient algorithm that transforms any bounded degree expander graph into another that achieves almost optimal (namely, near-quadratic, ) trade-of…