Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > RAGHUVANSH SAXENA:
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

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


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

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


TR21-160 | 15th November 2021
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Tight Bounds for General Computation in Noisy Broadcast Networks

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


TR21-060 | 8th April 2021
Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Optimal Error Resilience of Adaptive Message Exchange

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


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

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


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

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


TR21-001 | 1st January 2021
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Computation Over the Noisy Broadcast Channel with Malicious Parties

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


TR20-137 | 11th September 2020
Zvika Brakerski, Yael Tauman Kalai, Raghuvansh Saxena

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

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


TR20-022 | 19th February 2020
Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Interactive Error Resilience Beyond $\frac{2}{7}$

Revisions: 1

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


TR19-132 | 26th September 2019
Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Radio Network Coding Requires Logarithmic Overhead

Revisions: 1

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


TR19-111 | 16th August 2019
Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Noisy Beeps

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


TR17-093 | 22nd May 2017
Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Interactive Coding Over the Noisy Broadcast Channel

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




ISSN 1433-8092 | Imprint