Raghuvansh R. Saxena

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

Round-Vs-Resilience Tradeoffs for Binary Feedback Channels.

[BibT_eX]

[DOI]

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

2024

Information Dissemination via Broadcasts in the Presence of Adversarial Noise.

[BibT_eX]

[DOI]

Proceedings of the 39th Computational Complexity Conference, 2024

2023

The Rate of Interactive Codes Is Bounded Away from 1.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Streaming complexity of CSPs with randomly ordered constraints.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Interactive Coding with Small Memory.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

An Improved Lower Bound for Matroid Intersection Prophet Inequalities.

[BibT_eX]

[DOI]

Santhoshini Velusamy

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly.

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Noisy Radio Network Lower Bounds via Noiseless Beeping Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Protecting Single-Hop Radio Networks from Message Drops.

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions.

[BibT_eX]

[DOI]

Sepehr Assadi

Hrishikesh Khandeparkar

SIAM J. Comput., June, 2022

Streaming beyond sketching for Maximum Directed Cut.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Circuits resilient to short-circuit errors.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Binary Codes with Resilience Beyond 1/4 via Interaction.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Communication Complexity: For Coding, Commerce, and Currents

[BibT_eX]

[DOI]

Raghuvansh Saxena

PhD thesis, 2021

Exponential communication separations between notions of selfishness.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Optimal error resilience of adaptive message exchange.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Almost optimal super-constant-pass streaming lower bounds for reachability.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

99% Revenue with Constant Enhanced Competition.

[BibT_eX]

[DOI]

Linda Cai

Proceedings of the EC '21: The 22nd ACM Conference on Economics and Computation, 2021

Computation over the Noisy Broadcast Channel with Malicious Parties.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Tight Bounds for General Computation in Noisy Broadcast Networks.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Near Optimal Distributed Learning of Halfspaces with Two Parties.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

2020

Interactive error resilience beyond 2/7.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Separating the communication complexity of truthful and non-truthful combinatorial auctions.

[BibT_eX]

[DOI]

Sepehr Assadi

Hrishikesh Khandeparkar

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Optimal Mechanism Design for Single-Minded Agents.

[BibT_eX]

[DOI]

Proceedings of the EC '20: The 21st ACM Conference on Economics and Computation, 2020

Noisy Beeps.

[BibT_eX]

[DOI]

Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

Binary Interactive Error Resilience Beyond ${{}^{1}}\!/\!_{8}$ (or why $({{}^{1}}\!/\!_{2})^{3} > {{}^{1}}\!/\!_{8})$.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Deterministic and Efficient Interactive Coding from Hard-to-Decode Tree Codes.

[BibT_eX]

[DOI]

Zvika Brakerski

Yael Tauman Kalai

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility.

[BibT_eX]

[DOI]

CoRR, 2019

Radio Network Coding Requires Logarithmic Overhead.

[BibT_eX]

[DOI]

Raghuvansh Saxena

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Interactive coding over the noisy broadcast channel.

[BibT_eX]

[DOI]

Raghuvansh Saxena

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

The menu complexity of "one-and-a-half-dimensional" mechanism design.

[BibT_eX]

[DOI]

Ariel Schvartzman

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Interactive Distributed Proofs.

[BibT_eX]

[DOI]

Rotem Oshman