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...
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...
Opening Remarks and Introduction of Biology Session
Avi Wigderson, Herbert H. Maass Professor in the School of
Mathematics
Institute for Advanced Study
The Computational Universe
Leslie Valiant, Harvard University
I will continue the exposition of different derandmization
techniques for probabilistic logspace algorithms.
The material of this talk will assume only little knowledge from
the first talk.
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...
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...
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...
