Or Meir

Orcid: 0000-0001-5031-0750

Affiliations:
  • University of Haifa, Department of Computer Science, Israel
  • Weizmann Institute of Science, Rehovot, Israel


According to our database1, Or Meir authored at least 36 papers between 2008 and 2024.

Collaborative distances:

Timeline

2008
2010
2012
2014
2016
2018
2020
2022
2024
0
1
2
3
4
5
6
1
2
1
2
2
4
3
3
1
1
2
3
2
2
1
1
1
1
1
1
1

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
KRW Composition Theorems via Lifting.
Comput. Complex., June, 2024

Lifting with Inner Functions of Polynomial Discrepancy.
Electron. Colloquium Comput. Complex., 2024

2023
Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition.
Electron. Colloquium Comput. Complex., 2023

2021
Query-to-Communication Lifting Using Low-Discrepancy Gadgets.
SIAM J. Comput., 2021

Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling.
Comput. Complex., 2021

Shrinkage Under Random Projections, and Cubic Formula Lower Bounds for AC0 (Extended Abstract).
Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

2020
Bridging a Small Gap in the Gap Amplification of Assignment Testers.
Proceedings of the Computational Complexity and Property Testing, 2020

Shrinkage under Random Projections, and Cubic Formula Lower Bounds for AC<sup>0</sup>.
Electron. Colloquium Comput. Complex., 2020

Toward Better Depth Lower Bounds: Two Results on the Multiplexor Relation.
Comput. Complex., 2020

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019
Special Section on the Fifty-Seventh Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016).
SIAM J. Comput., 2019

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity.
Electron. Colloquium Comput. Complex., 2019

Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds.
Comput. Complex., 2019

On Derandomized Composition of Boolean Functions.
Comput. Complex., 2019

Query-To-Communication Lifting for BPP Using Inner Product.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018
The choice and agreement problems of a random function.
Inf. Process. Lett., 2018

The direct sum of universal relations.
Inf. Process. Lett., 2018

Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity.
Comput. Complex., 2018

Improved Composition Theorems for Functions and Relations.
Proceedings of the Approximation, 2018

2017
Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation.
SIAM J. Comput., 2017

High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity.
J. ACM, 2017

An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with Two Rounds.
Electron. Colloquium Comput. Complex., 2017

2016
Combinatorial PCPs with Short Proofs.
Comput. Complex., 2016

2015
High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity.
Electron. Colloquium Comput. Complex., 2015

2014
Locally Correctable and Testable Codes Approaching the Singleton Bound.
Electron. Colloquium Comput. Complex., 2014

Combinatorial PCPs with Efficient Verifiers.
Comput. Complex., 2014

2013
IP = PSPACE Using Error-Correcting Codes.
SIAM J. Comput., 2013

Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture.
Electron. Colloquium Comput. Complex., 2013

Constant rate PCPs for circuit-SAT with sublinear query complexity.
Electron. Colloquium Comput. Complex., 2013

2012
On the rectangle method in proofs of robustness of tensor products.
Inf. Process. Lett., 2012

The tensor product of two good codes is not necessarily robustly testable.
Inf. Process. Lett., 2012

2011
Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly.
Electron. Colloquium Comput. Complex., 2011

Derandomized Parallel Repetition via Structured PCPs.
Comput. Complex., 2011

2010
Derandomized Parallel Repetition of Structured PCPs.
Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

2009
Combinatorial Construction of Locally Testable Codes.
SIAM J. Comput., 2009

2008
On the Efficiency of Non-Uniform PCPP Verifiers.
Electron. Colloquium Comput. Complex., 2008


  Loading...