All reports by Author Or Meir:

__
TR23-078
| 30th May 2023
__

Or Meir#### Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition

Revisions: 3

__
TR20-180
| 2nd December 2020
__

Yuval Filmus, Or Meir, Avishay Tal#### Shrinkage under Random Projections, and Cubic Formula Lower Bounds for $\mathbf{AC}^0$

Revisions: 3

__
TR20-099
| 6th July 2020
__

Susanna de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere#### KRW Composition Theorems via Lifting

Revisions: 1

__
TR20-001
| 31st December 2019
__

Or Meir, Jakob Nordström, Robert Robere, Susanna de Rezende#### Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling

Revisions: 2

__
TR19-186
| 31st December 2019
__

Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Susanna de Rezende#### Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity

Revisions: 4

__
TR19-120
| 11th September 2019
__

Or Meir#### Toward Better Depth Lower Bounds: Two Results on the Multiplexor Relation

Revisions: 2

__
TR19-103
| 7th August 2019
__

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi#### Query-to-Communication Lifting Using Low-Discrepancy Gadgets

Revisions: 2

__
TR17-149
| 7th October 2017
__

Or Meir, Avi Wigderson#### Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds

Revisions: 5

__
TR17-148
| 6th October 2017
__

Or Meir, Avishay Tal#### The Choice and Agreement Problems of a Random Function

Revisions: 3

__
TR17-146
| 1st October 2017
__

Or Meir#### On Derandomized Composition of Boolean Functions

Revisions: 4

__
TR17-129
| 27th August 2017
__

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

Revisions: 8

__
TR17-128
| 15th August 2017
__

Or Meir#### The Direct Sum of Universal Relations

Revisions: 3
,
Comments: 1

__
TR16-035
| 11th March 2016
__

Irit Dinur, Or Meir#### Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity

Revisions: 2

__
TR15-110
| 8th July 2015
__

Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf#### High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity

Revisions: 1

__
TR14-107
| 10th August 2014
__

Or Meir#### Locally Correctable and Testable Codes Approaching the Singleton Bound

Revisions: 2

__
TR13-190
| 28th December 2013
__

Dmytro Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson#### Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture

Revisions: 11

__
TR13-134
| 25th September 2013
__

Or Meir#### Combinatorial PCPs with Short Proofs

__
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

__
TR11-104
| 3rd August 2011
__

Or Meir#### Combinatorial PCPs with efficient verifiers

Revisions: 3

__
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

__
TR10-137
| 29th August 2010
__

Or Meir#### IP = PSPACE using Error Correcting Codes

Revisions: 7

__
TR10-107
| 6th July 2010
__

Irit Dinur, Or Meir#### Derandomized Parallel Repetition via Structured PCPs

Revisions: 3

__
TR08-064
| 11th July 2008
__

Or Meir#### On the Efficiency of Non-Uniform PCPP Verifiers

__
TR07-115
| 19th November 2007
__

Or Meir#### Combinatorial Construction of Locally Testable Codes

Revisions: 1

__
TR07-062
| 15th July 2007
__

Oded Goldreich, Or Meir#### The Tensor Product of Two Good Codes Is Not Necessarily Robustly Testable

Revisions: 2

__
TR07-061
| 12th July 2007
__

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

Revisions: 4

Or Meir

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., $\mathbf{P}\not\subseteq \mathbf{NC}^{1}$). Karchmer, Raz, and Wigderson (Computational Complexity 5(3/4), 1995) suggested to approach this problem by proving that depth complexity of a composition of functions $f \diamond g$ is roughly ... more >>>

Yuval Filmus, Or Meir, Avishay Tal

Håstad showed that any De Morgan formula (composed of AND, OR and NOT gates) shrinks by a factor of $O(p^{2})$ under a random restriction that leaves each variable alive independently with probability $p$ [SICOMP, 1998]. Using this result, he gave an $\widetilde{\Omega}(n^{3})$ formula size lower bound for the Andreev function, ... more >>>

Susanna de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}^1$). Karchmer, Raz, and Wigderson (Computational Complexity 5(3/4), 1995) suggested to approach this problem by proving that depth complexity behaves “as expected” with respect to the composition of functions $f ... more >>>

Or Meir, Jakob Nordström, Robert Robere, Susanna de Rezende

We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing that a graph $G$ can be reversibly pebbled in time $t$ and space $s$ if and only if there is a Nullstellensatz refutation of the pebbling formula over $G$ in size $t+1$ ... more >>>

Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Susanna de Rezende

We significantly strengthen and generalize the theorem lifting Nullstellensatz degree to monotone span program size by Pitassi and Robere (2018) so that it works for any gadget with high enough rank, in particular, for useful gadgets such as equality and greater-than. We apply our generalized theorem to solve two open ... more >>>

Or Meir

One of the major open problems in complexity theory is proving super-logarithmic

lower bounds on the depth of circuits (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}^1$). Karchmer, Raz, and Wigderson (Computational Complexity 5, 3/4) suggested to approach this problem by proving that depth complexity behaves "as expected" with respect to the composition of functions $f ...
more >>>

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi

Lifting theorems are theorems that relate the query complexity of a function $f:\left\{ 0,1 \right\}^n\to \left\{ 0,1 \right\}$ to the communication complexity of the composed function $f\circ g^n$, for some “gadget” $g:\left\{ 0,1 \right\}^b\times \left\{ 0,1 \right\}^b\to \left\{ 0,1 \right\}$. Such theorems allow transferring lower bounds from query complexity to ... more >>>

Or Meir, Avi Wigderson

Consider a random sequence of $n$ bits that has entropy at least $n-k$, where $k\ll n$. A commonly used observation is that an average coordinate of this random sequence is close to being uniformly distributed, that is, the coordinate “looks random”. In this work, we prove a stronger result that ... more >>>

Or Meir, Avishay Tal

The direct-sum question is a classical question that asks whether

performing a task on $m$ independent inputs is $m$ times harder

than performing it on a single input. In order to study this question,

Beimel et. al (Computational Complexity 23(1), 2014) introduced the following related problems:

* The choice ... more >>>

Or Meir

The composition of two Boolean functions $f:\left\{0,1\right\}^{m}\to\left\{0,1\right\}$, $g:\left\{0,1\right\}^{n}\to\left\{0,1\right\}$

is the function $f \diamond g$ that takes as inputs $m$ strings $x_{1},\ldots,x_{m}\in\left\{0,1\right\}^{n}$

and computes

\[

(f \diamond g)(x_{1},\ldots,x_{m})=f\left(g(x_{1}),\ldots,g(x_{m})\right).

\]

This operation has been used several times for amplifying different

hardness measures of $f$ and $g$. This comes at a cost: the ...
more >>>

Or Meir

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

Or Meir

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

Irit Dinur, Or Meir

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

Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf

An error correcting code is said to be \emph{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 small number of symbols

of the string. Locally testable codes (LTCs) are both interesting

in their ...
more >>>

Or Meir

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

Dmytro Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson

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

Or Meir

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

Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth

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

Or Meir

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

Oded Goldreich, Or Meir

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

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

Irit Dinur, Or Meir

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

Or Meir

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

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

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

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