All reports by Author Raghuvansh Saxena:

__
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

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 >>>