skip to content

Department of Computer Science and Technology

  • Associate Professor

About Me

I am an Associate 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 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, Algorithms, Coding TheoryCryptography, Learning Theory, and their interplay with Harmonic Analysis, Probability Theory, and Additive Combinatorics.

 

My Research Group

I am fortunate to supervise the following PhD Students and Postdocs.

Current

Alumni

 

Teaching

On Easter Term 2023/24, I will teach Complexity Theory for Part IB students.
On Michaelmas Term 2024/25, I will teach Quantum Algorithms and Complexity for Part III students.

Courses I have taught in the past include Coding Theory, Property Testing, Probabilistic Proofs, and Quantum Computing.

 

Selected Recent Publications

Perfect Zero-Knowledge PCPs for #P
with Jack O'Connor and Nicholas Spooner 
STOC 2024

On the Power of Interactive Proofs for Learning
with Mohammad Jahanara, Mohammad Khodabandeh, Ninad Rajgopal, Bahar Salamatian, and Igor Shinkar
STOC 2024

Quantum Worst-Case to Average-Case Reductions for All Linear Problems
with Vahid R. Asadi, Alexander Golovnev, Igor Shinkar, and Sathyawageeswar Subramanian
QIP 2023

Worst-Case to Average-Case Reductions via Additive Combinatorics
with Vahid R. Asadi, Alexander Golovnev, and Igor Shinkar
STOC 2022

Hypercontractivity on High Dimensional Expanders
with Noam Lifshitz and Siqi Liu
STOC 2022

Spatial Isolation Implies Zero Knowledge Even in a Quantum World
with Alessandro Chiesa, Michael Forbes, and Nicholas Spooner
Journal of the ACM, 2022

Quantum Learning Algorithms Imply Circuit Lower Bounds
with Srinivasan Arunachalam, Alex B. Grilo, Igor C. Oliveira, and Aarthi Sundaram
FOCS 2021

On the Power of Relaxed Local Decoding Algorithms
with Oded Lachish
SIAM Journal on Computing, 2021

 

Publications

Perfect Zero-Knowledge PCPs for #P
with Jack O'Connor and Nicholas Spooner 
STOC 2024

On the Power of Interactive Proofs for Learning
with Mohammad Jahanara, Mohammad Khodabandeh, Ninad Rajgopal, Bahar Salamatian, and Igor Shinkar
STOC 2024

Provable Advantage in Quantum PAC Learning
with Wilfred Salmon and Sergii Strelchuk
COLT 2024
TQC 2024

Information-Theoretic Generalization Bounds for Learning From Quantum Data
with Matthias Caro, Cambyse Rouzé, Daniel Stilck França, and Sathyawageeswar Subramanian
COLT 2024
TQC 2024

Streaming Zero-Knowledge Proofs
with Graham Cormode, Marcel Dall'Agnol, and Chris Hickey
CCC 2024

Distribution-Free Proofs of Proximity
with Hugo Aaronson, Ninad Rajgopal, and Ron D. Rothblum 
CCC 2024

High-precision and low-depth eigenstate property estimation
with Jinzhao Sun, Pei Zeng, and M. S. Kim
Preprint, 2024

