Subjects in Theoretical Computer Science
|
Fourier analysis has found many applications in Theoretical Computer Science in recent years. In this presentation I try to provide the basics of the method: convolution, the Fourier transform, the Fourier spectrum, polynomials, juntas, influences, noise sensitivity/stability etc. The presentation also includes more advanced theorems that are used in hardness of approximation, like the [MOO05] isoperimetric inequality. It is meant for people who saw Fourier analysis being applied before, but do not necessarily master it. The presentation was given
at the DIMACS Tutorial
on Limits of Approximation Algorithms: PCPs and Unique Games.
|
|
|
Introduction to PCP and Hardness of Approximation. The PCP (Probabilistically Checkable Proofs) Theorem and its connection to hardness of approximation were among the greatest discoveries of Theoretical Computer Science in the 1980’s-2000’s. In this presentation I try to start from the beginning, and provide the observations that one needs in order to appreciate this discovery. I discuss the 1991 discovery by [FGLSS91] of the PCP/hardness of approximation equivalence, the proof of the PCP Theorem by [AS92,ALMSS92], building upon substantial work from the 1980’s, the [BGS95] scheme for hardness of approximation and the Håstad analysis [H97], the Unique Games Conjecture by [Khot02]. I also mention the proof of the Parallel Repetition Theorem [Raz94], the combinatorial proof by [Dinur05], the low error Label Cover construction by [M-Raz08], and the SDP UGC-hardness of Constraint Satisfaction Problems by [Raghavendra08]. Not discussed: the connection to metric embeddings and Geometry by [Khot-Vishnoi,05]. The presentation was given
at the DIMACS Tutorial
on Limits of Approximation Algorithms: PCPs and Unique Games. More
material, including references, can be found here and here.
|
|
The Markov Chain Monte-Carlo Method.
The Markov Chain Monte-Carlo Method is a method for designing algorithms to sample from complicated sample spaces/to count the number of solutions to problems/ etc. The method is based on designing and analyzing Markov chains. This presentation is based on a series of lectures given
by Alistair Sinclair
from Berkeley at the SCHOOL
ON STATISTICAL PHYSICS, PROBABILITY THEORY AND COMPUTATIONAL COMPLEXITY, It includes some useful stuff, such as the analysis of the coupon collector problem and the birthday paradox, as well as some fun stuff, such as analysis of card shuffling. |
|
Undirected connectivity.
Given a graph G and two vertices s,t in G, the connectivity problem asks whether there is a path from s to t in G. The problem on directed graphs is NL-complete (where NL is non-deterministic log-space). For the undirected version there is a simple probabilistic log-space algorithm. The presentation shows this algorithm and analyzes it. The presentation was prepared in 2002 when I was a teaching assistant for an undergraduate complexity course given by Muli Safra at Tel-Aviv University. Today we know that undirected connectivity is in L (log-space), and not just in RL (randomized log-space) by the beautiful 2005 result of Omer Reingold. |
|
