Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > COMMUNICATION LOWER BOUND:
Reports tagged with communication lower bound:
TR17-095 | 26th May 2017
Ran Gelles, Yael Tauman Kalai

#### Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks

Multiparty interactive coding allows a network of $n$ parties to perform distributed computations when the communication channels suffer from noise. Previous results (Rajagopalan and Schulman, STOC '94) obtained a multiparty interactive coding protocol, resilient to random noise, with a blowup of $O(\log(\Delta+1))$ for networks whose topology has a maximal degree ... more >>>

TR18-206 | 3rd December 2018

#### Equality Alone Does Not Simulate Randomness

Revisions: 1

The canonical problem that gives an exponential separation between deterministic and randomized communication complexity in the classical two-party communication model is Equality'. In this work, we show that even allowing access to an Equality' oracle, deterministic protocols remain exponentially weaker than randomized ones. More precisely, we exhibit a total function ... more >>>

TR21-011 | 13th February 2021
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy

#### Classification of the streaming approximability of Boolean CSPs

A Boolean constraint satisfaction problem (CSP), Max-CSP$(f)$, is a maximization problem specified by a constraint $f:\{-1,1\}^k\to\{0,1\}$. An instance of the problem consists of $m$ constraint applications on $n$ Boolean variables, where each constraint application applies the constraint to $k$ literals chosen from the $n$ variables and their negations. The goal ... more >>>

TR21-063 | 3rd May 2021
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy

#### Approximability of all finite CSPs in the dynamic streaming setting

Revisions: 3

A constraint satisfaction problem (CSP), Max-CSP$({\cal F})$, is specified by a finite set of constraints ${\cal F} \subseteq \{[q]^k \to \{0,1\}\}$ for positive integers $q$ and $k$. An instance of the problem on $n$ variables is given by $m$ applications of constraints from ${\cal F}$ to subsequences of the $n$ ... more >>>

TR21-086 | 22nd June 2021
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy

#### Linear Space Streaming Lower Bounds for Approximating CSPs

Revisions: 1

We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on $n$ variables taking values in $\{0,\ldots,q-1\}$, we prove that improving over the trivial approximability by a factor of $q$ requires $\Omega(n)$ space even on instances with $O(n)$ constraints. We also identify ... more >>>

ISSN 1433-8092 | Imprint