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:

Shrinkage under Random Projections, and Cubic Formula Lower Bounds for AC0

Yuval Filmus, Or Meir, Avishay Tal

Conference version  Full version

 

KRW Composition Theorems via Lifting

Susanna de-Rezenda, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere

Conference version  Full version

 

 

Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling

Susanna de-Rezenda, Or Meir, Jakob Nordström, Robert Robere

Conference version  Full version

 

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

Conference version Full version

 

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

Or Meir

Full version

 

Query-to-Communication Lifting Using Low-Discrepancy Gadgets

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

Conference version  Full version

 

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

Or Meir and Avi Wigderson

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

Full version

 

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

Or Meir

Full version

 

The Direct Sum of Universal Relations

Or Meir

Full version

 

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

Irit Dinur, Or Meir

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

Conference version  Full version

 

Combinatorial Construction of Locally Testable Codes

Or Meir

Conference version   Full version

 

On the Rectangle Method in proofs of Robustness of Tensor Products

Or Meir

Full version

 

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

Oded Goldreich, Or Meir

Full version