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.
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for AC0
Yuval Filmus, Or Meir, Avishay Tal
KRW Composition Theorems via Lifting
Susanna de-Rezenda, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere
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
Toward Better Depth Lower Bounds: Two Results on the Multiplexor Relation
Query-to-Communication Lifting Using Low-Discrepancy Gadgets
Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi
Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds
Or Meir and Avi Wigderson
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
An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with Three Rounds
The Direct Sum of Universal Relations
Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity
Irit Dinur, Or Meir
High rate locally-correctable and locally-testable codes with sub-polynomial query complexity
Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf
Combinatorial Construction of Locally Testable Codes
On the Rectangle Method in proofs of Robustness of Tensor Products
The Tensor Product of Two Good Codes Is Not Necessarily Robustly Testable
Oded Goldreich, Or Meir