Tom Gur

Associate Professor
Department of Computer Science
University of Warwick
United Kingdom

Google Scholar profile
Twitter account
I am an associate professor in the Department of Computer Science at the University of Warwick.
I am a member of the Division of Theory and Foundations and the Centre for Discrete Mathematics and its Applications (DIMAP).
My research is supported by a UKRI Future Leaders Fellowship.

Prior to joining Warwick, I was a postdoctoral researcher at UC Berkeley.
I received my PhD from the Weizmann Institute of Science, where my advisor was Oded Goldreich.
My research is primarily in the foundations of computer science and combinatorics.
Specific interests include algorithms, complexity theory, coding theory, cryptography, quantum computing, and more.
Marcel Dall'Agnol (PhD student)
Hugo Aaronson (PhD student)
Jack O'Connor (MSc student)

Prospective students and postdocs: I am interested to hear from potential PhD students and postdocs with a strong TCS/maths background.
If our research interests intersect and you would like to work with me, feel free to drop me a line.

Quantum Computing
This module provides an introduction to quantum computing, focusing on the design and analysis of quantum algorithms, as well as covering topics in quantum information and quantum cryptography.
(Anonymous feedback form for CS419)
Quantum Proofs of Proximity
with Marcel Dall'Agnol, Subhayan Roy Moulik, and Justin Thaler
TQC 2021
(Video of Marcel's TQC talk)

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

A Structural Theorem for Local Algorithms with Applications to Testing, Coding, and Privacy
with Marcel Dall'Agnol and Oded Lachish
SODA 2021
(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, 2021 (to appear)

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
Presented at QIP 2019
Journal of the ACM, 2021 (to appear)

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

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 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 Clement Canonne
CCC 2017
Computational Complexity, 2018

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

A Hierarchy Theorem for Interactive Proofs of Proximity
with Ron 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 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 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


On Locally Verifiable Proofs of Proximity
PhD Thesis
Weizmann Institute of Science, 2017


MSRI Summer School on Foundations and Frontiers of Probabilistic Proofs, Summer 2021 (co-teaching with Alessandro Chiesa)
FOCS 2020 Tutorial on Relaxed Locally Decodable Codes (with Igor Shinkar)
Algorithms UK, September 2019 (co-organised with Artur Czumaj and Graham Cormode)
DIMAP Workshop, May 2019 (co-organised with Vadim Lozin)

Program Committees

ITCS 2020 (the 11th Innovations in Theoretical Computer Science Conference)
RANDOM 2018 (the 22nd International Workshop on Randomization and Computation)
Tom Gur
Centre for Discrete Mathematics and its Applications (DIMAP)
Department of Computer Science
University of Warwick
United Kingdom