20112023

Research activity per year

Filter
Conference contribution

Search results

  • 2022

    Proving as fast as computing: succinct arguments with constant prover overhead

    Ron-Zewi, N. & Rothblum, R. D., 6 Sep 2022, STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Leonardi, S. & Gupta, A. (eds.). Association for Computing Machinery, p. 1353-1363 11 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

  • 2021

    Efficient list-decoding with constant alphabet and list sizes

    Guo, Z. & Ron-Zewi, N., 15 Jun 2021, STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Khuller, S. & Williams, V. V. (eds.). Association for Computing Machinery, p. 1502-1515 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

    Open Access
  • Query Complexity Lower Bounds for Local List-Decoding and Hard-Core Predicates (Even for Small Rate and Huge Lists)

    Shaltiel, R., Ron-Zewi, N. & Varma, N., 2021, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Lee, J. R. (ed.). Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum für Informatik, Vol. 185. p. 33:1-33:18 33. (Leibniz International Proceedings in Informatics (LIPIcs)).

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

  • 2020

    Ldpc codes achieve list decoding capacity

    Mosheiff, J., Resch, N., Ron-Zewi, N., Silas, S. & Wootters, M., Nov 2020, Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020. IEEE Computer Society, p. 458-469 12 p. 9317881. (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
  • Linear-time Erasure List-decoding of Expander Codes

    Ron-Zewi, N., Wootters, M. & Zemor, G., Jun 2020, 2020 IEEE International Symposium on Information Theory, ISIT 2020 - Proceedings. Institute of Electrical and Electronics Engineers Inc., p. 379-383 5 p. 9174325. (IEEE International Symposium on Information Theory - Proceedings; vol. 2020-June).

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

    Open Access
  • Local proofs approaching the witness length [extended abstract]

    Ron-Zewi, N. & Rothblum, R. D., Nov 2020, Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020. IEEE Computer Society, p. 846-857 12 p. 9317981. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2020-November).

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

  • 2019

    Erasures vs. errors in local decoding and property testing

    Raskhodnikova, S., Ron-Zewi, N. & Varma, N., 1 Jan 2019, 10th Innovations in Theoretical Computer Science, ITCS 2019. Blum, A. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 63. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 124).

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

  • From local to robust testing via agreement testing

    Dinur, I., Harsha, P., Kaufman, T. & Ron-Zewi, N., 1 Jan 2019, 10th Innovations in Theoretical Computer Science, ITCS 2019. Blum, A. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 29. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 124).

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

  • On list recovery of high-rate tensor codes

    Kopparty, S., Resch, N., Ron-Zewi, N., Saraf, S. & Silas, S., Sep 2019, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019. Achlioptas, D. & Vegh, L. A. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 68. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 145).

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

  • 2018

    Improved decoding of folded reed-solomon and multiplicity codes

    Kopparty, S., Ron-Zewi, N., Saraf, S. & Wootters, M., 30 Nov 2018, Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018. Thorup, M. (ed.). IEEE Computer Society, p. 212-223 12 p. 8555107. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2018-October).

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

    Open Access
  • 2017

    Local list recovery of high-rate tensor codes & applications

    Hemenway, B., Ron-Zewi, N. & Wootters, M., 10 Nov 2017, Proceedings - 58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017. IEEE Computer Society, p. 204-215 12 p. 8104059. (Annual Symposium on Foundations of Computer Science - Proceedings; vol. 2017-October).

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

  • Locally testable and locally correctable codes approaching the gilbert-varshamov bound

    Gopi, S., Kopparty, S., Oliveira, R., Ron-Zewi, N. & Saraf, S., 2017, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. Klein, P. N. (ed.). Association for Computing Machinery, p. 2073-2091 19 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 0).

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

    Open Access
  • 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
  • On public key encryption from noisy codewords

    Ben-Sasson, E., Ben-Tov, I., Damgård, I., Ishai, Y. & Ron-Zewi, N., 2016, Public-Key Cryptography – PKC 2016 - 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings. Cheng, C-M., Chung, K-M., Yang, B-Y. & Persiano, G. (eds.). Springer Verlag, p. 417-446 30 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 9615).

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

    Open Access
  • Towards optimal deterministic coding for interactive communication

    Gelles, R., Haeupler, B., Kol, G., Ron-Zewi, N. & Wigderson, A., 2016, 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016. Krauthgamer, R. (ed.). Association for Computing Machinery, p. 1922-1936 15 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 3).

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

  • 2014

    Sampling-based proofs of almost-periodicity results and algorithmic applications

    Ben-Sasson, E., Ron-Zewi, N., Tulsiani, M. & Wolf, J., 2014, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings. PART 1 ed. Springer Verlag, p. 955-966 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8572 LNCS, no. PART 1).

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

    Open Access
  • 2013

    Absolutely sound testing of lifted codes

    Haramaty, E., Ron-Zewi, N. & Sudan, M., 2013, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 16th International Workshop, APPROX 2013 and 17th International Workshop, RANDOM 2013, Proceedings. p. 671-682 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8096 LNCS).

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

    Open Access
  • 2012

    A new upper bound on the query complexity for testing generalized Reed-Muller codes

    Ron-Zewi, N. & Sudan, M., 2012, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings. p. 639-650 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7408 LNCS).

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

    Open Access
  • Space complexity in polynomial calculus

    Filmus, Y., Lauria, M., Nordström, J., Thapen, N. & Ron-Zewi, N., 2012, Proceedings - 2012 IEEE 27th Conference on Computational Complexity, CCC 2012. p. 334-344 11 p. 6243410. (Proceedings of the Annual IEEE Conference on Computational Complexity).

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

    Open Access
  • 2011

    From affine to two-source extractors via approximate duality

    Ben-Sasson, E. & Zewi, N., 2011, STOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing. Association for Computing Machinery, p. 177-186 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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