Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Or Meir:

TR17-129 | 27th August 2017
Or Meir

An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with Two Rounds

Revisions: 6

One of the important challenges in circuit complexity is proving strong
lower bounds for constant-depth circuits. One possible approach to
this problem is to use the framework of Karchmer-Wigderson relations:
Karchmer and Wigderson (SIDMA 3(2), 1990) observed that for every Boolean
function $f$ there is a corresponding communication problem $\mathrm{KW}_{f}$,
more >>>

TR17-128 | 15th August 2017
Or Meir

The Direct Sum of Universal Relations

Revisions: 2 , Comments: 1

The universal relation is the communication problem in which Alice and Bob get as inputs two distinct strings, and they are required to find a coordinate on which the strings differ. The study of this problem is motivated by its connection to Karchmer-Wigderson relations, which are communication problems that are ... more >>>

TR16-035 | 11th March 2016
Irit Dinur, Or Meir

Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity

Revisions: 2

One of the major challenges of the research in circuit complexity is proving super-polynomial lower bounds for de-Morgan formulas. Karchmer, Raz, and Wigderson suggested to approach this problem by proving that formula complexity behaves "as expected'' with respect to the composition of functions $f\circ g$. They showed that this conjecture, ... more >>>

TR14-107 | 10th August 2014
Or Meir

Locally Correctable and Testable Codes Approaching the Singleton Bound

Revisions: 2

Locally-correctable codes (LCCs) and locally-testable codes (LTCs) are codes that admit local algorithms for decoding and testing respectively. The local algorithms are randomized algorithms that make only a small number of queries to their input. LCCs and LTCs are both interesting in their own right, and have important applications in ... more >>>

TR13-190 | 28th December 2013
Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson

Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture

Revisions: 10

One of the major open problems in complexity theory is proving super-polynomial lower bounds for circuits with logarithmic depth (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}_1~$). This problem is interesting for two reasons: first, it is tightly related to understanding the power of parallel computation and of small-space computation; second, it is one of the ... more >>>

TR13-134 | 25th September 2013
Or Meir

Combinatorial PCPs with Short Proofs

The PCP theorem (Arora et. al., J. ACM 45(1,3)) asserts the existence of proofs that can be verified by reading a very small part of the proof. Since the discovery of the theorem, there has been a considerable work on improving the theorem in terms of the length of the ... more >>>

TR13-085 | 13th June 2013
Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth

Constant rate PCPs for circuit-SAT with sublinear query complexity

The PCP theorem (Arora et. al., J. ACM 45(1,3)) says that every NP-proof can be encoded to another proof, namely, a probabilistically checkable proof (PCP), which can be tested by a verifier that queries only a small part of the PCP. A natural question is how large is the blow-up ... more >>>

TR11-104 | 3rd August 2011
Or Meir

Combinatorial PCPs with efficient verifiers

Revisions: 3

The PCP theorem asserts the existence of proofs that can be verified by a verifier that reads only a very small part of the proof. The theorem was originally proved by Arora and Safra (J. ACM 45(1)) and Arora et al. (J. ACM 45(3)) using sophisticated algebraic tools. More than ... more >>>

TR11-023 | 16th February 2011
Oded Goldreich, Or Meir

Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly

Revisions: 5 , Comments: 2

We initiate a study of input-oblivious proof systems, and present a few preliminary results regarding such systems.
Our results offer a perspective on the intersection of the non-uniform complexity class P/poly with uniform complexity classes such as NP and IP.
In particular, we provide a uniform complexity formulation of the ... 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 >>>

TR10-107 | 6th July 2010
Irit Dinur, Or Meir

Derandomized Parallel Repetition via Structured PCPs

Revisions: 3

A PCP is a proof system for NP in which the proof can be checked by a probabilistic verifier. The verifier is only allowed to read a very small portion of the proof, and in return is allowed to err with some bounded probability. The probability that the verifier accepts ... more >>>

TR08-064 | 11th July 2008
Or Meir

On the Efficiency of Non-Uniform PCPP Verifiers

We define a non-uniform model of PCPs of Proximity, and observe that in this model the non-uniform verifiers can always be made very efficient. Specifically, we show that any non-uniform verifier can be modified to run in time that is roughly polynomial in its randomness and query complexity.

more >>>

TR07-115 | 19th November 2007
Or Meir

Combinatorial Construction of Locally Testable Codes

An error correcting code is said to be locally testable if there is a test that checks whether a given string is a codeword, or rather far from the code, by reading only a constant number of symbols of the string. Locally Testable Codes (LTCs) were first systematically studied by ... 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 >>>

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

ISSN 1433-8092 | Imprint