Filter
Conference contribution

Search results

  • 2023

    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).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
  • 2022

    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).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • 2021

    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).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • 2020

    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).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
  • 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).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
  • 2019

    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).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • 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).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • 2018

    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).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • 2016

    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).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
  • 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).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • 2014

    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).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • 2013

    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).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access
  • 2012

    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).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • 2010

    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).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • 2009

    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).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • 2008

    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 output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    Open Access