Raghuvansh R. Saxena

According to our database, Raghuvansh R. Saxena authored at least 36 papers between 2017 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

The Rate of Interactive Codes is Bounded Away from 1.

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Electron. Colloquium Comput. Complex., 2024

Information Dissemination via Broadcasts in the Presence of Adversarial Noise.

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Ran Raz, Raghuvansh R. Saxena

Proceedings of the 39th Computational Complexity Conference, 2024

2023

Protecting Single-Hop Radio Networks from Message Drops.

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Electron. Colloquium Comput. Complex., 2023

An Improved Lower Bound for Matroid Intersection Prophet Inequalities.

Raghuvansh R. Saxena, Santhoshini Velusamy, S. Matthew Weinberg

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

Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots.

Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, Santhoshini Velusamy

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.

Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, S. Matthew Weinberg

SIAM J. Comput., June, 2022

Streaming beyond sketching for Maximum Directed Cut.

Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy

Electron. Colloquium Comput. Complex., 2022

Streaming complexity of CSPs with randomly ordered constraints.

Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy

Electron. Colloquium Comput. Complex., 2022

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

Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Huacheng Yu

Electron. Colloquium Comput. Complex., 2022

Binary Codes with Resilience Beyond 1/4 via Interaction.

Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang

Electron. Colloquium Comput. Complex., 2022

Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds.

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Electron. Colloquium Comput. Complex., 2022

Interactive Coding with Small Memory.

Klim Efremenko, Bernhard Haeupler, Gillat Kol, Nicolas Resch, Raghuvansh Saxena, Yael Tauman Kalai

Electron. Colloquium Comput. Complex., 2022

Circuits Resilient to Short-Circuit Errors.

Klim Efremenko, Bernhard Haeupler, Yael Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh Saxena

Electron. Colloquium Comput. Complex., 2022

Round-vs-Resilience Tradeoffs for Binary Feedback Channels.

Mark Braverman, Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang

Electron. Colloquium Comput. Complex., 2022

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

Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu

Electron. Colloquium Comput. Complex., 2022

2021

Communication Complexity: For Coding, Commerce, and Currents

Raghuvansh Saxena

PhD thesis, 2021

Optimal Error Resilience of Adaptive Message Exchange.

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Electron. Colloquium Comput. Complex., 2021

Binary Interactive Error Resilience Beyond $1/8$ (or why $(1/2)^3 > 1/8$).

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Electron. Colloquium Comput. Complex., 2021

Tight Bounds for General Computation in Noisy Broadcast Networks.

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Electron. Colloquium Comput. Complex., 2021

Computation Over the Noisy Broadcast Channel with Malicious Parties.

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Electron. Colloquium Comput. Complex., 2021

Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability.

Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu

Electron. Colloquium Comput. Complex., 2021

Exponential communication separations between notions of selfishness.

Aviad Rubinstein, Raghuvansh R. Saxena, Clayton Thomas, S. Matthew Weinberg, Junyao Zhao

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

99% Revenue with Constant Enhanced Competition.

Linda Cai, Raghuvansh R. Saxena

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

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

Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu

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

Near Optimal Distributed Learning of Halfspaces with Two Parties.

Mark Braverman, Gillat Kol, Shay Moran, Raghuvansh R. Saxena

Proceedings of the Conference on Learning Theory, 2021

2020

Interactive Error Resilience Beyond 2/7.

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Electron. Colloquium Comput. Complex., 2020

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

Zvika Brakerski, Yael Tauman Kalai, Raghuvansh Saxena

Electron. Colloquium Comput. Complex., 2020

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

Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, S. Matthew Weinberg

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

Optimal Mechanism Design for Single-Minded Agents.

Nikhil R. Devanur, Kira Goldner, Raghuvansh R. Saxena, Ariel Schvartzman, S. Matthew Weinberg

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

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

Sepehr Assadi, Gillat Kol, Raghuvansh R. Saxena, Huacheng Yu

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

2019

Radio Network Coding Requires Logarithmic Overhead.

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Electron. Colloquium Comput. Complex., 2019

Noisy Beeps.

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Electron. Colloquium Comput. Complex., 2019

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

Mark Braverman, Gillat Kol, Shay Moran, Raghuvansh R. Saxena

CoRR, 2019

2018

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

Raghuvansh R. Saxena, Ariel Schvartzman, S. Matthew Weinberg

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

Interactive Distributed Proofs.

Gillat Kol, Rotem Oshman, Raghuvansh R. Saxena

Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

2017

Interactive Coding Over the Noisy Broadcast Channel.

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Electron. Colloquium Comput. Complex., 2017