About
I completed my Ph.d. at the Weizmann Institute of Science under the supervision of Prof. Oded Goldreich. After finishing my Ph.d., I was a postdoc at Stanford (hosted by Prof. Luca Trevisan), the Institute for Advanced Study (hosted by Prof. Avi Wigderson), and the Weizmann Institute of Science (hosted by Prof. Irit Dinur).
Publications
- TOWARD BETTER DEPTH LOWER BOUNDS: A KRW-LIKE THEOREM FOR STRONG COMPOSITION, Meir, O., 2025, In: SIAM Journal on Computing. 54, 5, p. 1193-1240 48 p.
- KRW Composition Theorems via Lifting, Rezende, S. F. D., Meir, O., Nordström, J., Pitassi, T. & Robere, R., Jun 2024, In: Computational Complexity. 33, 1, 4.
- Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition, Meir, O., 2023, Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023. IEEE Computer Society, p. 1056-1081 26 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).
- Shrinkage under Random Projections, and Cubic Formula Lower Bounds for AC0, Filmus, Y., Meir, O. & Tal, A., 2023, In: Theory of Computing. 19, 7.
- Lifting with Inner Functions of Polynomial Discrepancy, Manor, Y. & Meir, O., 1 Sep 2022, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2022. Chakrabarti, A. & Swamy, C. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 26. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 245).
- Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling, De Rezende, S. F., Meir, O., Nordström, J. & Robere, R., Jun 2021, In: Computational Complexity. 30, 1, 4.
- Shrinkage under random projections, and cubic formula lower bounds for AC0, Filmus, Y., Meir, O. & Tal, A., 1 Feb 2021, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021. Lee, J. R. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 89. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 185).
- Query-to-Communication Lifting Using Low-Discrepancy Gadgets, Chattopadhyay, A., Filmus, Y., Koroth, S., Meir, O. & Pitassi, T., 2021, In: SIAM Journal on Computing. 50, 1, p. 171-210 40 p.
- Lifting with simple gadgets and applications to circuit and proof complexity, De Rezende, S., Meir, O., Nordstrom, J., Pitassi, T., Robere, R. & Vinyals, M., Nov 2020, Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020. IEEE Computer Society, p. 24-30 7 p. 9317963. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2020-November).
- Krw composition theorems via lifting, De Rezende, S. F., Meir, O., Nordstrom, J., Pitassi, T. & Robere, R., Nov 2020, Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020. IEEE Computer Society, p. 43-49 7 p. 9317931. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2020-November).
- Toward Better Depth Lower Bounds: Two Results on the Multiplexor Relation, Meir, O., 1 Jun 2020, In: Computational Complexity. 29, 1, 4.
- Bridging a small gap in the gap amplification of assignment testers, Goldreich, O. & Meir, O., 2020, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer, p. 9-16 8 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 12050 LNCS).
- On Derandomized Composition of Boolean Functions, Meir, O., 1 Dec 2019, In: Computational Complexity. 28, 4, p. 661-708 48 p.
- Query-to-communication lifting for BPP using inner product, Chattopadhyay, A., Filmus, Y., Koroth, S., Meir, O. & Pitassi, T., 1 Jul 2019, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019. Baier, C., Chatzigiannakis, I., Flocchini, P. & Leonardi, S. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 35:1–35:15 35. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 132).
- Nullstellensatz size-degree trade-offs from reversible pebbling, De Rezende, S. F., Nordström, J., Meir, O. & Robere, R., 1 Jul 2019, 34th Computational Complexity Conference, CCC 2019. Shpilka, A. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 18:1–18:16 (Leibniz International Proceedings in Informatics, LIPIcs; vol. 137).
- Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds, Meir, O. & Wigderson, A., 1 Jun 2019, In: Computational Complexity. 28, 2, p. 145-183 39 p.
- Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity, Dinur, I. & Meir, O., 1 Sep 2018, In: Computational Complexity. 27, 3, p. 375-462 88 p.
- The direct sum of universal relations, Meir, O., Aug 2018, In: Information Processing Letters. 136, p. 105-111 7 p.
- Improved composition theorems for functions and relations, Koroth, S. & Meir, O., 1 Aug 2018, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018. Blais, E., Rolim, J. D. P., Steurer, D. & Jansen, K. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 48. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 116).
- The choice and agreement problems of a random function, Meir, O. & Tal, A., May 2018, In: Information Processing Letters. 133, p. 16-20 5 p.
- High-rate locally correctable and locally testable codes with sub-polynomial query complexity, Kopparty, S., Meir, O., Ron-Zewi, N. & Saraf, S., May 2017, In: Journal of the ACM. 64, 2, 11.
- Special section on the fifty-seventhth annual IEEE symposium on foundations of computer science (2016), Dinur, I. (Editor), Meir, O. (Editor) & Kopparty, S. (Editor), 2017, In: SIAM Journal on Computing. 48, 2
- Toward better formula lower bounds: The composition of a function and a universal relation, Gavinsky, D., Meir, O., Weinstein, O. & Wigderson, A., 2017, In: SIAM Journal on Computing. 46, 1, p. 114-131 18 p.
- Constant rate PCPs for circuit-SAT with sublinear query complexity, Ben-Sasson, E., Kaplan, Y., Kopparty, S., Meir, O. & Stichtenoth, H., Nov 2016, In: Journal of the ACM. 63, 4, 32.
- High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity, Kopparty, S., Meir, O., Ron-Zewi, N. & Saraf, S., 19 Jun 2016, STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. Mansour, Y. & Wichs, D. (eds.). Association for Computing Machinery, p. 202-215 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. 19-21-June-2016).
- Toward the KRW composition conjecture: Cubic formula lower bounds via communication complexity, Dinur, I. & Meir, O., 1 May 2016, 31st Conference on Computational Complexity, CCC 2016. Raz, R. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 3:1-3:51 (Leibniz International Proceedings in Informatics, LIPIcs; vol. 50).
- Combinatorial PCPs with Short Proofs, Meir, O., 1 Mar 2016, In: Computational Complexity. 25, 1, p. 1-102 102 p.
- Input-oblivious proof systems and a uniform complexity perspective on P/poly, Goldreich, O. & Meir, O., 1 Aug 2015, In: ACM Transactions on Computation Theory. 7, 4, 16.
- Combinatorial PCPs with Efficient Verifiers, Meir, O., 1 Sep 2014, In: Computational Complexity. 23, 3, p. 355-478 124 p.
- Toward better formula lower bounds: An information complexity approach to the KRW composition conjecture, Gavinsky, D., Meir, O., Weinstein, O. & Wigderson, A., 2014, STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 213-222 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).
- Constant rate PCPs for circuit-SAT with sublinear query complexity, Ben-Sasson, E., Kaplan, Y., Kopparty, S., Meir, O. & Stichtenoth, H., 2013, Proceedings - 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013. p. 320-329 10 p. 6686168. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).
- IP = PSPACE using error-correcting codes, Meir, O., 2013, In: SIAM Journal on Computing. 42, 1, p. 380-403 24 p.
- The tensor product of two good codes is not necessarily robustly testable, Goldreich, O. & Meir, O., 30 Apr 2012, In: Information Processing Letters. 112, 8-9, p. 351-355 5 p.
- On the rectangle method in proofs of robustness of tensor products, Meir, O., 15 Mar 2012, In: Information Processing Letters. 112, 6, p. 257-260 4 p.
- Combinatorial PCPs with short proofs, Meir, O., 2012, Proceedings - 2012 IEEE 27th Conference on Computational Complexity, CCC 2012. p. 345-355 11 p. 6243411. (Proceedings of the Annual IEEE Conference on Computational Complexity).
- Derandomized Parallel Repetition via Structured PCPs, Dinur, I. & Meir, O., Jun 2011, In: Computational Complexity. 20, 2, p. 207-327 121 p.
- Derandomized parallel repetition of structured PCPs, Dinur, I. & Meir, O., 2010, Proceedings - 25th Annual IEEE Conference on Computational Complexity, CCC 2010. p. 16-27 12 p. 5497901. (Proceedings of the Annual IEEE Conference on Computational Complexity).
- Combinatorial PCPs with efficient verifiers, Meir, O., 2009, Proceedings - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009. p. 463-471 9 p. 5438606. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).
- Combinatorial Construction of Locally Testable Codes, Meir, O., 2009, In: SIAM Journal on Computing. 39, 2, p. 491-544 54 p.
- Combinatorial construction of locally testable codes, Meir, O., 2008, STOC'08: Proceedings of the 2008 ACM Symposium on Theory of Computing. Association for Computing Machinery (ACM), p. 285-294 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).
Research Areas
My research area is theoretical computer science, and specifically complexity theory. These days I am particularly interested in circuit complexity, communication complexity, and derandomization.
Awards
- Otto Schwartz Excellence Award
- The Adams Fellowship of the National Israeli Academy of Science
- The Dimitris N. Chorafas Prize
- The Rothschild Fellowship of Yad Hanadiv