Raghuvansh R. Saxena

47 papers A* 26A 9Journal 12

Year	Rank	Type	Title / Venue / Authors
2026	A	`conf`	Optimal White-Box Adversarial Streaming Lower Bounds for Approximating LIS Length. ITCS Anna Gál, Gillat Kol, Raghuvansh R. Saxena, Huacheng Yu
2026	A	`conf`	Universally Optimal Streaming Algorithm for Random Walks in Dense Graphs. ITCS Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena, Zhijun Zhang
2025	J	`jnl`	Approximately Optimal Mechanism Design for Competing Sellers. CoRR Brendan Lucier, Raghuvansh R. Saxena
2025	A*	`conf`	Constant Rate Codes for Adaptive Broadcasts Do Not Exist. FOCS Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena
2025	A	`conf`	Polynomial Size, Short-Circuit Resilient Circuits for NC. ITCS Yael Tauman Kalai, Raghuvansh R. Saxena
2025	A	`conf`	Round-Vs-Resilience Tradeoffs for Binary Feedback Channels. ITCS Mark Braverman, Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena, Zhijun Zhang
2025	A*	`conf`	Streaming Algorithms via Local Algorithms for Maximum Directed Cut. SODA Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, Santhoshini Velusamy
2024	A	`conf`	Information Dissemination via Broadcasts in the Presence of Adversarial Noise. CCC Klim Efremenko, Gillat Kol, Dmitry Paramonov, Ran Raz, Raghuvansh R. Saxena
2024	J	`jnl`	Streaming Algorithms via Local Algorithms for Maximum Directed Cut. CoRR Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, Santhoshini Velusamy
2023	A	`conf`	An Improved Lower Bound for Matroid Intersection Prophet Inequalities. ITCS Raghuvansh R. Saxena, Santhoshini Velusamy, S. Matthew Weinberg
2023	A	`conf`	Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly. ITCS Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Huacheng Yu
2023	A*	`conf`	Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots. FOCS Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, Santhoshini Velusamy
2023	A*	`conf`	Interactive Coding with Small Memory. SODA Klim Efremenko, Bernhard Haeupler, Yael Tauman Kalai, Gillat Kol, Nicolas Resch, Raghuvansh R. Saxena
2023	A	`conf`	Noisy Radio Network Lower Bounds via Noiseless Beeping Lower Bounds. ITCS Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena
2023	A*	`conf`	Protecting Single-Hop Radio Networks from Message Drops. ICALP Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena
2023	A*	`conf`	Streaming complexity of CSPs with randomly ordered constraints. SODA Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy
2023	A*	`conf`	The Rate of Interactive Codes Is Bounded Away from 1. STOC Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena
2023	A*	`conf`	Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut. SODA Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu
2022	J	`jnl`	An Improved Lower Bound for Matroid Intersection Prophet Inequalities. CoRR Raghuvansh R. Saxena, Santhoshini Velusamy, S. Matthew Weinberg
2022	A*	`conf`	Binary Codes with Resilience Beyond 1/4 via Interaction. FOCS Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena, Zhijun Zhang
2022	A*	`conf`	Circuits resilient to short-circuit errors. STOC Klim Efremenko, Bernhard Haeupler, Yael Tauman Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh R. Saxena
2022	J	`jnl`	Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions. SIAM J. Comput. Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, S. Matthew Weinberg
2022	J	`jnl`	Streaming beyond sketching for Maximum Directed Cut. CoRR Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy
2022	J	`jnl`	Streaming complexity of CSPs with randomly ordered constraints. CoRR Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy
2021	A*	`conf`	99% Revenue with Constant Enhanced Competition. EC Linda Cai, Raghuvansh R. Saxena
2021	J	`jnl`	99% Revenue with Constant Enhanced Competition. CoRR Linda Cai, Raghuvansh R. Saxena
2021	A*	`conf`	Almost optimal super-constant-pass streaming lower bounds for reachability. STOC Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu
2021	A	`conf`	Computation over the Noisy Broadcast Channel with Malicious Parties. ITCS Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena
2021	A*	`conf`	Exponential communication separations between notions of selfishness. STOC Aviad Rubinstein, Raghuvansh R. Saxena, Clayton Thomas, S. Matthew Weinberg, Junyao Zhao
2021	A*	`conf`	Near Optimal Distributed Learning of Halfspaces with Two Parties. COLT Mark Braverman, Gillat Kol, Shay Moran, Raghuvansh R. Saxena
2021	A*	`conf`	Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs. ICALP Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu
2021	A*	`conf`	Optimal error resilience of adaptive message exchange. STOC Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena
2021	A*	`conf`	Tight Bounds for General Computation in Noisy Broadcast Networks. FOCS Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena
2020	A*	`conf`	Binary Interactive Error Resilience Beyond ${{}^{1}}\!/\!_{8}$ (or why $({{}^{1}}\!/\!_{2})^{3} > {{}^{1}}\!/\!_{8})$. FOCS Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena
2020	A*	`conf`	Deterministic and Efficient Interactive Coding from Hard-to-Decode Tree Codes. FOCS Zvika Brakerski, Yael Tauman Kalai, Raghuvansh R. Saxena
2020	J	`jnl`	Exponential Communication Separations between Notions of Selfishness. CoRR Aviad Rubinstein, Raghuvansh R. Saxena, Clayton Thomas, S. Matthew Weinberg, Junyao Zhao
2020	A*	`conf`	Interactive error resilience beyond 2/7. STOC Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena
2020	A*	`conf`	Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems. FOCS Sepehr Assadi, Gillat Kol, Raghuvansh R. Saxena, Huacheng Yu
2020	J	`jnl`	Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems. CoRR Sepehr Assadi, Gillat Kol, Raghuvansh R. Saxena, Huacheng Yu
2020	A*	`conf`	Noisy Beeps. PODC Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena
2020	A*	`conf`	Optimal Mechanism Design for Single-Minded Agents. EC Nikhil R. Devanur, Kira Goldner, Raghuvansh R. Saxena, Ariel Schvartzman, S. Matthew Weinberg
2020	J	`jnl`	Separating the Communication Complexity of Truthful and Non-Truthful Combinatorial Auctions. CoRR Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, S. Matthew Weinberg
2020	A*	`conf`	Separating the communication complexity of truthful and non-truthful combinatorial auctions. STOC Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, S. Matthew Weinberg
2019	J	`jnl`	Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility. CoRR Mark Braverman, Gillat Kol, Shay Moran, Raghuvansh R. Saxena
2018	A*	`conf`	Interactive Distributed Proofs. PODC Gillat Kol, Rotem Oshman, Raghuvansh R. Saxena
2018	A*	`conf`	The menu complexity of "one-and-a-half-dimensional" mechanism design. SODA Raghuvansh R. Saxena, Ariel Schvartzman, S. Matthew Weinberg
2017	J	`jnl`	The menu complexity of "one-and-a-half-dimensional" mechanism design. CoRR Raghuvansh R. Saxena, Ariel Schvartzman, S. Matthew Weinberg