I agree that this site is using cookies. You can find further informations here.
X
Gur, Tom
23  results:
Articles (Online) X
Search for persons X
?
1

A Structural Theorem for Local Algorithms with Applications..:

Dall'Agnol, Marcel ; Gur, Tom ; Lachish, Oded
SIAM Journal on Computing.  52 (2023)  6 - p. 1413-1463 , 2023
Link: https://doi.org/10.1137/..
 
?
2

Spatial Isolation Implies Zero Knowledge Even in a Quantum ..:

Chiesa, Alessandro ; Forbes, Michael A. ; Gur, Tom.
Journal of the ACM.  69 (2022)  2 - p. 1-44 , 2022
Link: https://doi.org/10.1145/..
 
?
3

Quantum Proofs of Proximity:

Dall'Agnol, Marcel ; Gur, Tom ; Roy Moulik, Subhayan.
Quantum.  6 (2022)  - p. 834 , 2022
Link: https://doi.org/10.22331..
 
?
4

Relaxed Locally Correctable Codes with Nearly-Linear Block ..:

Chiesa, Alessandro ; Gur, Tom ; Shinkar, Igor
SIAM Journal on Computing.  51 (2022)  6 - p. 1839-1865 , 2022
Link: https://doi.org/10.1137/..
 
?
5

On the Power of Relaxed Local Decoding Algorithms:

Gur, Tom ; Lachish, Oded
SIAM Journal on Computing.  50 (2021)  2 - p. 788-813 , 2021
Link: https://doi.org/10.1137/..
 
?
6

An Exponential Separation Between MA and AM Proofs of Proxi..:

Gur, Tom ; Liu, Yang P. ; Rothblum, Ron D.
computational complexity.  30 (2021)  2 - p. , 2021
Link: https://doi.org/10.1007/..
 
?
7

Universal locally verifiable codes and 3-round interactive ..:

Goldreich, Oded ; Gur, Tom
Theoretical Computer Science.  878-879 (2021)  - p. 83-101 , 2021
Link: https://doi.org/10.1016/..
 
?
8

Distribution Testing Lower Bounds via Reductions from Commu..:

Blais, Eric ; Canonne, Clément L. ; Gur, Tom
ACM Transactions on Computation Theory.  11 (2019)  2 - p. 1-37 , 2019
Link: https://doi.org/10.1145/..
 
?
9

Strong Locally Testable Codes with Relaxed Local Decoders:

Goldreich, Oded ; Gur, Tom ; Komargodski, Ilan
ACM Transactions on Computation Theory (TOCT).  11 (2019)  3 - p. 1-38 , 2019
Link: https://dl.acm.org/doi/1..
 
?
10

Distribution Testing Lower Bounds via Reductions from Commu..:

Blais, Eric ; Canonne, Clément L. ; Gur, Tom
ACM Transactions on Computation Theory (TOCT).  11 (2019)  2 - p. 1-37 , 2019
Link: https://dl.acm.org/doi/1..
 
?
11

Strong Locally Testable Codes with Relaxed Local Decoders:

Goldreich, Oded ; Gur, Tom ; Komargodski, Ilan
ACM Transactions on Computation Theory.  11 (2019)  3 - p. 1-38 , 2019
Link: https://doi.org/10.1145/..
 
?
12

An adaptivity hierarchy theorem for property testing:

Canonne, Clément L. ; Gur, Tom
computational complexity.  27 (2018)  4 - p. 671-716 , 2018
Link: https://doi.org/10.1007/..
 
?
13

Proofs of proximity for context-free languages and read-onc..:

Goldreich, Oded ; Gur, Tom ; Rothblum, Ron D.
Information and Computation.  261 (2018)  - p. 175-201 , 2018
Link: https://doi.org/10.1016/..
 
?
14

Non-interactive proofs of proximity:

Gur, Tom ; Rothblum, Ron D.
computational complexity.  27 (2016)  1 - p. 99-207 , 2016
Link: https://doi.org/10.1007/..
 
?
15

Arthur–Merlin streaming complexity:

Gur, Tom ; Raz, Ran
Information and Computation.  243 (2015)  - p. 145-165 , 2015
Link: https://doi.org/10.1016/..
 
1-15