Irit Dinur, Madhu Sudan, Avi Wigderson

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

Or Meir

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

Oded Goldreich, Or Meir

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

Or Meir

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