Sourya Roy
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Sourya Roy has a total of 9 co-authors. Here are the top co-authors by number of shared publications:
- Joshua Z. Sobel
University of Iowa, Iowa City, USA
2 shared publications - Sriram V. Pemmaraju
University of Iowa, Iowa City, USA
2 shared publications - Avi Wigderson
Institute for Advanced Study, Technion Israel Institute of Technology
1 shared publication - Bhaswati Goswami
Jadavpur University
1 shared publication - Fernando Granha Jeronimo
University of Illinois, Urbana-Champaign, USA
1 shared publication - Gopal Pandurangan
University of Houston, Houston, USA
1 shared publication
Latest Publications
- Open Access
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 402-413
Improved Bounds for Distributed Random Walks and Spanning Trees
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 402-413
Open AccessImproved Bounds for Distributed Random Walks and Spanning Trees
- Open Access
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 337-348
Sublinear-Time Sampling of Spanning Trees in the Congested Clique
- 13 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 337-348
Open AccessSublinear-Time Sampling of Spanning Trees in the Congested Clique
- 14 August 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (2) , 1040-1049
Analyzing Ta-Shma’s Code via the Expander Mixing Lemma
Random walks in expander graphs and their various derandomizations ( e.g ., replacement=zig-zag product) are invaluable tools from pseudorandomness. Recently, Ta-Shma used s -wide replacement walks in his breakthrough construction of a binary linear code almost matching the Gilbert-Varshamov bound (STOC 2017). Ta-Shma’s original analysis was entirely linear algebraic, and subsequent developments have inherited this viewpoint. In this work, we rederive Ta-Shma’s analysis from a combinatorial point of view using repeated application of the expander mixing lemma . We hope that this alternate perspective will yield a better understanding of Ta-Shma’s construction. As an additional application of our techniques, we give an alternate proof of the expander hitting set lemma .
- 14 August 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (2) , 1040-1049
Analyzing Ta-Shma’s Code via the Expander Mixing Lemma
Random walks in expander graphs and their various derandomizations ( e.g ., replacement=zig-zag product) are invaluable tools from pseudorandomness. Recently, Ta-Shma used s -wide replacement walks in his breakthrough construction of a binary linear code almost matching the Gilbert-Varshamov bound (STOC 2017). Ta-Shma’s original analysis was entirely linear algebraic, and subsequent developments have inherited this viewpoint. In this work, we rederive Ta-Shma’s analysis from a combinatorial point of view using repeated application of the expander mixing lemma . We hope that this alternate perspective will yield a better understanding of Ta-Shma’s construction. As an additional application of our techniques, we give an alternate proof of the expander hitting set lemma .
- Open Access
Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification
We give an efficient algorithm that transforms any bounded degree expander graph into another that achieves almost optimal (namely, near-quadratic, $d \leq 1/\lambda^{2+o(1)}$) trade-off between (any desired) spectral expansion $\lambda$ and degree $d$. Furthermore, the algorithm is local: every vertex can compute its new neighbors as a subset of its original neighborhood of radius $O(\log(1/\lambda))$. The optimal quadratic trade-off is known as the Ramanujan bound, so our construction gives almost Ramanujan expanders from arbitrary expanders. The locality of the transformation preserves structural properties of the original graph, and thus has many consequences. Applied to Cayley graphs, our transformation shows that any expanding finite group has almost Ramanujan expanding generators. Similarly, one can obtain almost optimal explicit constructions of quantum expanders, dimension expanders, monotone expanders, etc., from existing (suboptimal) constructions of such objects. Another consequence is a "derandomized" random walk on the original (suboptimal) expander with almost optimal convergence rate. Our transformation also applies when the degree is not bounded or the expansion is not constant. We obtain our results by a generalization of Ta-Shma's technique in his breakthrough paper [STOC 2017], used to obtain explicit almost optimal binary codes. Specifically, our spectral amplification extends Ta-Shma's analysis of bias amplification from scalars to matrices of arbitrary dimension in a very natural way. Curiously, while Ta-Shma's explicit bias amplification derandomizes a well-known probabilistic argument (underlying the Gilbert--Varshamov bound), there seems to be no known probabilistic (or other existential) way of achieving our explicit ("high-dimensional") spectral amplification.Open AccessAlmost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification
We give an efficient algorithm that transforms any bounded degree expander graph into another that achieves almost optimal (namely, near-quadratic, $d \leq 1/\lambda^{2+o(1)}$) trade-off between (any desired) spectral expansion $\lambda$ and degree $d$. Furthermore, the algorithm is local: every vertex can compute its new neighbors as a subset of its original neighborhood of radius $O(\log(1/\lambda))$. The optimal quadratic trade-off is known as the Ramanujan bound, so our construction gives almost Ramanujan expanders from arbitrary expanders. The locality of the transformation preserves structural properties of the original graph, and thus has many consequences. Applied to Cayley graphs, our transformation shows that any expanding finite group has almost Ramanujan expanding generators. Similarly, one can obtain almost optimal explicit constructions of quantum expanders, dimension expanders, monotone expanders, etc., from existing (suboptimal) constructions of such objects. Another consequence is a "derandomized" random walk on the original (suboptimal) expander with almost optimal convergence rate. Our transformation also applies when the degree is not bounded or the expansion is not constant. We obtain our results by a generalization of Ta-Shma's technique in his breakthrough paper [STOC 2017], used to obtain explicit almost optimal binary codes. Specifically, our spectral amplification extends Ta-Shma's analysis of bias amplification from scalars to matrices of arbitrary dimension in a very natural way. Curiously, while Ta-Shma's explicit bias amplification derandomizes a well-known probabilistic argument (underlying the Gilbert--Varshamov bound), there seems to be no known probabilistic (or other existential) way of achieving our explicit ("high-dimensional") spectral amplification. - Open Access
- 1 January 2014
- Published by Elsevier in IFAC Proceedings Volumes
- Vol. 47 (1) , 333-339
Comparison of Cartesian and polar estimates of the EKF for different choices of the robustness and sensitivity metrics
- 1 January 2014
- Published by Elsevier in IFAC Proceedings Volumes
- Vol. 47 (1) , 333-339
Open AccessComparison of Cartesian and polar estimates of the EKF for different choices of the robustness and sensitivity metrics