All reports by Author Raghuvansh Saxena:

__
TR24-112
| 3rd July 2024
__

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena#### The Rate of Interactive Codes is Bounded Away from 1

__
TR23-066
| 4th May 2023
__

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena#### Protecting Single-Hop Radio Networks from Message Drops

__
TR22-179
| 16th December 2022
__

Mark Braverman, Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang#### Round-vs-Resilience Tradeoffs for Binary Feedback Channels

__
TR22-174
| 23rd November 2022
__

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena#### Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds

Revisions: 2

__
TR22-166
| 23rd November 2022
__

Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Huacheng Yu#### Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly

__
TR22-161
| 9th November 2022
__

Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu#### Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut

__
TR22-146
| 9th November 2022
__

Klim Efremenko, Bernhard Haeupler, Gillat Kol, Nicolas Resch, Raghuvansh Saxena, Yael Tauman Kalai#### Interactive Coding with Small Memory

__
TR22-144
| 7th November 2022
__

Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy#### Streaming beyond sketching for Maximum Directed Cut

__
TR22-129
| 15th September 2022
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang#### Binary Codes with Resilience Beyond 1/4 via Interaction

__
TR22-100
| 14th July 2022
__

Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy#### Streaming complexity of CSPs with randomly ordered constraints

__
TR22-050
| 12th April 2022
__

Klim Efremenko, Bernhard Haeupler, Yael Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh Saxena#### Circuits Resilient to Short-Circuit Errors

__
TR21-160
| 15th November 2021
__

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena#### Tight Bounds for General Computation in Noisy Broadcast Networks

__
TR21-060
| 8th April 2021
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena#### Optimal Error Resilience of Adaptive Message Exchange

__
TR21-051
| 8th April 2021
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena#### Binary Interactive Error Resilience Beyond $1/8$ (or why $(1/2)^3 > 1/8$)

__
TR21-027
| 24th February 2021
__

Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu#### Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability

__
TR21-001
| 1st January 2021
__

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena#### Computation Over the Noisy Broadcast Channel with Malicious Parties

__
TR20-137
| 11th September 2020
__

Zvika Brakerski, Yael Tauman Kalai, Raghuvansh Saxena#### Deterministic and Efficient Interactive Coding from Hard-to-Decode Tree Codes

__
TR20-022
| 19th February 2020
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena#### Interactive Error Resilience Beyond $\frac{2}{7}$

Revisions: 1

__
TR19-132
| 26th September 2019
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena#### Radio Network Coding Requires Logarithmic Overhead

Revisions: 1

__
TR19-111
| 16th August 2019
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena#### Noisy Beeps

__
TR17-093
| 22nd May 2017
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena#### Interactive Coding Over the Noisy Broadcast Channel

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Kol and Raz [STOC 2013] showed how to simulate any alternating two-party communication protocol designed to work over the noiseless channel, by a protocol that works over a stochastic channel that corrupts each sent symbol with probability $\epsilon>0$ independently, with only a $1+\mathcal{O}(\sqrt{\H(\epsilon)})$ blowup to the communication. In particular, this ... more >>>

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Single-hop radio networks (SHRN) are a well studied abstraction of communication over a wireless channel. In this model, in every round, each of the $n$ participating parties may decide to broadcast a message to all the others, potentially causing collisions. We consider the SHRN model in the presence of stochastic ... more >>>

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

In a celebrated result from the $60$'s, Berlekamp showed that feedback can be used to increase the maximum fraction of adversarial noise that can be tolerated by binary error correcting codes from $1/4$ to $1/3$. However, his result relies on the assumption that feedback is "continuous", i.e., after every utilization ... more >>>

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Much of today's communication is carried out over large wireless systems with different input-output behaviors. In this work, we compare the power of central abstractions of wireless communication through the general notion of boolean symmetric $f$-channels: In every round of the $f$-channel, each of its $n$ parties decides to either ... more >>>

Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Huacheng Yu

We study boolean constraint satisfaction problems (CSPs) $\mathrm{Max}\text{-}\mathrm{CSP}^f_n$ for all predicates $f: \{ 0, 1 \} ^k \to \{ 0, 1 \}$. In these problems, given an integer $v$ and a list of constraints over $n$ boolean variables, each obtained by applying $f$ to a sequence of literals, we wish ... more >>>

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

