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.

 

Professional Activities:

·         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.

Publications:

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

Or Meir and Avi Wigderson

Available as ECCC TR17-149.

Full version

 

On Derandomized Composition of Boolean Functions

Or Meir

Available as ECCC TR17-146.

Full version

 

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.

Full version

 

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

Or Meir

Available as ECCC TR17-129.

Full version

 

The Direct Sum of Universal Relations

Or Meir

Available as ECCC TR17-128.

Full version

 

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

Journal of the ACM 64(2), pages 11:1-11:42, 2017.

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

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

SICOMP 46(1), pages 114-131, 2017.

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

Available as 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

SICOMP 39(2), pages 491-544, 2009.

Conference version   Full version

 

On the Rectangle Method in proofs of Robustness of Tensor Products

Or Meir

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

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

ECCC TR07-062

Full version