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

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Lifting with Inner Functions of Polynomial Discrepancy.

Yahel Manor, Or Meir

Proceedings of the Approximation, 2022

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

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

KRW Composition Theorems via Lifting.

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

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

Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling.

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

Proceedings of the 34th Computational Complexity Conference, 2019

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

The Choice and Agreement Problems of a Random Function.

Or Meir, Avishay Tal

Electron. Colloquium Comput. Complex., 2017

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

Or Meir

Electron. Colloquium Comput. Complex., 2017

The Direct Sum of Universal Relations.

Or Meir

Electron. Colloquium Comput. Complex., 2017

2016

High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity.

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

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

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

Irit Dinur, Or Meir

Proceedings of the 31st Conference on Computational Complexity, 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

Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture.

Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson

Proceedings of the Symposium on Theory of Computing, 2014

2013

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

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

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

Combinatorial PCPs with Short Proofs.

Or Meir

Proceedings of the 27th Conference on Computational Complexity, 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

2009

Combinatorial PCPs with Efficient Verifiers.

Or Meir

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008

On the Efficiency of Non-Uniform PCPP Verifiers.

Or Meir

Electron. Colloquium Comput. Complex., 2008

Combinatorial construction of locally testable codes.

Or Meir

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

2007

On the Rectangle Method in proofs of Robustness of Tensor Products.

Or Meir

Electron. Colloquium Comput. Complex., 2007

The Tensor Product of Two Good Codes Is Not Necessarily Robustly Testable.

Oded Goldreich, Or Meir

Electron. Colloquium Comput. Complex., 2007