Or Meir

According to our database, Or Meir authored at least 36 papers between 2007 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2023

Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition.

Or Meir

Electron. Colloquium Comput. Complex., 2023

2022

Lifting with Inner Functions of Polynomial Discrepancy.

Yahel Manor, Or Meir

Proceedings of the Approximation, 2022

2021

Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling.

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

Comput. Complex., 2021

Shrinkage Under Random Projections, and Cubic Formula Lower Bounds for AC0 (Extended Abstract).

Yuval Filmus, Or Meir, Avishay Tal

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

2020

Bridging a Small Gap in the Gap Amplification of Assignment Testers.

Oded Goldreich, Or Meir

Proceedings of the Computational Complexity and Property Testing, 2020

KRW Composition Theorems via Lifting.

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

Electron. Colloquium Comput. Complex., 2020

Shrinkage under Random Projections, and Cubic Formula Lower Bounds for AC⁰.

Yuval Filmus, Or Meir, Avishay Tal

Electron. Colloquium Comput. Complex., 2020

Toward Better Depth Lower Bounds: Two Results on the Multiplexor Relation.

Or Meir

Comput. Complex., 2020

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity.

Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Marc Vinyals

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Special Section on the Fifty-Seventh Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016).

Irit Dinur, Or Meir, Swastik Kopparty

SIAM J. Comput., 2019

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity.

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

Electron. Colloquium Comput. Complex., 2019

Query-to-Communication Lifting Using Low-Discrepancy Gadgets.

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

Electron. Colloquium Comput. Complex., 2019

Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds.

Or Meir, Avi Wigderson

Comput. Complex., 2019

On Derandomized Composition of Boolean Functions.

Or Meir

Comput. Complex., 2019

Query-To-Communication Lifting for BPP Using Inner Product.

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

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

The choice and agreement problems of a random function.

Or Meir, Avishay Tal

Inf. Process. Lett., 2018

The direct sum of universal relations.

Or Meir

Inf. Process. Lett., 2018

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

Irit Dinur, Or Meir

Comput. Complex., 2018

Improved Composition Theorems for Functions and Relations.

Sajin Koroth, Or Meir

Proceedings of the Approximation, 2018

2017

Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation.

Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson

SIAM J. Comput., 2017

High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity.

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

J. ACM, 2017

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

Or Meir

Electron. Colloquium Comput. Complex., 2017

2016

Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity.

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

J. ACM, 2016

Combinatorial PCPs with Short Proofs.

Or Meir

Comput. Complex., 2016

2015

High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity.

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

Electron. Colloquium Comput. Complex., 2015

2014

Locally Correctable and Testable Codes Approaching the Singleton Bound.

Or Meir

Electron. Colloquium Comput. Complex., 2014

Combinatorial PCPs with Efficient Verifiers.

Or Meir

Comput. Complex., 2014

2013

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

Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson

Electron. Colloquium Comput. Complex., 2013

2012

On the rectangle method in proofs of robustness of tensor products.

Or Meir

Inf. Process. Lett., 2012

The tensor product of two good codes is not necessarily robustly testable.

Oded Goldreich, Or Meir

Inf. Process. Lett., 2012

2011

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

Oded Goldreich, Or Meir

Electron. Colloquium Comput. Complex., 2011

Derandomized Parallel Repetition via Structured PCPs.

Irit Dinur, Or Meir

Comput. Complex., 2011

2010

IP = PSPACE using Error Correcting Codes.

Or Meir

Electron. Colloquium Comput. Complex., 2010

Derandomized Parallel Repetition of Structured PCPs.

Irit Dinur, Or Meir

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

2008

On the Efficiency of Non-Uniform PCPP Verifiers.

Or Meir

Electron. Colloquium Comput. Complex., 2008

2007

Combinatorial Construction of Locally Testable Codes.

Or Meir

Electron. Colloquium Comput. Complex., 2007