Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > GILLAT KOL:
All reports by Author Gillat Kol:

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


TR16-113 | 22nd July 2016
Gillat Kol, Ran Raz, Avishay Tal

Time-Space Hardness of Learning Sparse Parities

We define a concept class ${\cal F}$ to be time-space hard (or memory-samples hard) if any learning algorithm for ${\cal F}$ requires either a memory of size super-linear in $n$ or a number of samples super-polynomial in $n$, where $n$ is the length of one sample.

A recent work shows ... more >>>


TR15-168 | 18th October 2015
Gillat Kol

Interactive Compression for Product Distributions

We study the interactive compression problem: Given a two-party communication protocol with small information cost, can it be compressed so that the total number of bits communicated is also small? We consider the case where the parties have inputs that are independent of each other, and give a simulation protocol ... more >>>


TR15-165 | 14th October 2015
Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson

Towards Optimal Deterministic Coding for Interactive Communication

Revisions: 1

We study \emph{efficient, deterministic} interactive coding schemes that simulate any interactive protocol both under random and adversarial errors, and can achieve a constant communication rate independent of the protocol length.

For channels that flip bits independently with probability~$\epsilon<1/2$, our coding scheme achieves a communication rate of $1 - O(\sqrt{H({\epsilon})})$ and ... more >>>


TR15-088 | 31st May 2015
Anat Ganor, Gillat Kol, Ran Raz

Exponential Separation of Communication and External Information

We show an exponential gap between communication complexity and external information complexity, by analyzing a communication task suggested as a candidate by Braverman [Bra13]. Previously, only a separation of communication complexity and internal information complexity was known [GKR14,GKR15].

More precisely, we obtain an explicit example of a search problem with ... more >>>


TR14-113 | 27th August 2014
Anat Ganor, Gillat Kol, Ran Raz

Exponential Separation of Information and Communication for Boolean Functions

We show an exponential gap between communication complexity and information complexity for boolean functions, by giving an explicit example of a partial function with information complexity $\leq O(k)$, and distributional communication complexity $\geq 2^k$. This shows that a communication protocol for a partial boolean function cannot always be compressed to ... more >>>


TR14-049 | 11th April 2014
Anat Ganor, Gillat Kol, Ran Raz

Exponential Separation of Information and Communication

Revisions: 1

We show an exponential gap between communication complexity and information complexity, by giving an explicit example for a communication task (relation), with information complexity $\leq O(k)$, and distributional communication complexity $\geq 2^k$. This shows that a communication protocol cannot always be compressed to its internal information. By a result of ... more >>>


TR14-046 | 8th April 2014
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff

Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound

We consider two known lower bounds on randomized communication complexity: The smooth rectangle bound and the logarithm of the approximate non-negative rank. Our main result is that they are the same up to a multiplicative constant and a small additive term.
The logarithm of the nonnegative rank is known to ... more >>>


TR13-079 | 2nd June 2013
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff

Direct Sum Fails for Zero Error Average Communication

We show that in the model of zero error communication complexity, direct sum fails for average communication complexity as well as for external information cost. Our example also refutes a version of a conjecture by Braverman et al. that in the zero error case amortized communication complexity equals external information ... more >>>


TR13-001 | 2nd January 2013
Gillat Kol, Ran Raz

Interactive Channel Capacity

Revisions: 1

We study the interactive channel capacity of an $\epsilon$-noisy channel. The interactive channel capacity $C(\epsilon)$ is defined as the minimal ratio between the communication complexity of a problem (over a non-noisy channel), and the communication complexity of the same problem over the binary symmetric channel with noise rate $\epsilon$, where ... more >>>


TR12-088 | 7th July 2012
Irit Dinur, Gillat Kol

Covering CSPs

We study the covering complexity of constraint satisfaction problems (CSPs). The covering number of a CSP instance C, denoted $\nu(C)$, is the smallest number of assignments to the variables, such that each constraint is satisfied by at least one of the assignments. This covering notion describes situations in which we ... more >>>


TR11-122 | 14th September 2011
Gillat Kol, Ran Raz

Competing Provers Protocols for Circuit Evaluation

Let $C$ be a (fan-in $2$) Boolean circuit of size $s$ and depth $d$, and let $x$ be an input for $C$. Assume that a verifier that knows $C$ but doesn't know $x$ can access the low degree extension of $x$ at one random point. Two competing provers try to ... more >>>


TR09-138 | 14th December 2009
Gillat Kol, Ran Raz

Bounds on 2-Query Locally Testable Codes with Affine Tests

We study Locally Testable Codes (LTCs) that can be tested by making two queries to the tested word using an affine test. That is, we consider LTCs over a finite field F, with codeword testers that only use tests of the form $av_i + bv_j = c$, where v is ... more >>>


TR09-128 | 29th November 2009
Gillat Kol, Ran Raz

Locally Testable Codes Analogues to the Unique Games Conjecture Do Not Exist

The Unique Games Conjecture (UGC) is possibly the most important open problem in the research of PCPs and hardness of approximation. The conjecture is a strengthening of the PCP Theorem, predicting the existence of a special type of PCP verifiers: 2-query verifiers that only make unique tests. Moreover, the UGC ... more >>>




ISSN 1433-8092 | Imprint