Proof complexity - an introduction

Submitted by sgriffin on Thu, 2020-03-19 11:48
Description: 
March 15, 2016
File: 
Video

The Resolution proof system

Submitted by sgriffin on Thu, 2020-03-19 11:17
Description: 
March 22, 2016
File: 
Video

Spanoids - an abstraction of spanning structures, and a barrier for LCCs

Submitted by sgriffin on Tue, 2020-02-11 13:56
Author: 
Z. Dvir
S. Gopi
Y. Gu
A. Wigderson
Publication: 
SIAM Journal on Computing (SICOMP) Volume 49, Issue 3, pp. 465-496 (2020)
Proceedings of the Innovations in Theoretical Computer Science (ITCS) 2019, pp. 32:1-32:20, 2019
Year: 
2020
Files
File: 
Final journal version (pdf)
Conference version (pdf)

The sum-product theorem and applications

Submitted by kphillips on Tue, 2019-06-25 17:46
Description: 
A short talk given at the Institute for Advanced Study, Princeton, New Jersey - May 31, 2019
File: 
Powerpoint

Arithmetic complexity theory: determinants, permanents and the VP vs. VNP problem

Submitted by kphillips on Tue, 2019-06-25 17:41
Description: 
A 1-hour talk given at the University of Copenhagen, København, Denmark - May 14, 2019

Optimization, Complexity and Math (through the lens of one problem and one algorithm)

Submitted by kphillips on Tue, 2019-06-25 17:36
Description: 
University of Copenhagen, København, Denmark - May 14, 2019

Complexity, Optimization and Math (or, Can we prove that P != NP by gradient descent?)

Submitted by kphillips on Tue, 2019-06-25 17:25
Description: 
A 1-hour talk given at the Fields Institute, Toronto, Ontario, Canada - May 7, 2019
File: 
Video

Optimization, Complexity and Math (through the lens of one problem and one algorithm)

Submitted by kphillips on Tue, 2019-06-25 17:16
Description: 
A 1-hour talk given at the Princeton University, Princeton, New Jersey - April 8, 2019

Pages

Subscribe to Avi Wigderson RSS