Quantum Worst-Case to Average-Case Reductions for All Linear Problems
with Vahid R. Asadi, Alexander Golovnev, Igor Shinkar, and Sathyawageeswar Subramanian
QIP 2023
SODA 2024
(Video of Vahid's QIP talk)

Proof-Carrying Data From Arithmetized Random Oracles
with Megan Chen, Alessandro Chiesa, Jack O'Connor, and Nicholas Spooner
Eurocrypt 2023
(Video of Jack's Eurocrypt talk)

Derandomization of Cell Sampling
with Alexander Golovnev and Igor Shinkar
SOSA 2023

Worst-Case to Average-Case Reductions via Additive Combinatorics
with Vahid R. Asadi, Alexander Golovnev, and Igor Shinkar
STOC 2022
(Video of Vahid's STOC talk)

Hypercontractivity on High Dimensional Expanders
with Noam Lifshitz and Siqi Liu
STOC 2022
(Video of Siqi's STOC talk)

Sublinear Quantum Algorithms for Estimating von Neumann Entropy
with Min-Hsiu Hsieh and Sathyawageeswar Subramanian
QIP 2022
(Video of Sathya's QIP talk)

Quantum Learning Algorithms Imply Circuit Lower Bounds
with Srinivasan Arunachalam, Alex B. Grilo, Igor C. Oliveira, and Aarthi Sundaram
FOCS 2021
QIP 2021
(Video of my QIP talk)

Quantum Proofs of Proximity
with Marcel Dall'Agnol, Subhayan Roy Moulik, and 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
with Marcel Dall'Agnol and 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
with Oded Goldreich
Theoretical Computer Science, 2021

On the Power of Relaxed Local Decoding Algorithms
with 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
with Alessandro Chiesa and Igor Shinkar
SODA 2020
SIAM Journal on Computing, 2022

An Entropy Lower Bound for Non-Malleable Extractors
with Igor Shinkar
IEEE Transactions on Information Theory, 2020

Linear-Size Constant-Query IOPs for Delegating Computation
with Eli Ben-Sasson, Alessandro Chiesa, Lior Goldberg, Michael Riabzev, and Nicholas Spooner
TCC 2019

Every Set in P Is Strongly Testable under a Suitable Encoding
with Irit Dinur and Oded Goldreich
ITCS 2019

Spatial Isolation Implies Zero Knowledge Even in a Quantum World
with Alessandro Chiesa, Michael Forbes, and Nicholas Spooner
FOCS 2018
QIP 2019
Journal of the ACM, 2022

An Exponential Separation between MA and AM Proofs of Proximity
with Yang P. Liu and Ron D. Rothblum
ICALP 2018
Computational Complexity, 2021

Proofs of Proximity for Distribution Testing
with Alessandro Chiesa
ITCS 2018
(Video of my FOCS 2017 Workshop talk)

Relaxed Locally Correctable Codes
with Govind Ramnarayan and Ron D. Rothblum
ITCS 2018
Theory of Computing, 2020

Universal Locally Testable Codes
with Oded Goldreich
Chicago Journal of Theoretical Computer Science, 2018

An Adaptivity Hierarchy Theorem for Property Testing
with Clément Canonne
CCC 2017
Computational Complexity, 2018

Distribution Testing Lower Bounds via Reductions from Communication Complexity
with Eric Blais and Clément Canonne
CCC 2017
ACM Transactions on Computation Theory, 2019

A Hierarchy Theorem for Interactive Proofs of Proximity
with Ron D. Rothblum
ITCS 2017
(Video of my ITCS talk)

Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs
with Oded Goldreich and Ron D. Rothblum
ICALP 2015
Information and Computation, 2018 (special issue for ICALP 2015)

Strong Locally Testable Codes with Relaxed Local Decoders
with Oded Goldreich and Ilan Komargodski
CCC 2015
ACM Transactions on Computation Theory, 2019

Non-Interactive Proofs of Proximity
with Ron D. Rothblum
ITCS 2015
Computational Complexity, 2018

Arthur-Merlin Streaming Complexity
with Ran Raz
ICALP 2013
Information and Computation, 2015 (special issue for ICALP 2013)

Testing Booleanity and the Uncertainty Principle
with Omer Tamuz
Chicago Journal of Theoretical Computer Science, 2013

Leveraging Genetic Variability across Populations for the Identification of Causal Variant
with Noah Zaitlen, Bogdan Pasaniuc, Elad Ziv, and Eran Halperin
American Journal of Human Genetics, 2010

A Generic Coalescent-Based Framework for the Selection of a Reference Panel for Imputation
with Bogdan Pasaniuc, Ram Avinery, Christine F. Skibola, Paige M. Bracci, and Eran Halperin
Genetic Epidemiology, 2010

Thesis

On Locally Verifiable Proofs of Proximity
PhD Thesis, 2017
Supervised by Oded Goldreich

 

Selected Professional Activities

Contact Details

Room: 
FC10
Email: 

tom.gur@cl.cam.ac.uk