G. Rothblum

Submitted by dloring on Wed, 2015-04-15 11:56
Home Page: 
https://guyrothblum.wordpress.com/

Interactive proofs of proximity: delegating computation in sublinear time

Submitted by dloring on Wed, 2015-04-15 00:00
Author: 
G. Rothblum
S. Vadhan
A. Wigderson
Publication: 
Proceedings of Symposium on the Theory of Computing (STOC) 2013, pp. 793-802, 2013
Year: 
2013
Abstract: 
Hide Files
File: 
Journal version (pdf)

R. Meka

Submitted by dloring on Mon, 2015-03-23 11:43
Home Page: 
https://raghumeka.github.io/

A. Potechin

Submitted by dloring on Mon, 2015-03-23 11:30
Home Page: 
http://www.potechin.org/aaronpotechin/

Sum-of-squares lower bounds for planted clique

Submitted by dloring on Mon, 2015-03-23 00:00
Author: 
R. Meka
A. Potechin
A. Wigderson
Publication: 
Proceedings of the Symposium on Theory of Computing (STOC) 2015, pp. 87-96, 2015.
Year: 
2015
Hide Files
File: 
Journal version (pdf)

S. Moran

Submitted by dloring on Mon, 2015-02-23 11:33
Home Page: 
http://www.cs.technion.ac.il/~shaymrn/

Teaching and compressing for low VC-dimension

Submitted by dloring on Mon, 2015-02-23 00:00
Author: 
S. Moran
A. Shpilka
A. Wigderson
A. Yehudayoff
Publication: 
Accepted into "Journey Through Discrete Mathematics. A Tribute to Jiri Matousek"
Electronic Colloquium on Computational Complexity (ECCC) Report TR15-025, pp. 1-24, 2015.
Year: 
2015
Hide Files
File: 
Journal version (pdf)

On Randomness Extraction in ACo

Submitted by dloring on Mon, 2015-01-05 00:00
Author: 
O. Goldreich
E. Viola
A. Wigderson
Publication: 
Proceedings of the Computational Complexity Conference (CCC) 2015, pp. 601-668, 2015.
Electronic Colloquium on Computational Complexity (ECCC) Report TR15-003, pp. 1-70, 2015.
Year: 
2015
Hide Files
File: 
Journal version (pdf)

E. Abbe

Submitted by dloring on Tue, 2014-11-18 13:44
Home Page: 
https://web.math.princeton.edu/~eabbe/

Reed-Muller codes for random erasures and errors

Submitted by dloring on Tue, 2014-11-18 13:43
Author: 
E. Abbe
A. Shpilka
A. Wigderson
Publication: 
IEEE Transactions on Information Theory, vol. 61, no. 10, pp. 5229-5252, 2015.
Proceedings of the Symposium on Theory of Computing (STOC) 2015, pp. 297-306, 2015.
Year: 
2015
Hide Files
File: 
Journal version (pdf)

Pages

Subscribe to Avi Wigderson RSS