Tom Gur

Assistant Professor
Department of Computer Science
University of Warwick
United Kingdom

E-mail: tom.gur@warwick.ac.uk
Google Scholar profile
I am an assistant 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).

Before joining Warwick, I was a postdoctoral researcher at UC Berkeley, hosted by Alessandro Chiesa.
I received my PhD in computer science and mathematics from the Weizmann Institute of Science, where my advisor was Oded Goldreich.
I received my MSc, also from the Weizmann Institute of Science, under the guidance of Ran Raz, and my BSc from Tel Aviv University.
My research is in the foundations of computer science and discrete mathematics.
Specific interests include computational complexity, sublinear-time algorithms, cryptography, coding theory, quantum information, and more.

Preprints

A Lower Bound for Relaxed Locally Decodable Codes
with Oded Lachish

An Entropy Lower Bound for Non-Malleable Extractors
with Igor Shinkar

Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP
with Oded Goldreich

Journal and conference publications

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

An Exponential Separation between MA and AM Proofs of Proximity
with Yang P. Liu and Ron Rothblum
ICALP 2018

Proofs of Proximity for Distribution Testing
with Alessandro Chiesa
ITCS 2018
(Video of talk at FOCS 2017 Workshop: Frontiers in Distribution Testing)

Relaxed Locally Correctable Codes
with Govind Ramnarayan and Ron Rothblum
ITCS 2018

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 talk at ITCS)

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

Thesis

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

Email
tom.gur@warwick.ac.uk
Office
CS2.06
Address
Tom Gur
Centre for Discrete Mathematics and its Applications (DIMAP)
Department of Computer Science
University of Warwick
CV4 7AL
United Kingdom