אודות
סיימתי את הדוקטורט במכון ויצמן תחת הנחייתו של פרופ' עודד גולדרייך, ולאחר מכן עשיתי פוסט-דוקטורט בסטנפורד (עם פרופ' לוקה טרויזן), במכון ללימודים מתקדמים בפרינסטון (עם פרופ' אבי ויגדרזון), ובמכון ויצמן (עם פרופ' אירית דינור).
פרסומים
- 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).
תחומי מחקר
אני חוקר את התיאוריה של מדעי המחשב, ובפרט, את תורת הסיבוכיות. בימים אלה אני מתעניין בעיקר בסיבוכיות מעגלים, סיבוכיות תקשורת, ודירנדומיזציה.
פרסים
- מלגת אוטו שוורץ
- מלגת אדמס של האקדמיה הישראלית למדעים
- הפרס ע"ש דימטרי כורפס
- מלגת רוטשילד