Sourya Roy

activity

20242026

collaborators

6 papers

cs.DS2026

Near-Optimal Online Metric Matching on $Δ$ -ary HST

Parth Gor, Sourya Roy, Kasturi Varadarajan

In the online metric matching problem, we have $n$ servers with known locations in some metric space. Requests arrive one-by-one at certain locations, and upon arrival a request mu…

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

cs.DC2024

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…

cs.CC2024

Derandomized Non-Abelian Homomorphism Testing in Low Soundness Regime