- Professor of Computer Science
About Me
I am a Professor in the Department of Computer Science and Technology at the University of Cambridge.
I am a member of the Algorithms and Complexity and Quantum Computing groups.
My research is supported by an ERC Starting Grant, a UKRI Future Leaders Fellowship, an EPSRC New Horizons Grant, and an EPSRC Robust and Reliable Quantum Computing Grant.
Research Interests
I am particularly interested in Classical and Quantum Complexity Theory, Sublinear Algorithms, Coding Theory, Cryptography, Learning Theory, and their interplay with Harmonic Analysis and Additive Combinatorics.
My Research Group
I am fortunate to supervise the following PhD Students and Postdocs.
Current
- Hugo Aaronson (PhD Student)
- Gaia Carenini (PhD Student; co-supervising with Mateja Jamnik)
- Davi Castro-Silva (Postdoc; co-supervising with Anuj Dawar and Sergii Strelchuk)
- Aditya Jain (Postdoc)
- Jack O'Connor (PhD Student)
- Gregory Rosenthal (Postdoc; co-supervising with Animesh Datta)
- Victor Seixas Souza (Postdoc)
- Sathyawageeswar Subramanian (Postdoc)
Alumni
- Marcel Dall'Agnol (PhD Student → Lecturer at Princeton)
- Ninad Rajgopal (Postdoc → Postdoc at Charles University)
- Jinzhao Sun (Postdoc → Postdoc at Oxford)
Prospective students and postdocs. I am always interested in hearing from potential PhD students and postdocs. Strong candidates are welcome to email me.
Teaching
- Quantum Algorithms and Complexity, Michaelmas Term 2024/25
- Complexity Theory, Easter Term 2024/25
Courses I taught in the past include Complexity Theory, Coding Theory, Property Testing, Probabilistic Proofs, and Quantum Computing.
Seminars
Selected Recent Publications
Quantum Communication Advantage in TFNP
Mika Göös, Tom Gur, Siddhartha Jain, Jiawei Li
QIP 2025
Perfect Zero-Knowledge PCPs for #P
Tom Gur, Jack O'Connor, Nicholas Spooner
STOC 2024
(Featured in Quanta Magazine)
On the Power of Interactive Proofs for Learning
Tom Gur, Mohammad Jahanara, Mohammad Khodabandeh, Ninad Rajgopal, Bahar Salamatian, Igor Shinkar
STOC 2024
Quantum Worst-Case to Average-Case Reductions for All Linear Problems
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian
QIP 2023
Worst-Case to Average-Case Reductions via Additive Combinatorics
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar
STOC 2022
Hypercontractivity on High Dimensional Expanders
Tom Gur, Noam Lifshitz, Siqi Liu
STOC 2022
Spatial Isolation Implies Zero Knowledge Even in a Quantum World
Alessandro Chiesa, Michael Forbes, Tom Gur, Nicholas Spooner
Journal of the ACM, 2022
Quantum Learning Algorithms Imply Circuit Lower Bounds
Srinivasan Arunachalam, Alex B. Grilo, Tom Gur, Igor C. Oliveira, Aarthi Sundaram
FOCS 2021
On the Power of Relaxed Local Decoding Algorithms
Tom Gur, Oded Lachish
SIAM Journal on Computing, 2021
Publications
A Zero-Knowledge PCP Theorem
Tom Gur, Jack O'Connor, Nicholas Spooner
Preprint
Quantum Channel Testing in Average-Case Distance
Hugo Aaronson, Gregory Rosenthal, Sathyawageeswar Subramanian, Animesh Datta, Tom Gur
Preprint
Quantum Communication Advantage in TFNP
Mika Göös, Tom Gur, Siddhartha Jain, Jiawei Li
QIP 2025
Perfect Zero-Knowledge PCPs for #P
Tom Gur, Jack O'Connor, Nicholas Spooner
STOC 2024
(Featured in Quanta Magazine)
On the Power of Interactive Proofs for Learning
Tom Gur, Mohammad Jahanara, Mohammad Khodabandeh, Ninad Rajgopal, Bahar Salamatian, Igor Shinkar
STOC 2024
Provable Advantage in Quantum PAC Learning
Wilfred Salmon, Sergii Strelchuk, Tom Gur
COLT 2024
TQC 2024
Information-Theoretic Generalization Bounds for Learning From Quantum Data
Matthias Caro, Tom Gur, Cambyse Rouzé, Daniel Stilck França, Sathyawageeswar Subramanian
COLT 2024
TQC 2024
Streaming Zero-Knowledge Proofs
Graham Cormode, Marcel Dall'Agnol, Tom Gur, Chris Hickey
CCC 2024
Distribution-Free Proofs of Proximity
Hugo Aaronson, Tom Gur, Ninad Rajgopal, Ron D. Rothblum
CCC 2024
High-precision and low-depth eigenstate property estimation
Jinzhao Sun, Pei Zeng, Tom Gur, M. S. Kim
Preprint, 2024
Quantum Worst-Case to Average-Case Reductions for All Linear Problems
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian
QIP 2023
SODA 2024
(Video of Vahid's QIP talk)
Proof-Carrying Data From Arithmetized Random Oracles
Megan Chen, Alessandro Chiesa, Tom Gur, Jack O'Connor, Nicholas Spooner
Eurocrypt 2023
(Video of Jack's Eurocrypt talk)
Derandomization of Cell Sampling
Alexander Golovnev, Tom Gur, Igor Shinkar
SOSA 2023
Worst-Case to Average-Case Reductions via Additive Combinatorics
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar
STOC 2022
(Video of Vahid's STOC talk)
Hypercontractivity on High Dimensional Expanders
Tom Gur, Noam Lifshitz, Siqi Liu
STOC 2022
(Video of Siqi's STOC talk)
Sublinear Quantum Algorithms for Estimating von Neumann Entropy
Tom Gur, Min-Hsiu Hsieh, Sathyawageeswar Subramanian
QIP 2022
(Video of Sathya's QIP talk)
Quantum Learning Algorithms Imply Circuit Lower Bounds
Srinivasan Arunachalam, Alex B. Grilo, Tom Gur, Igor C. Oliveira, Aarthi Sundaram
FOCS 2021
QIP 2021
(Video of my QIP talk)
Quantum Proofs of Proximity
Marcel Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler
TQC 2021
Quantum, 2022
(Video of Marcel's TQC talk)
A Structural Theorem for Local Algorithms with Applications to Testing, Coding, and Privacy
Marcel Dall'Agnol, Tom Gur, Oded Lachish
SODA 2021
SIAM Journal on Computing, 2023
(Video of Marcel's SODA talk)
Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP
Oded Goldreich, Tom Gur
Theoretical Computer Science, 2021
On the Power of Relaxed Local Decoding Algorithms
Tom Gur, Oded Lachish
SODA 2020
SIAM Journal on Computing, 2021
(Videos of my FOCS 2020 Tutorial)
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
Alessandro Chiesa, Tom Gur, Igor Shinkar
SODA 2020
SIAM Journal on Computing, 2022
An Entropy Lower Bound for Non-Malleable Extractors
Tom Gur, Igor Shinkar
IEEE Transactions on Information Theory, 2020
Linear-Size Constant-Query IOPs for Delegating Computation
Eli Ben-Sasson, Alessandro Chiesa, Lior Goldberg, Tom Gur, Michael Riabzev, Nicholas Spooner
TCC 2019
Every Set in P Is Strongly Testable under a Suitable Encoding
Irit Dinur, Tom Gur, Oded Goldreich
ITCS 2019
Spatial Isolation Implies Zero Knowledge Even in a Quantum World
Alessandro Chiesa, Michael Forbes, Tom Gur, Nicholas Spooner
FOCS 2018
QIP 2019
Journal of the ACM, 2022
An Exponential Separation between MA and AM Proofs of Proximity
Tom Gur, Yang P. Liu, Ron D. Rothblum
ICALP 2018
Computational Complexity, 2021
Proofs of Proximity for Distribution Testing
Alessandro Chiesa, Tom Gur
ITCS 2018
(Video of my FOCS 2017 Workshop talk)
Relaxed Locally Correctable Codes
Tom Gur, Govind Ramnarayan, Ron D. Rothblum
ITCS 2018
Theory of Computing, 2020
Universal Locally Testable Codes
Oded Goldreich, Tom Gur
Chicago Journal of Theoretical Computer Science, 2018
An Adaptivity Hierarchy Theorem for Property Testing
Clément Canonne, Tom Gur
CCC 2017
Computational Complexity, 2018
Distribution Testing Lower Bounds via Reductions from Communication Complexity
Eric Blais, Clément Canonne, Tom Gur
CCC 2017
ACM Transactions on Computation Theory, 2019
A Hierarchy Theorem for Interactive Proofs of Proximity
Tom Gur, Ron D. Rothblum
ITCS 2017
(Video of my ITCS talk)
Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs
Oded Goldreich, Tom Gur, Ron D. Rothblum
ICALP 2015
Information and Computation, 2018 (special issue for ICALP 2015)
Strong Locally Testable Codes with Relaxed Local Decoders
Oded Goldreich, Tom Gur, Ilan Komargodski
CCC 2015
ACM Transactions on Computation Theory, 2019
Non-Interactive Proofs of Proximity
Tom Gur, Ron D. Rothblum
ITCS 2015
Computational Complexity, 2018
Arthur-Merlin Streaming Complexity
Tom Gur, Ran Raz
ICALP 2013
Information and Computation, 2015 (special issue for ICALP 2013)
Testing Booleanity and the Uncertainty Principle
Tom Gur, Omer Tamuz
Chicago Journal of Theoretical Computer Science, 2013
Leveraging Genetic Variability across Populations for the Identification of Causal Variant
Noah Zaitlen, Bogdan Pasaniuc, Tom Gur, Elad Ziv, Eran Halperin
American Journal of Human Genetics, 2010
A Generic Coalescent-Based Framework for the Selection of a Reference Panel for Imputation
Bogdan Pasaniuc, Ram Avinery, Tom Gur, Christine F. Skibola, Paige M. Bracci, Eran Halperin
Genetic Epidemiology, 2010
Thesis
On Locally Verifiable Proofs of Proximity
PhD Thesis, 2017
Supervised by Oded Goldreich
Selected Professional Activities
- PC member at SODA 2025
- Founding board member of the International Association for Quantum Information (IAQI), 2024-Present
- Editor of SICOMP Special Issue for STOC 2024
- PC member at STOC 2024
- PC member at TQC 2024
- PC member at RANDOM 2024
- Organising the Cambridge Algorithms and Complexity Workshop, 2024 (with Anuj Dawar, Thomas Sauerwald)
- Associate Editor-in-Chief of the Chicago Journal of Theoretical Computer Science, 2023-Present
- Local chair of CCC 2023
- Editor for Quantum, 2022-Present
- Organising the Cambridge-Warwick Quantum Computing Colloquium, 2022-Present (with Sergii Strelchuk)
- Organised a STOC 2022 Workshop on Quantum Proofs (with Alessandro Chiesa, Dakshita Khurana, Giulio Malavolta, Thomas Vidick).
- PC member at FSTTCS 2022
- Lead diversity and inclusivity advisor for CCC, 2022-Present
- Organised the DIMAP Theory Day 2022 (with Artur Czumaj and Ramanujan Sridharan)
- Organised and taught a Graduate School on Probabilistic Proofs at Berkeley MSRI, 2021 (with Alessandro Chiesa)
- Member of the EPSRC Peer Review College, 2021-Present
- Member of the UKRI Talent Peer Review College, 2021-Present
- Lead diversity and inclusivity advisor for STOC, 2021-Present
- Editor for CRC Press, 2021-2023
- PC member at ITCS 2020
- Organised and taught a FOCS 2020 Tutorial on Relaxed Locally Decodable Codes (with Igor Shinkar)
- Group leader at the SIGACT Visioning Workshop, 2020
- Organised the Algorithms UK Workshop, 2019 (with Artur Czumaj and Graham Cormode)
- Organised the DIMAP Workshop 2019 (with Vadim Lozin)
- PC member at RANDOM 2018
