Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Raghuvansh Saxena:

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

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

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

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