\documentclass[12pt]{article}
\usepackage{latexsym}
\usepackage{amsfonts,amsmath,graphics,amssymb}
\newcommand{\set}[1]{\{ #1 \}}
\newcommand{\structure}[1]{\langle #1 \rangle}
\newcommand{\game}[1]{\widehat{G}_{#1}(D,g)}
\newcommand{\power}[1]{\mathcal{P}(#1)}
\newcommand{\ggame}[2]{\widehat{G}_{#1}(D,#2)}
\newcommand{\fight}[3]{\put(#1,#2){\circle{0.6}{\tiny#3}}}
\newcommand{\ol}{\overline}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\ns}{\vartriangleleft}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceiling}[1]{\lceil #1 \rceil}
\newcommand{\R}{\mathbb{R}}
\newcommand{\inv}[1]{#1^{-1}}
\newcommand{\ep}{\varepsilon}
\newcommand{\mat}[4]{\left(\begin{array}{cc}
 #1 & #2 \\
 #3 & #4 \\
\end{array}\right)}

\begin{document}
\begin{center}
Oral Exam Syllabus\\
Paul Raff \\
Committee: Jeff Kahn (chair), Mike Saks, Fred Roberts, J\'ozsef Beck
\end{center}
\textbf{1. Combinatorics and Graph Theory}\\
\\
\textbf{1.1. Combinatorics}\\
\\
\textbf{Basics:} counting arguments, generating functions, binomial coefficients, recurrence relations, reflection principle, inclusion-exclusion, Stirling's formula.\\
\textbf{Set Systems:} Sperner's Theorem, Kruskal-Katona, Erd\H{o}s-Ko-Rado, Fisher and generalized Fisher inequality, Frankl-Wilson, Ray-Chaudhuri-Wilson, nonuniform RCW, Steiner systems, isoperimetric problems and Harper's Theorem.\\
\textbf{Lattices:} geometric and distributive lattices, chains in distributive lattices, linear extensions of posets, the incidence algebra, the M\"obius inversion formula, Weisner's Theorem, Dowling-Wilson.\\
\textbf{Rational Generating Functions:} fundamentals, interplay between rational generating functions, recursive sequences, and closed-form formulae.\\
\textbf{Linear Algebra Methods:} Combinatorial Nullstellensatz and its applications, inclusion matrices, Chevalley-Warning, Alon-Dubiner, Erd\H{o}s-Ginzburg-Ziv.\\
\textbf{Correlation Inequalities:} The Four Functions Theorem, the FKG Inequality, Harris-Kleitman, the XYZ-theorem.\\
\textbf{Ramsey Theory:} Ramsey's Theorem for graphs and hypergraphs, countable and uncountable Ramsey Theory, K\"onig's Lemma, upper and lower bounds, van der Waerden's Theorem and the statements of Roth and Szemer\'edi.\\
\begin{footnotesize}
\textbf{Sources}\\
Bollob\'as, \emph{Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Conditional Probability}\\
van Lint and Wilson, \emph{Combinatorics}\\
Babai and Frankl, \emph{Linear Algebra Methods in Combinatorics}\\
Alon, \emph{Combinatorial Nullstellensatz} (paper)\\
Jeff Kahn's notes for 640-582, Fall 2004\\
\end{footnotesize}
\\
\newpage
\noindent\textbf{1.2. Graph Theory}\\
\\
\textbf{Matching:} Hall's theorem, K\"onig's theorem, matching algorithms, Gale-Shapley, Augmenting Paths, Tutte's Theorem.\\
\textbf{Connectivity and Spanning Trees:} Menger's Theorem, Max Flow/Min Cut Theorem, Prim's Algorithm, Kruskal's Algorithm, Dijkstra's Algorithm, Cayley's Theorem, Pr\"ufer Codes.\\
\textbf{Planarity:} Euler's Formula, Kuratowski, Wagner's Theorem, Tarjan's Algorithm for planarity testing.\\
\textbf{Coloring:} Chromatic and Edge Chromatic Numbers, List Coloring, Brook's Theorem, Vizing's Theorem, chromatic polynomials and properties, 5-color theorem, perfect graphs, perfect graph theorem.\\
\textbf{Extremal Problems:} Tur\'an's Theorem, Statement of Regularity Lemma and its application to the Erd\H{o}s-Stone Theorem.\\
\begin{footnotesize}
\textbf{Sources}\\
Diestel, \emph{Graph Theory}
\end{footnotesize}\\
\\
\noindent\textbf{1.3. Probabilistic Methods}\\
\\
\textbf{Basics:} Linearity of Expecation, Bonferroni Inequalities, common distributions, conditional probability, law of total probability, Chernoff bounds, Chebyshev Inequality, coupling.\\
\textbf{Alteration Method:} General idea and application to Property B.\\
\textbf{Second Moment Method:} General procedure and application to threshold functions.\\
\textbf{Lov\'asz Local Lemma:} Symmetric and general versions, application to Ramsey lower bounds.\\
\textbf{Poisson Paradigm:} Janson inequalities, application to number of triangles in $G_{n,p}$, Brun's Sieve, application to the number of isolated points.\\
\textbf{Martingales:} Definitions, Azuma's Inequality, applications to chromatic number.\\
\textbf{Random Graphs:} Monotone properties, $G_{n,p}$ v. $G_{n,k}$, threshold functions, connectedness.\\
\begin{footnotesize}
\textbf{Sources}\\
Alon and Spencer, \emph{The Probabilistic Method}\\
Jeff Kahn's notes for 642-591, Fall 2005
\end{footnotesize}\\
\\
\newpage
\noindent\textbf{2. Computational complexity theory and algorithm analysis}\\
\\
\textbf{Separation theorems:} Gap Theorem, Time and Space Hierarchy
Theorems (deterministic and nondeterministic versions), linear speedup theorem, statement of the Blum Speedup
Theorem.\\
\textbf{P v. NP:} Definitions, reducibility, \#P, the Cook-Levin Theorem, NP-completeness of \textsc{independent set}, \textsc{vertex cover}, \textsc{$k$-colorability}, \textsc{planar 3-colorability}, \textsc{exact cover}, \textsc{knapsack}, \textsc{subset sum}, \textsc{partition}, \textsc{hamiltonian cycle}.\\
\textbf{Space-bounded complexity:} Savitch's theorem, the Immerman-Szeleplcs\'enyi Theorem and implications.\\
\textbf{Polynomial hierarchy:} Definitions of $\Sigma_i, \Pi_i, \Delta_i$, complete problems, conditions that lead to the collapse of PH.\\
\textbf{Circuits:} Characterization of P/poly as TMs with advice, The Karp-Lipton Theorem, characterization of PH as DC uniform circuits.\\
\textbf{NC hierarchy:} Definitions of NC$^{i}$, AC$^{i}$, SAC$^{i}$. Branching programs and NC$^{1}$ (Barrington).\\
\textbf{Lower bounds:} Simple bounds, polynomial method, Smolensky's theorem. Hastad's switching lemma and application to circuit lower bounds.\\
\textbf{Probabilistic Proof Systems:} Definitions of IP, PCP, and zero-knowledge proofs, Co-NP $\subset$ IP, main ideas behind IP = PSPACE.\\
\textbf{Randomization:} Definition of RP, BPP and ZPP, BPP $\subseteq \Sigma_2 \cap \Pi_2$, BPP $\subseteq$ P/\emph{poly}, Toda's Theorem.\\
\textbf{Derandomization:} Nisan-Wigderson pseudorandom generator, application to derandomizing BPP.\\
\textbf{Decision Trees:} Decision tree complexity, 0- and 1-certificates, certificate complexity, randomized decision tree complexity, sensitivity, block sensitivity.\\
\textbf{Communication Complexity:} Fooling sets, tiling lowerbound, rank lowerbound.\\
\begin{footnotesize}
\textbf{Sources}\\
Papadimitriou, \emph{Computational Complexity}\\
Arora, \emph{Computational Complexity: A Modern Approach}\\
Rudich and Wigderson (editors), \emph{Computational Complexity Theory}\\
\end{footnotesize}\\

\end{document}