Publications
Finer-grained Reductions in Fine-grained Hardness of Approximation
With Elie Abboud
Proceedings of the 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024).
Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead
With Ron Rothblum
In proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC 2022)
Efficient List-Decoding with Constant Alphabet and List Sizes
With Zeyu Guo
IEEE Transactions on Information Theory, Volume 68(3), pages 1663-1682, 2022.
Preliminary version in proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC 2021)
With Ronen Shaltiel and Nithin Varma
Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Local proofs approaching the witness length
With Ron Rothblum
Journal of the ACM, to appear.
Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2020)
LDPC codes achieve list decoding capacity
With Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, and Mary Wootters
SIAM Journal on Computing (SICOMP) (special issue of FOCS 2020) (to appear)
Preliminary version in proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2020)
Linear-time erasure list-decoding of expander codes
With Mary Wootters and Gilles Zemor
IEEE Transactions on Information Theory, Volume 67(9), pages 5827-5839, 2021.
Preliminary version in IEEE International Symposium on Information Theory (ISIT 2020)
On list recovery of high-rate tensor codes
With Swastik Kopparty, Nicolas Resch, Shubhangi Saraf, and Shashwat Silas
IEEE Transactions on Information Theory, Volume 67(1), pages 296-316, 2021.
Preliminary version in proceedings of the 23rd International Conference on Randomization and Computation (Random 2019)
From Local to Robust Testing via Agreement Testing
With Irit Dinur, Prahladh Harsha, and Tali Kaufman
Theory of Computing, volume 18(12), pages 1-25, 2022.
Preliminary version in proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Erasures vs. Errors in Local Decoding and Property Testing
With Sofya Raskhodnikova and Nithin Varma
Random Structures and Algorithms (RSA), volume 59(4), pages 640-670, 2021
Preliminary version in proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Improved list decoding of Folded Reed-Solomon and Multiplicity Codes
With Swastik Kopparty, Shubhangi Saraf, and Mary Wootters
SIAM Journal on Computing (SICOMP), volume 52(3), pages 794-820, 2023
Preliminary version in proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2018)
Local list recovery of high-rate tensor codes & applications
With Brett Hemenway and Mary Wootters
SIAM Journal on Computing (SICOMP), volume 49(4), pages 157-195, 2020 (special issue of FOCS 2017)
Preliminary verison in proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017)
Locally testable and locally correctable codes approaching the Gilbert-Varshamov bound
With Sivakanth Gopi, Swastik Kopparty, Rafael Oliveira and Shubhangi Saraf
IEEE Transactions on Information Theory, Volume 64(8), pages 5813-5831, 2018.
Preliminary version in proceedings of the 28h Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)
[Filmed talk at Banff (by Swastik Kopparty)], [In DIMACS Highlights (by Tami Carpenter)]
High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity
With Swastik Kopparty, Or Meir and Shubhangi Saraf
Journal of the ACM (JACM), Volume 64(2), 2017
Preliminary version in proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC 2016)
[Filmed talk at TCS+ (by Swastik Kopparty)], [In SIGACT News (by Swastik Kopparty and Shubhangi Saraf)], [In DIMACS Highlights (by Tami Carpenter)]
Towards optimal deterministic coding for interactive communication
With Ran Gelles, Bernhard Haeuplr, Gillat Kol and Avi Wigderson
IEEE Transactions on Information Theory, volume 64(10), pages 6546-6560, 2018.
Preliminary version in proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)
On public key encryption from noisy codewords
With Eli Ben-Sasson, Iddo Ben-Tov, Ivan Damgard and Yuval Ishai
Proceedings of the 19th International Conference on the Theory and Practice of Public-key Cryptography (PKC 2016)
Sampling-based proofs of almost-periodicity results and algorithmic applications
With Eli Ben-Sasson, Madhur Tulsiani and Julia Wolf
Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014).
Absolutely sound testing of lifted codes
With Elad Haramaty and Madhu Sudan
Theory of Computing, volume 11(12), pages 299-338, 2015 (Special issue of Random 2013)
Preliminary version in proceedings of the 7th International Workshop on Randomization and Computation (Random 2013)
An additive combinatorics approach relating rank to communication complexity
With Eli Ben-Sasson and Shachar Lovett
Journal of the ACM (JACM), volume 61(4), 2014
Preliminary version in proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012)
[Filmed talk at IAS, Princeton]
Sparse affine-invariant linear codes are locally testable
With Eli Ben-Sasson and Madhu Sudan
Computational Complexity, volume 26(1), pages 37-77, 2017.
Preliminary version in proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012)
A new upper bound on the query complexity of testing the generalized Reed-Muller codes
With Madhu Sudan.
Theory of Computing, volume 25(9), pages 781-807, 2013 (Special issue of Random 2012).
Preliminary version in proceedings of the 6th International Workshop on Randomization and Computaiton (Random 2012)
Space complexity in polynomial calculus
With Yuval Filmus, Massimo Lauria, Jakob Nordstrom and Neil Thapen
SIAM Journal of computing (SICOMP), volume 44(4), pages 889-1172, 2015
Preliminary version in proceedings of the 27th IEEE Conference on Computational Complexity (CCC 2012)
From affine to two-source extractors via approximate duality
With Eli Ben-Sasson.
SIAM Journal of Computing (SICOMP), volume 44(6), pages 1670-1695, 2015
Preliminary version in proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC 2011).
Manuscripts
Locally testable codes via high-dimensional expanders
With Yotam Dikstein, Irit Dinur and Prahladh Harsha
Simple Constructions of Unique Neighbor Expanders from Error-correcting Codes
With Swastik Kopparty and Shubhangi Saraf
Submitted
Ph.D. Thesis
Additive combinatorics methods in computational complexity
Ph.D. Thesis, Technion, 2014.