Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > CODES:
Reports tagged with codes:
TR06-117 | 31st August 2006
Arkadev Chattopadhyay, Michal Koucky, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien

#### Languages with Bounded Multiparty Communication Complexity

We study languages with bounded communication complexity in the multiparty "input on the forehead" model with worst-case partition. In the two party case, it is known that such languages are exactly those that are recognized by programs over commutative monoids. This can be used to show that these languages can ... more >>>

TR06-118 | 2nd September 2006
Irit Dinur, Madhu Sudan, Avi Wigderson

#### Robust Local Testability of Tensor Products of LDPC Codes

Given two binary linear codes R and C, their tensor product R \otimes C consists of all matrices with rows in R and columns in C. We analyze the "robustness" of the following test for this code (suggested by Ben-Sasson and Sudan~\cite{BenSasson-Sudan04}): Pick a random row (or column) and check ... more >>>

TR07-061 | 12th July 2007
Or Meir

#### On the Rectangle Method in proofs of Robustness of Tensor Products

Revisions: 4

Given linear two codes R,C, their tensor product $R \otimes C$
consists of all matrices whose rows are codewords of R and whose
columns are codewords of C. The product $R \otimes C$ is said to
be robust if for every matrix M that is far from $R \otimes C$
more >>>

TR07-062 | 15th July 2007
Oded Goldreich, Or Meir

#### The Tensor Product of Two Good Codes Is Not Necessarily Robustly Testable

Revisions: 2

Given two codes R,C, their tensor product $R \otimes C$ consists of all matrices whose rows are codewords of R and whose columns are codewords of C. The product $R \otimes C$ is said to be robust if for every matrix M that is far from $R \otimes C$ it ... more >>>

TR10-115 | 17th July 2010
Shachar Lovett, Emanuele Viola

#### Bounded-depth circuits cannot sample good codes

We study a variant of the classical circuit-lower-bound problems: proving lower bounds for sampling distributions given random bits. We prove a lower bound of $1-1/n^{\Omega(1)}$ on the statistical distance between (i) the output distribution of any small constant-depth (a.k.a.~$\mathrm{AC}^0$) circuit $f : \{0,1\}^{\mathrm{poly}(n)} \to \{0,1\}^n$, and (ii) the uniform distribution ... more >>>

TR10-137 | 29th August 2010
Or Meir

#### IP = PSPACE using Error Correcting Codes

Revisions: 5

The IP theorem, which asserts that IP = PSPACE (Lund et. al., and Shamir, in J. ACM 39(4)), is one of the major achievements of complexity theory. The known proofs of the theorem are based on the arithmetization technique, which transforms a quantified Boolean formula into a related polynomial. The ... more >>>

TR16-115 | 30th July 2016
Xin Li

#### Improved Non-Malleable Extractors, Non-Malleable Codes and Independent Source Extractors

In this paper we give improved constructions of several central objects in the literature of randomness extraction and tamper-resilient cryptography. Our main results are:

(1) An explicit seeded non-malleable extractor with error $\epsilon$ and seed length $d=O(\log n)+O(\log(1/\epsilon)\log \log (1/\epsilon))$, that supports min-entropy $k=\Omega(d)$ and outputs $\Omega(k)$ bits. Combined with ... more >>>

TR18-188 | 7th November 2018
Zeev Dvir, Alexander Golovnev, Omri Weinstein

#### Static Data Structure Lower Bounds Imply Rigidity

Revisions: 2

We show that static data structure lower bounds in the group (linear) model imply semi-explicit lower bounds on matrix rigidity. In particular, we prove that an explicit lower bound of $t \geq \omega(\log^2 n)$ on the cell-probe complexity of linear data structures in the group model, even against arbitrarily small ... more >>>

ISSN 1433-8092 | Imprint