Avi Wigderson

Avi Wigderson

More on sum-of-squares proofs for planted clique

Avi Wigderson
Herbert H. Maass Professor, School of Mathematics
December 9, 2014

While this talk is a continuation of the one I gave on Tue Nov 25, it will be planned as an independent one. I will not assume knowledge from that talk, and will reintroduce that is needed. (That first lecture gave plenty of background material, and anyone interested can watch it on https://video.ias.edu/csdm/2014/1125-AviWigderson).

Sum-of-squares lower bounds for the planted clique problem

Avi Wigderson
Herbert H. Maass Professor, School of Mathematics
November 25, 2014
Finding large cliques in random graphs and the closely related "planted" clique variant, where a clique of size \(k\) is planted in a random \(G(n,1/2)\) graph, have been the focus of substantial study in algorithm design. Despite much effort, the best known polynomial-time algorithms only solve the problem for \(k = \Theta(\sqrt{n})\). In this paper we study the complexity of the planted clique problem under algorithms from the Sum-Of-Squares hierarchy.

Derandomizing BPL?

Avi Wigderson
School of Mathematics, Institute for Advanced Study
February 26, 2013

I will survey some of the basic approaches to derandomizing Probabilistic Logspace computations, including the "classical" Nisan, Impagliazzo-Nisan-Widgerson and Reingold-Raz generators, the Saks-Zhou algorithm and some more recent approaches. We'll see why each falls short of complete derandomization, BPL=L, hopefully motivating further work on this basic problem.

Local Correction of Codes and Euclidean Incidence Geometry

Avi Wigderson
Institute for Advanced Study
March 5, 2012

A classical theorem in Euclidean geometry asserts that if a set of points has the property that every line through two of them contains a third point, then they must all be on the same line. We prove several approximate versions of this theorem (and related ones), which are motivated from questions about locally correctable codes and matrix rigidity. The proofs use an interesting combination of combinatorial, algebraic and analytic tools.

Joint work with Boaz Barak, Zeev Dvir and Amir Yehudayoff

CSDM: A Survey of Lower Bounds for the Resolution Proof System

Avi Wigderson
Herbert H. Maass Professor, School of Mathematics, Institute for Advanced Study
January 31, 2012
The Resolution proof system is among the most basic and popular for proving propositional tautologies, and underlies many of the automated theorem proving systems in use today. I'll start by defining the Resolution system, and its place in the proof-complexity picture.