Showing 2025Show all
2 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…