I am a faculty member in the Department of Computer Science at the University of Haifa.
E-mail: ormeir at cs dot haifa dot ac dot il
Office: Jacobs 412
Address: Department of Computer Science, University of Haifa, 31905, Israel
Research Interests: I am interested in all areas of Theoretical Computer Science, and in particular in Complexity Theory, Circuit Complexity, Probabilistically Checkable Proofs, Coding Theory and Derandomization.
· Editorial Board Member of Information Processing Letters (IPL).
· Program Committee Member of 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016).
· Associate Editor of special issue of SIAM Journal of Computing (SICOMP) dedicated to FOCS 2016.
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
Susanna de-Rezenda, Or Meir, Jakob Nordström, Robert Robere
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
Susanna de-Rezenda, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Marc Vinyals
Available as ECCC TR19-186.
Toward Better Depth Lower Bounds: Two Results on the Multiplexor Relation
Available as ECCC TR19-120.
Query-to-Communication Lifting Using Low-Discrepancy Gadgets
Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi
Extended abstract appeared in the proceedings of ICALP 2019, pages 35:1-35:15.
Available as ECCC TR19-103.
Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds
Or Meir and Avi Wigderson
Available as ECCC TR17-149.
On Derandomized Composition of Boolean Functions
Available as ECCC TR17-146.
The Choice and Agreement Problems of a Random Function
Or Meir and Avishay Tal
Inf. Process. Lett. 133, pages 16–20, 2018.
Available as ECCC TR17-148.
An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with Three Rounds
Available as ECCC TR17-129.
The Direct Sum of Universal Relations
Available as ECCC TR17-128.
Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity
Irit Dinur, Or Meir
Extended abstract appeared in the proceedings of CCC 2016, pages 3:1-3:51.
Available as ECCC TR16-035.
High rate locally-correctable and locally-testable codes with sub-polynomial query complexity
Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf
Journal of the ACM 64(2), pages 11:1-11:42, 2017.
Extended abstract appeared in the proceedings of STOC 2016, pages 202-215.
Preliminary versions of this paper were published in two separate technical reports on ECCC: TR14-107 and TR15-110.
Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture
Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
SICOMP 46(1), pages 114-131, 2017.
Extended abstract appeared in the proceedings of STOC 2014.
Available as ECCC TR13-190.
Constant rate PCPs for circuit-SAT with sublinear query complexity
Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir
With an Appendix by Henning Stichtenoth
Journal of the ACM 63(4), pages 32:1-32:57, 2016.
Extended abstract appeared in the proceedings of FOCS 2013, pages 320-329. Available as ECCC TR13-085.
Combinatorial PCPs with Short Proofs
Computational Complexity 25(1), pages 1-102, 2016.
Extended abstract appeared in the proceedings of CCC 2012, pages 345-355. Available as ECCC TR13-134.
Oded Goldreich, Or Meir
Transactions on Computation Theory 7(4): 16, 2015. Available as ECCC TR11-023.
IP = PSPACE using Error Correcting Codes
SICOMP 42(1), pages 380-403, 2013. Available as ECCC TR10-137.
Derandomized Parallel Repetition via Structured PCPs
Irit Dinur, Or Meir
Extended abstract appeared in the proceedings of CCC 2010, pages 16-27.
Invited paper in Computational Complexity 20(2), pages 207-327, 2011.
Combinatorial PCPs with Efficient Verifiers
Computational Complexity 23(3), pages 355-478, 2014.
Extended abstract appeared in the proceedings of FOCS 2009, pages 463-471.
On the Efficiency of Non-Uniform PCPP Verifiers
Available as ECCC TR08-064
Combinatorial Construction of Locally Testable Codes
Extended Abstract appeared in the proceedings of STOC 2008, pages 285-294
SICOMP 39(2), pages 491-544, 2009.
On the Rectangle Method in proofs of Robustness of Tensor Products
Inf. Process. Lett. 112(8-9), pages 257-260, 2012.
The Tensor Product of Two Good Codes Is Not Necessarily Robustly Testable
Oded Goldreich, Or Meir
Inf. Process. Lett. 112(8-9), pages 351-355, 2012.