2023

Chen, Megan, Chiesa, Alessandro, Gur, Tom, O’Connor, Jack and Spooner, Nicholas (2023) Proof-carrying data from arithmetized random oracles. In: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, 23–27 Apr 2023. Published in: Advances in Cryptology – EUROCRYPT 2023, 14005 pp. 379-404. ISBN 9783031306167. doi:10.1007/978-3-031-30617-4_13 ISSN 0302-9743.

Golonev, Alexander, Gur, Tom and Shinkar, Igor (2023) Derandomization of cell sampling. In: SIAM Symposium on Simplicity in Algorithms (SOSA23), Florence, Italy, 23-25 Jan 2023. Published in: Proceedings of the SIAM Symposium on Simplicity in Algorithms (SOSA23) (In Press)

2022

Dall'Agnol, Marcel, Gur, Tom, Moulik, Subhayan Roy and Thaler, Justin (2022) Quantum proofs of proximity. Quantum, 6 . 834. doi:10.22331/q-2022-10-13-834

Gur, Tom, Lifshitz, Noam and Liu, Siqi (2022) Hypercontractivity on high dimensional expanders. In: The 54th ACM Symposium on Theory of Computing (STOC 2022), Rome, Italy, 20-24 Jun 2022. Published in: STOC 2022 : Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing pp. 176-184. ISBN 9781450392648. doi:10.1145/3519935.3520004

Asadi, Vahid R., Golovnev, Alexander, Gur, Tom and Shinkar, Igor (2022) Worst-case to average-case reductions via additive combinatorics. In: The 54th ACM Symposium on Theory of Computing (STOC 2022), Rome, Italy, 20-24 Jun 2022. Published in: STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing pp. 1566-1574. ISBN 9781450392648. doi:10.1145/3519935.3520041

Chiesa, Alessandro, Forbes, Michael, Gur, Tom and Spooner, Nicholas (2022) Spatial isolation implies zero knowledge even in a quantum world. Journal of the ACM, 69 (2). 15. doi:10.1145/3511100 ISSN 0004-5411.

2021

Gur, Tom and Lachish, Oded (2021) On the power of relaxed local decoding algorithms. SIAM Journal on Computing, 50 (2). pp. 788-813. doi:10.1137/19M1307834 ISSN 0097-5397.

Arunachalam, Srinivasan, Grilo, Alex B., Gur, Tom, Carboni Oliveira, Igor and Sundaram, Aarthi (2021) Quantum learning algorithms imply circuit lower bounds. In: The 62nd Annual Symposium on Foundations of Computer Science (FOCS 2021), Denver, Colorado, 7-10 Feb 2022. Published in: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) doi:10.1109/FOCS52979.2021.00062 ISSN 2575-8454.

Dall'Agnol, Marcel, Gur, Tom, Wajc, David and Lachish, Oded (2021) A structural theorem for local algorithms with applications to testing, coding, and privacy. In: ACM-SIAM Symposium on Discrete Algorithms (SODA21), Virtual, 10-13 Jan 2021. Published in: SODA '21: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms pp. 1651-1665. ISBN 9781611976465. doi:10.5555/3458064.3458164

Chiesa, Alessandro, Gur, Tom and Shinkar, Igor (2021) Relaxed locally correctable codes with nearly-linear block length and constant query complexity. SIAM Journal of Computing . pp. 1395-1411. doi:10.1137/1.9781611975994.84 ISSN 0097-5397.

2020

Gur, Tom and Shinkar, Igor (2020) An entropy lower bound for non-malleable extractors. IEEE Transactions on Information Theory, 66 (5). pp. 2904-2911. doi:10.1109/TIT.2019.2946896 ISSN 0018-9448.

Gur, Tom and Lachish, Oded (2020) On the power of relaxed local decoding algorithms. In: 31st ACM-SIAM Symposium on Discrete Algorithms (SODA20), Salt Lake City, Utah, U.S., 5-8 Jan 2020. Published in: Proceedings of ACM-SIAM Symposium on Discrete Algorithms pp. 1377-1394. doi:10.5555/3381089.3381172

Chiesa, Alessandro, Gur, Tom and Shinkar, Igor (2020) Relaxed locally correctable codes with nearly-linear block length and constant query complexity. In: 31st ACM-SIAM Symposium on Discrete Algorithms (SODA20), Salt Lake City, Utah, U.S., 5-8 Jan 2020. Published in: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA) 1395-1411 . ISBN 9781611975994. doi:10.1137/1.9781611975994.84

2019

Ben-Sasson, Eli, Chiesa, Alessandro, Goldberg, Lior, Gur, Tom, Riabzev, Michael and Spooner, Nicholas (2019) Linear-size constant-query IOPs for delegating computation. In: The Seventeenth Theory of Cryptography Conference (TCC 2019), Nuremberg, Germany, 1-5 Dec 2019. Published in: Theory of Cryptography. TCC 2019, 11892 pp. 494-521. ISBN 9783030360320. doi:10.1007/978-3-030-36033-7_19