We consider the Max-Cut problem, asking how much space is needed by a streaming algorithm in order to estimate the value of the maximum cut in a graph. This problem has been extensively studied over the last decade, and we now have a near-optimal lower bound for one-pass streaming algorithms, ... more >>>

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

In this work, we design an interactive coding scheme that converts any two party interactive protocol $\Pi$ into another interactive protocol $\Pi'$, such that even if errors are introduced during the execution of $\Pi'$, the parties are able to determine what the outcome of running $\Pi$ would be in an ... more >>>

Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy

We give an $\widetilde{O}(\sqrt{n})$-space single-pass $0.483$-approximation streaming algorithm for estimating the maximum directed cut size (Max-DICUT) in a directed graph on $n$ vertices. This improves over an $O(\log n)$-space $4/9 < 0.45$ approximation algorithm due to Chou, Golovnev, Velusamy (FOCS 2020), which was known to be optimal for $o(\sqrt{n})$-space algorithms.

... more >>>Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang

In the reliable transmission problem, a sender, Alice, wishes to transmit a bit-string x to a remote receiver, Bob, over a binary channel with adversarial noise. The solution to this problem is to encode x using an error correcting code. As it is long known that the distance of binary ... more >>>

Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy

We initiate a study of the streaming complexity of constraint satisfaction problems (CSPs) when the constraints arrive in a random order. We show that there exists a CSP, namely Max-DICUT, for which random ordering makes a provable difference. Whereas a $4/9 \approx 0.445$ approximation of DICUT requires $\Omega(\sqrt{n})$ space with ... more >>>

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

Given a Boolean circuit $C$, we wish to convert it to a circuit $C'$ that computes the same function as $C$ even if some of its gates suffer from adversarial short circuit errors, i.e., their output is replaced by the value of one of their inputs [KLM97]. Can we ... more >>>

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Let $\Pi$ be a protocol over the $n$-party broadcast channel, where in each round, a pre-specified party broadcasts a symbol to all other parties. We wish to design a scheme that takes such a protocol $\Pi$ as input and outputs a noise resilient protocol $\Pi'$ that simulates $\Pi$ over the ... more >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

We study the error resilience of the message exchange task: Two parties, each holding a private input, want to exchange their inputs. However, the channel connecting them is governed by an adversary that may corrupt a constant fraction of the transmissions. What is the maximum fraction of corruptions that still ... more >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Interactive error correcting codes are codes that encode a two party communication protocol to an error-resilient protocol that succeeds even if a constant fraction of the communicated symbols are adversarially corrupted, at the cost of increasing the communication by a constant factor. What is the largest fraction of corruptions that ... more >>>

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

We give an almost quadratic $n^{2-o(1)}$ lower bound on the space consumption of any $o(\sqrt{\log n})$-pass streaming algorithm solving the (directed) $s$-$t$ reachability problem. This means that any such algorithm must essentially store the entire graph. As corollaries, we obtain almost quadratic space lower bounds for additional fundamental problems, including ... more >>>

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

We study the $n$-party noisy broadcast channel with a constant fraction of malicious parties. Specifically, we assume that each non-malicious party holds an input bit, and communicates with the others in order to learn the input bits of all non-malicious parties. In each communication round, one of the parties broadcasts ... more >>>

Zvika Brakerski, Yael Tauman Kalai, Raghuvansh Saxena

The field of Interactive Coding studies how an interactive protocol can be made resilient to channel errors. Even though this field has received abundant attention since Schulman's seminal paper (FOCS 92), constructing interactive coding schemes that are both deterministic and efficient, and at the same time resilient to adversarial errors ... more >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Interactive error correcting codes can protect interactive communication protocols against a constant fraction of adversarial errors, while incurring only a constant multiplicative overhead in the total communication. What is the maximum fraction of errors that such codes can protect against?

For the non-adaptive channel, where the parties must agree ... more >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

We consider the celebrated radio network model for abstracting communication in wireless networks. In this model, in any round, each node in the network may broadcast a message to all its neighbors. However, a node is able to hear a message broadcast by a neighbor only if no collision occurred, ... more >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

We study the effect of noise on the $n$-party beeping model. In this model, in every round, each party may decide to either `beep' or not. All parties hear a beep if and only if at least one party beeps. The beeping model is becoming increasingly popular, as it offers ... more >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

A set of $n$ players, each holding a private input bit, communicate over a noisy broadcast channel. Their mutual goal is for all players to learn all inputs. At each round one of the players broadcasts a bit to all the other players, and the bit received by each player ... more >>>