2 citations · 2 across the 6 of their papers we have counts for
9 papers · 1 filter
Lifting with Inner Functions of Polynomial Discrepancy
Yahel Manor, Or Meir
Lifting theorems are theorems that bound the communication complexity of a composed function in terms of the query complexity of and the communication complexity…
Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition
Or Meir
One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., ). Karchmer, R…
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for
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 under a random restriction…
KRW Composition Theorems via Lifting
Susanna F. de Rezende, Or Meir, Jakob Nordström +2
One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., ). Karchmer, Raz…
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
Susanna F. de Rezende, Or Meir, Jakob Nordström +1
We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing that a graph can be reversibly pebbl…
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
Susanna F. de Rezende, Or Meir, Jakob Nordström +3
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 wit…
Query-to-Communication Lifting Using Low-Discrepancy Gadgets
Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth +2
Lifting theorems are theorems that relate the query complexity of a function to the communication complexity of the composed function , for…
High rate locally-correctable and locally-testable codes with sub-polynomial query complexity
Swastik Kopparty, Or Meir, Noga Ron-Zewi +1
In this work, we construct the first locally-correctable codes (LCCs), and locally-testable codes (LTCs) with constant rate, constant relative distance, and sub-polynomial query co…
Derandomized Parallel Repetition via Structured PCPs
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…