Showing 2025Show all
3 papers · 1 filter
cs.CC2025
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…
cs.CC2025
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…
cs.IT2025
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 o…