High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity S Kopparty, O Meir, N Ron-Zewi, S Saraf
Journal of the ACM (JACM) 64 (2), 11, 2017
102 * 2017 Combinatorial construction of locally testable codes O Meir
Proceedings of the fortieth annual ACM symposium on Theory of computing, 285-294, 2008
67 2008 Toward better formula lower bounds: An information complexity approach to the KRW composition conjecture D Gavinsky, O Meir, O Weinstein, A Wigderson
Proceedings of the 46th Annual ACM Symposium on Theory of Computing, 213-222, 2014
60 * 2014 Toward the KRW composition conjecture: Cubic formula lower bounds via communication complexity I Dinur, O Meir
computational complexity 27 (3), 375-462, 2018
57 2018 Query-to-Communication Lifting Using Low-Discrepancy Gadgets A Chattopadhyay, Y Filmus, S Koroth, O Meir, T Pitassi
50 * 2019 IP= PSPACE using error-correcting codes O Meir
SIAM Journal on Computing 42 (1), 380-403, 2013
44 2013 Constant rate PCPs for circuit-SAT with sublinear query complexity E Ben-Sasson, Y Kaplan, S Kopparty, O Meir, H Stichtenoth
Journal of the ACM (JACM) 63 (4), 32, 2016
39 2016 Derandomized parallel repetition via structured PCPs I Dinur, O Meir
computational complexity 20, 207-327, 2011
37 * 2011 Combinatorial PCPs with efficient verifiers O Meir
computational complexity 23 (3), 355-478, 2014
33 * 2014 The tensor product of two good codes is not necessarily robustly testable O Goldreich, O Meir
Information Processing Letters 112 (8-9), 351-355, 2012
32 * 2012 Lifting with simple gadgets and applications to circuit and proof complexity S De Rezende, O Meir, J Nordström, T Pitassi, R Robere, M Vinyals
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 24-30, 2020
30 2020 Combinatorial PCPs with short proofs O Meir
computational complexity 25 (1), 1-102, 2016
22 2016 KRW composition theorems via lifting SF De Rezende, O Meir, J Nordström, T Pitassi, R Robere
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 43-49, 2020
20 2020 Toward better depth lower bounds: Two results on the multiplexor relation O Meir
computational complexity 29 (1), 4, 2020
19 2020 Improved composition theorems for functions and relations S Koroth, O Meir
Approximation, Randomization, and Combinatorial Optimization. Algorithms and …, 2018
19 2018 Prediction from partial information and hindsight, with application to circuit lower bounds O Meir, A Wigderson
computational complexity 28 (2), 145-183, 2019
13 2019 Nullstellensatz size-degree trade-offs from reversible pebbling SF De Rezende, O Meir, J Nordström, R Robere
computational complexity 30, 1-45, 2021
12 2021 On the rectangle method in proofs of robustness of tensor products O Meir
Information Processing Letters 112 (6), 257-260, 2012
12 * 2012 Input-oblivious proof systems and a uniform complexity perspective on P/poly O Goldreich, O Meir
ACM Transactions on Computation Theory (TOCT) 7 (4), 16, 2015
8 2015 Shrinkage under Random Projections, and Cubic Formula Lower Bounds for Y Filmus, O Meir, A Tal
Theory of Computing 19 (1), 1-51, 2023
6 2023 