Raghuvansh Saxena

31 papers A* 2Journal 28
YearRankTypeTitle / Venue / Authors
2025 J jnl
Constant Rate Codes for Adaptive Broadcasts Do Not Exist.
Electron. Colloquium Comput. Complex.
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena
2025 J jnl
Information Dissemination via Broadcasts in the Presence of Adversarial Noise.
Electron. Colloquium Comput. Complex.
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Ran Raz, Raghuvansh Saxena
2025 J jnl
Optimal White-Box Adversarial Streaming Lower Bounds for Approximating LIS Length.
Electron. Colloquium Comput. Complex.
Anna Gál, Gillat Kol, Raghuvansh Saxena, Huacheng Yu
2025 J jnl
Polynomial Size, Short-Circuit Resilient Circuits for NC.
Electron. Colloquium Comput. Complex.
Raghuvansh Saxena, Yael Tauman Kalai
2025 J jnl
Universally Optimal Streaming Algorithm for Random Walks in Dense Graphs.
Electron. Colloquium Comput. Complex.
Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang
2024 J jnl
The Rate of Interactive Codes is Bounded Away from 1.
Electron. Colloquium Comput. Complex.
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena
2023 J jnl
Protecting Single-Hop Radio Networks from Message Drops.
Electron. Colloquium Comput. Complex.
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena
2022 J jnl
Binary Codes with Resilience Beyond 1/4 via Interaction.
Electron. Colloquium Comput. Complex.
Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang
2022 J jnl
Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly.
Electron. Colloquium Comput. Complex.
Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Huacheng Yu
2022 J jnl
Circuits Resilient to Short-Circuit Errors.
Electron. Colloquium Comput. Complex.
Klim Efremenko, Bernhard Haeupler, Yael Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh Saxena
2022 J jnl
Interactive Coding with Small Memory.
Electron. Colloquium Comput. Complex.
Klim Efremenko, Bernhard Haeupler, Gillat Kol, Nicolas Resch, Raghuvansh Saxena, Yael Tauman Kalai
2022 J jnl
Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds.
Electron. Colloquium Comput. Complex.
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena
2022 J jnl
Round-vs-Resilience Tradeoffs for Binary Feedback Channels.
Electron. Colloquium Comput. Complex.
Mark Braverman, Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang
2022 J jnl
Streaming beyond sketching for Maximum Directed Cut.
Electron. Colloquium Comput. Complex.
Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy
2022 J jnl
Streaming complexity of CSPs with randomly ordered constraints.
Electron. Colloquium Comput. Complex.
Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy
2022 J jnl
Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut.
Electron. Colloquium Comput. Complex.
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
2021 J jnl
Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability.
Electron. Colloquium Comput. Complex.
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
2021 J jnl
Binary Interactive Error Resilience Beyond $1/8$ (or why $(1/2)^3 > 1/8$).
Electron. Colloquium Comput. Complex.
Klim Efremenko, Gillat Kol, Raghuvansh Saxena
2021 — —
Communication Complexity: For Coding, Commerce, and Currents
Raghuvansh Saxena
2021 J jnl
Computation Over the Noisy Broadcast Channel with Malicious Parties.
Electron. Colloquium Comput. Complex.
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena
2021 J jnl
Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs.
CoRR
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu
2021 J jnl
Optimal Error Resilience of Adaptive Message Exchange.
Electron. Colloquium Comput. Complex.
Klim Efremenko, Gillat Kol, Raghuvansh Saxena
2021 J jnl
Tight Bounds for General Computation in Noisy Broadcast Networks.
Electron. Colloquium Comput. Complex.
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena
2020 J jnl
Deterministic and Efficient Interactive Coding from Hard-to-Decode Tree Codes.
Electron. Colloquium Comput. Complex.
Zvika Brakerski, Yael Tauman Kalai, Raghuvansh Saxena
2020 J jnl
Interactive Error Resilience Beyond 2/7.
Electron. Colloquium Comput. Complex.
Klim Efremenko, Gillat Kol, Raghuvansh Saxena
2020 J jnl
Optimal Mechanism Design for Single-Minded Agents.
CoRR
Nikhil R. Devanur, Kira Goldner, Raghuvansh Saxena, Ariel Schvartzman, S. Matthew Weinberg
2019 J jnl
Noisy Beeps.
Electron. Colloquium Comput. Complex.
Klim Efremenko, Gillat Kol, Raghuvansh Saxena
2019 A* conf
Radio Network Coding Requires Logarithmic Overhead.
FOCS
Klim Efremenko, Gillat Kol, Raghuvansh Saxena
2019 J jnl
Radio Network Coding Requires Logarithmic Overhead.
Electron. Colloquium Comput. Complex.
Klim Efremenko, Gillat Kol, Raghuvansh Saxena
2018 A* conf
Interactive coding over the noisy broadcast channel.
STOC
Klim Efremenko, Gillat Kol, Raghuvansh Saxena
2017 J jnl
Interactive Coding Over the Noisy Broadcast Channel.
Electron. Colloquium Comput. Complex.
Klim Efremenko, Gillat Kol, Raghuvansh Saxena