Goldreich, Oded, Gur, Tom and Komargodski, Ilan (2019) Strong locally testable codes with relaxed local decoders. ACM Transactions on Computation Theory, 11 (3). pp. 1-38. doi:10.1145/3319907 ISSN 1942-3454.

Blais, Eric, Canonne, Clément L. and Gur, Tom (2019) Distribution testing lower bounds via reductions from communication complexity. ACM Transactions on Computation Theory, 11 (2). pp. 1-37. 6. doi:10.1145/3305270 ISSN 1942-3454.

Dinur, Irit, Goldreich, Oded and Gur, Tom (2019) Every set in P is strongly testable under a suitable encoding. In: 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Published in: 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), 124 30:1-30:17. ISBN 9783959770958. doi:10.4230/LIPIcs.ITCS.2019.30 ISSN 1868-8969.

2018

Canonne, Clément L. and Gur, Tom (2018) An adaptivity hierarchy theorem for property testing. computational complexity, 27 (4). pp. 671-716. doi:10.1007/s00037-018-0168-4 ISSN 1016-3328.

Gur, Tom, Liu, Yang P. and Rothblum, Ron (2018) An exponential separation between MA and AM proofs of proximity. In: The 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague, Czech Republic, 9-13 Jul 2018. Published in: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), 107 73:1-73:15. ISBN 9783959770767. doi:10.4230/LIPIcs.ICALP.2018.73 ISSN 1868-8969.

Gur, Tom and Rothblum, Ron D. (2018) Non-interactive proofs of proximity. Computational Complexity, 27 (1). pp. 99-207. doi:10.1007/s00037-016-0136-9 ISSN 1016-3328.

Chiesa, Alessandro and Gur, Tom (2018) Proofs of proximity for distribution testing. In: 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Published in: 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), 94 53:1-53:14. ISBN 9783959770606. doi:10.4230/LIPIcs.ITCS.2018.53 ISSN 1868-8969.

Gur, Tom, Ramnarayan, Govind and Rothblum, Ron D. (2018) Relaxed locally correctable codes. In: 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Published in: 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), 94 27:1-27:11. ISBN 9783959770606. doi:10.4230/LIPIcs.ITCS.2018.27 ISSN 1868-8969.

Chiesa, Alessandro, Forbes, Michael, Gur, Tom and Spooner, Nicholas (2018) Spatial isolation implies zero knowledge even in a quantum world. In: 59th Annual IEEE Symposium on Foundations of Computer Science, Paris, France, 7-9 Oct 2018. Published in: 59th Annual IEEE Symposium on Foundations of Computer Science pp. 755-765. ISBN 9781538642306. doi:10.1109/FOCS.2018.00077 ISSN 1523-8288.

2017

Blais, Eric, Canonne, Clément L. and Gur, Tom (2017) Distribution testing lower bounds via reductions from communication complexity. In: 32nd Computational Complexity Conference (CCC 2017). Published in: 32nd Computational Complexity Conference (CCC 2017), 79 28:1-28:40. ISBN 9783959770408. doi:10.4230/LIPIcs.CCC.2017.28 ISSN 1868-8969.

Canonne, Clément L. and Gur, Tom (2017) An adaptivity hierarchy theorem for property testing. In: 32nd Computational Complexity Conference (CCC 2017). Published in: 32nd Computational Complexity Conference (CCC 2017, 79 27:1-27:25. ISBN 9783959770408. doi:10.4230/LIPIcs.CCC.2017.27 ISSN 1868-8969.

Gur, Tom and Rothblum, Ron D. (2017) A hierarchy theorem for interactive proofs of proximity. In: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Published in: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), 67 39:1-39:43. ISBN 9783959770293. doi:10.4230/LIPIcs.ITCS.2017.39 ISSN 1868-8969.

2015

Goldreich, Oded, Gur, Tom and Rothblum, Ron D. (2015) Proofs of proximity for context-free languages and read-once branching programs. In: The 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), Kyoto, Japan, 6-10 Jul 2015. Published in: Automata, Languages, and Programming. ICALP 2015, 9134 pp. 666-677. ISBN 9783662476710. doi:10.1007/978-3-662-47672-7_54 ISSN 0302-9743.

Goldreich, Oded, Gur, Tom and Komargodski , Ilan (2015) Strong locally testable codes with relaxed local decoders. In: 30th Conference on Computational Complexity (CCC’15). Published in: 30th Conference on Computational Complexity (CCC 2015), 33 pp. 1-41. doi:10.4230/LIPIcs.CCC.2015.1