%% LyX 1.1 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[english]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{babel}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@}

\makeatother
\begin{document}

\title{Oral Qualifying Exam Syllabus}


\author{Nicholas Weininger}

\maketitle
Committee: Profs. E. Allender, J. Beck, J. Kahn, M. Saks

~


\section{Combinatorics and graph theory}


\subsection{Combinatorics}

\textbf{Basics:} counting arguments, generating functions, binomial
coefficients, recurrence relations, inclusion-exclusion principle,
Stirling's formula.

\textbf{~}\\
\textbf{Set systems:} Sperner's theorem, Fisher's and generalized
Fisher's inequalities, existence of Steiner systems, Frankl-Wilson
theorem, Borsuk conjecture and Kahn-Kalai counterexample, Baranyai's
theorem.

\textbf{~}\\
\textbf{Extremal problems:} Intersecting families, Erd\H{o}s-Ko-Rado
theorem, Harper's theorem, Kruskal-Katona theorem, compression method. 

~\\
\textbf{Lattices:} Geometric and distributive lattices, Birkhoff covering
property, Jordan-Dedekind chain condition, M\"obius inversion, Weisner's
theorem, Dowling-Wilson theorem.

~\\
\textbf{Correlation inequalities:} Harris/Kleitman theorem, FKG inequality,
Four Functions Theorem, application to \( xyz \) inequality.

~\\
\textbf{Discrepancy results:} Erd\H{o}s-Selfridge theorem, Beck-Fiala
theorem, Roth's theorem on 2-D discrepancy, Roth's {}``second theorem''
(discrepancy in arithmetic progressions), properties of positive-density
sets.

~\\
\textbf{Ramsey theory:} Ramsey's theorem for graphs and hypergraphs,
K\"onig's lemma, infinite Ramsey theorem, general upper bounds, probabilistic
lower bounds, stepping-up lemma, van der Waerden's theorem.

~\\
\emph{References:} notes for Combinatorics I and II, fall 2001-spring
2002; notes for Combinatorics II, spring 2001; van lint and Wilson,
\emph{A Course in Combinatorics.}


\subsection{Graph theory}

\textbf{Matchings:} K\"onig-Hall theorem, Hungarian algorithm, Tutte's
1-factor theorem, Berge's theorem.

~\\
\textbf{Connectivity and spanning trees:} basic properties, Menger's
theorem, Max-Flow-Min-Cut theorem, Matrix-Tree Theorem, Pr\"ufer codes,
minimum-cost spanning trees.

~\\
\textbf{Planarity:} Euler's formula, Kuratowski's theorem.

~\\
\textbf{Coloring:} chromatic and edge chromatic numbers, Brooks' theorem,
Vizing's theorem, perfect graphs, Lov\'asz perfect graph theorem.

~\\
\textbf{Extremal problems:} Tur\'an's theorem, Erd\H{o}s-Stone theorem.

~\\
\textbf{Regularity lemma:} statement (not proof!) and application
to graph Ramsey numbers (CRST result).

\emph{~}\\
\textbf{Graph minors:} Wagner's theorem, application to equivalence
of four-color theorem and Hadwiger's conjecture for case \( r=5 \)\emph{.}

\emph{~}\\
\emph{References:} notes for Graph Theory, spring 2001; Diestel, \emph{Graph
Theory}.


\subsection{Probabilistic methods}

\textbf{Probability basics:} linearity of expectation, Bonferroni
inequalities, binomial and Poisson distributions, conditional probabilities,
law of total probability, Chebyshev's inequality, Chernoff bound,
coupling and stochastic domination.

~\\
\textbf{Random graphs:} monotone properties, \( G_{n,p} \) versus
\( G_{n,M} \), existence of threshold functions, relationship between
connectedness and having no isolated vertices, probabilistic refutation
of Haj\'os conjecture.

~\\
\textbf{Second Moment Method:} general procedure, application to threshold
function for having a certain graph as a subgraph. 

~\\
\textbf{Lov\'asz Local Lemma:} symmetric and asymmetric versions,
applications to hypergraph discrepancy and Latin transversals.

~\\
\textbf{Martingales:} Azuma's inequality, edge and vertex exposure,
application to chromatic number.

~\\
\textbf{Poisson paradigm:} Janson inequalities, application to number
of triangles in \( G_{n,p} \); Brun's sieve, application to number
of isolated points in \( G_{n,p} \).

~\\
\emph{References:} notes for Probabilistic Methods in Combinatorics,
fall 2001; Alon and Spencer, \emph{The Probabilistic Method,} 2nd
ed.


\section{Computational complexity theory}

\textbf{Separation theorems:} Gap Theorem, Time and Space Hierarchy
Theorems (deterministic and nondeterministic versions), Blum Speedup
Theorem.

~\textbf{}\\
\textbf{Relating circuit and TM complexity:} nonuniform circuit complexity
vs. Turing machines with advice functions, definition and bounds for
alternating TMs, relationship between uniform circuit families and
alternating TMs.

\textbf{~}\\
\textbf{NC hierarchy:} definitions of \( NC^{i} \), \( AC^{i} \),
\( SAC^{i} \), closure of \( SAC^{i} \) under complementation. Branching
programs and \( NC^{1} \), nonsolvable group method.

\textbf{~}\\
\textbf{Reducibility:} polytime many-one, Turing reducibility, stricter
circuit reducibility notions (\( AC^{0} \) reducibility etc), randomized
reducibility.

~\\
\textbf{Lower bounds:} simple bounds, polynomial method, Smolensky's
theorem. Hastad's switching lemma and application to circuit lower
bounds.

~\\
\textbf{Isolation method:} the Isolation Lemma, application to proof
that \( NL/poly=UL/poly \).

~\\
\textbf{Polynomial hierarchy:} unambiguous and probabilistic complexity
classes, error types (\( n \)-sided for \( n=0,1,2 \)), Toda's Theorem. 

~\\
\textbf{Derandomization:} Nisan-Wigderson pseudorandom generator,
application to derandomizing BPP.

\textbf{~}\\
\textbf{Query complexity:} deterministic, nondeterministic, and quantum
versions, sensitivity/block sensitivity/certificate complexity bounds,
degree bounds, adversary bounds.

~\\
\textbf{Space-bounded complexity:} Savitch's theorem, closure of NL
under complementation.

~\\
\emph{References}: notes from Computational Complexity Theory, spring
2002; notes from Quantum Computation, spring 2001; Vollmer, \emph{Introduction
to Circuit Complexity}; Hemaaspandra and Ogihara, \emph{The Complexity
Theory Companion}.
\end{document}
