נגה רון-צבי - הפקולטה למדעי המחשב והמידע

פרסומים▼

Efficient Decoding of Double-Circulant and Wozencraft Codes From Square-Root Errors, Dubin, O., Oz, N. & Ron-Zewi, N., 1 Jul 2026, In: IEEE Transactions on Information Theory. 72, 7, p. 4710-4718 9 p.
Linear Prover IOPs in Log Star Rounds, Athamnah, N., Ron-Zewi, N. & Rothblum, R. D., 2026, Theory of Cryptography - 23rd International Conference, TCC 2025, Proceedings. Applebaum, B. & Lin, H. (eds.). Springer Science and Business Media Deutschland GmbH, p. 335-368 34 p. (Lecture Notes in Computer Science; vol. 16268 LNCS).
Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead, Ron-Zewi, N. & Rothblum, R., 28 Mar 2025, In: Journal of the ACM. 72, 2, 15.
Finer-grained reductions in fine-grained hardness of approximation, Abboud, E. & Ron-Zewi, N., 12 Feb 2025, In: Theoretical Computer Science. 1026, 114976.
Preface, Kumar, A. & Ron-Zewi, N., Sep 2024, In: Leibniz International Proceedings in Informatics, LIPIcs. 317, p. XI
Preface, Kumar, A. & Ron-Zewi, N., Sep 2024, In: Leibniz International Proceedings in Informatics, LIPIcs. 317, p. XI
Preface, Kumar, A. & Ron-Zewi, N., Sep 2024, In: Leibniz International Proceedings in Informatics, LIPIcs. 317, p. XI
Finer-Grained Reductions in Fine-Grained Hardness of Approximation, Abboud, E. & Ron-Zewi, N., Jul 2024, 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024. Bringmann, K., Grohe, M., Puppis, G. & Svensson, O. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 7. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 297).
Local Proofs Approaching the Witness Length, Ron-Zewi, N. & Rothblum, R., 11 Jun 2024, In: Journal of the ACM. 71, 3, 18.
LOW-DENSITY PARITY-CHECK CODES ACHIEVE LIST-DECODING CAPACITY, Mosheiff, J., Resch, N., Ron-Zewi, N., Silas, S. & Wootters, M., 2024, In: SIAM Journal on Computing. 53, 6, p. FOCS20-38-FOCS20-73
Zero-Knowledge IOPs Approaching Witness Length, Ron-Zewi, N. & Weiss, M., 2024, Advances in Cryptology – CRYPTO 2024 - 44th Annual International Cryptology Conference, Proceedings. Reyzin, L. & Stebila, D. (eds.). Springer Science and Business Media Deutschland GmbH, p. 105-137 33 p. (Lecture Notes in Computer Science; vol. 14929 LNCS).
IMPROVED LIST DECODING OF FOLDED REED-SOLOMON AND MULTIPLICITY CODES, Kopparty, S., Ron-Zewi, N., Saraf, S. & Wootters, M., 2023, In: SIAM Journal on Computing. 52, 3, p. 794-840 47 p.
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).
Efficient List-Decoding with Constant Alphabet and List Sizes, Guo, Z. & Ron-Zewi, N., 1 Mar 2022, In: IEEE Transactions on Information Theory. 68, 3, p. 1663-1682 20 p.
From Local to Robust Testing via Agreement Testing, Dinur, I., Harsha, P., Kaufman, T. & Ron-Zewi, N., 2022, In: Theory of Computing. 18, 12.
Erasures versus errors in local decoding and property testing, Raskhodnikova, S., Ron-Zewi, N. & Varma, N., Dec 2021, In: Random Structures and Algorithms. 59, 4, p. 640-670 31 p.
Linear-Time Erasure List-Decoding of Expander Codes, Ron-Zewi, N., Wootters, M. & Zemor, G., Sep 2021, In: IEEE Transactions on Information Theory. 67, 9, p. 5827-5839 13 p., 9449885.
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).
Query complexity lower bounds for local list-decoding and hard-core predicates (Even for small rate and huge lists), Ron-Zewi, N., Shaltiel, R. & Varma, N., 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, 33. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 185).
On List Recovery of High-Rate Tensor Codes, Kopparty, S., Resch, N., Ron-Zewi, N., Saraf, S. & Silas, S., Jan 2021, In: IEEE Transactions on Information Theory. 67, 1, p. 296-316 21 p., 9195853.
Guest Editors’ Foreword, Bezáková, I., Ron-Zewi, N. & Végh, L. A., 2021, In: Theory of Computing. 17, 3.
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).
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).
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).
Locally testable codes via high-dimensional expanders, Dikstein, Y., Dinur, I., Harsha, P. & Ron-Zewi, N., 3 May 2020, p. 1-15, 15 p.
Local list recovery of high-rate tensor codes and applications, Hemenway, B., Ron-Zewi, N. & Wootters, M., 2020, In: SIAM Journal on Computing. 49, 4, p. 157-195 39 p.
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).
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).
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).
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).
Explicit Capacity Approaching Coding for Interactive Communication, Gelles, R., Haeupler, B., Kol, G., Ron-Zewi, N. & Wigderson, A., Oct 2018, In: IEEE Transactions on Information Theory. 64, 10, p. 6546-6560 15 p., 8345651.
Locally testable and locally correctable codes approaching the gilbert-varshamov bound, Gopi, S., Kopparty, S., Oliveira, R., Ron-Zewi, N. & Saraf, S., Aug 2018, In: IEEE Transactions on Information Theory. 64, 8, p. 5813-5831 19 p.
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).
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.
Sparse affine-invariant linear codes are locally testable, Ben-Sasson, E., Ron-Zewi, N. & Sudan, M., 1 Mar 2017, In: Computational Complexity. 26, 1, p. 37-77 41 p.
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).
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).
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; vol. 9615).
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).
Absolutely sound testing of lifted codes, Haramaty, E., Ron-Zewi, N. & Sudan, M., 13 Aug 2015, In: Theory of Computing. 11, p. 299-338 40 p.
From affine to two-source extractors via approximate duality, Ben-Sasson, E. & Ron-Zewi, N., 2015, In: SIAM Journal on Computing. 44, 6, p. 1670-1697 28 p.
Space complexity in polynomial calculus, Filmus, Y., Lauria, M., Nordström, J., Ron-Zewi, N. & Thapen, N., 2015, In: SIAM Journal on Computing. 44, 4, p. 1119-1153 35 p.
An additive combinatorics approach relating rank to communication complexity, Ben-Sasson, E., Lovett, S. & Ron-Zewi, N., Jul 2014, In: Journal of the ACM. 61, 4, 22.
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).
A New Upper Bound on the Query Complexity of Testing Generalized Reed-Muller Codes, Ron Zewi, N. & Sudan, M., 2013, In: Theory of Computing. 9, 25, p. 783-807 25 p.
Vector representation of graph domination, Zewi, N., 2012, In: Journal of Graph Theory. 70, 2, p. 152-170 19 p.
An additive combinatorics approach relating rank to communication complexity, Ben-Sasson, E., Lovett, S. & Ron-Zewi, N., 2012, In: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. p. 177-186 10 p., 6375295.
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).
Sparse affine-invariant linear codes are locally testable, Ben-Sasson, E., Ron-Zewi, N. & Sudan, M., 2012, In: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. p. 561-570 10 p., 6375335.
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).

תחומי מחקר▼

אלגוריתמים
סיבוכיות חישובית
תורת הצפינה

הפקולטה למדעי המחשב והמידע

אוניברסיטת חיפה

פרופ' נגה רון-צבי

פרסומים▼

תחומי מחקר▼