Or Meir

 

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

 

Phone: 04-8280785

 

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.

 

Publications:

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.

Conference version  Full version

 

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

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

Extended abstract appeared in the proceedings of STOC 2016, pages 202-215.

To appear in the Journal of the ACM.

Conference version  Full version

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

To appear in SICOMP.

Extended abstract appeared in the proceedings of STOC 2014.

Available as ECCC TR13-190.

Conference version  Full version

 

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.

Conference version  Full version

 

Combinatorial PCPs with Short Proofs

Or Meir

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.

Extended conference version Full version


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

Oded Goldreich, Or Meir

Transactions on Computation Theory 7(4): 16, 2015. Available as ECCC TR11-023.

Full version

 

IP = PSPACE using Error Correcting Codes

Or Meir

SICOMP 42(1), pages 380-403, 2013. Available as ECCC TR10-137.

Full version

 

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.

Conference version   Full version

 

Combinatorial PCPs with Efficient Verifiers

Or Meir

Computational Complexity 23(3), pages 355-478, 2014.

Extended abstract appeared in the proceedings of FOCS 2009, pages 463-471.

Brief Description   Overview   Full version

 

On the Efficiency of Non-Uniform PCPP Verifiers

Or Meir

ECCC TR08-064

Full version

 

Combinatorial Construction of Locally Testable Codes

Or Meir

Extended Abstract appeared in the proceedings of STOC 2008, pages 285-294

Full version appeared in SICOMP 39(2), pages 491-544, 2009.

Conference version   Full version

 

On the Rectangle Method in proofs of Robustness of Tensor Products

Or Meir

Appeared in Inf. Process. Lett. 112(8-9), pages 257-260, 2012.

ECCC TR07-061

Full version

 

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

Oded Goldreich, Or Meir

Appeared in Inf. Process. Lett. 112(8-9), pages 351-355, 2012.

ECCC TR07-062

Full version