Sourya Roy

collaborators

4 papers

cs.CC2026

Low Soundness Linearity Testing on the Half-Slice

Haakon Larsen, Tushant Mittal, Silas Richelson +1

Let $f : T \to {0, 1}$ be a Boolean function on the Boolean half-slice, $T$ , \ie elements of ${0, 1}^{n}$ with Hamming weight $n /2$ . We show that if $f (x) + f (y) = f (x + y)$ holds with p…

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 $I^£$ , and study the mean of…

cs.DC2025

Sublinear-Time Sampling of Spanning Trees in the Congested Clique

Sriram V. Pemmaraju, Sourya Roy, Joshua Z. Sobel

We present the first sublinear-in- $n$ round algorithm for sampling an approximately uniform spanning tree of an $n$ -vertex graph in the CongestedClique model of distributed computi…