Tom Gur

Postdoctoral Scholar
Department of Electrical Engineering and Computer Science
UC Berkeley

Google Scholar profile
I am a postdoc in the EECS Department at UC Berkeley, hosted by Prof. Alessandro Chiesa.
I received my PhD in computer science and mathematics from the Weizmann Institute of Science, where my advisor was Prof. Oded Goldreich.
I received my MSc, also from the Weizmann Institute of Science, under the guidance of Prof. Ran Raz, and my BSc from Tel Aviv University.
I am broadly interested in sublinear algorithms and verifiable computing,
as well as in their interplay with coding theory, complexity theory, cryptography, and combinatorics.
Program Committees: RANDOM 2018

Coding Theory (Fall 2017, UC Berkeley)
This graduate course provides an introduction to error-correcting codes, with an emphasis on codes exhibiting a robust local-to-global structure that admits sublinear-time algorithms for tasks such as local testability and local decodability.

In submission

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

Universal Locally Testable Codes
with Oded Goldreich

Journal and conference publications

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

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

An Adaptivity Hierarchy Theorem for Property Testing
with Clément Canonne
CCC 2017

Distribution Testing Lower Bounds via Reductions from Communication Complexity
with Eric Blais and Clément Canonne
CCC 2017

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
(Invited to the ICALP 2015 special issue of Information and Computation)

Strong Locally Testable Codes with Relaxed Local Decoders
with Oded Goldreich and Ilan Komargodski
CCC 2015

Non-Interactive Proofs of Proximity
with Ron Rothblum
ITCS 2015
Computational Complexity, 2016

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
Advised by Prof. Oded Goldreich

633 Soda Hall
Tom Gur
Department of Electrical Engineering and Computer Science
University of California, Berkeley
Berkeley, CA 94720