Syllabus for COS 593
Advanced Algorithm Design
Bernard Chazelle
TTH 3:00-4:20 (Rm:TBA)

Basic Techniques
  • dynamic programming
  • linear time median
  • epsilon-approximations
  • Fibonacci/soft heaps

    Pseudorandomness
  • finite fields, Riemann's hypothesis, Weil's thm, etc.
  • low fourier coefficients via characters
  • perfect matching
  • pairwise independence, universal hash functions, expanders (for BPP)

    • Randomized Algorithms
  • Schwartz-Zippel (applns to polynomial identities, perfect matching)
  • fingerprinting (primal/dual methods)
  • primality testing (solovay-strassen, rabin-miller)
  • interactive proofs
  • IP = PSPACE and NP = PCP(log n, 1) [proofs of weakened versions]

    • Linear Programming
  • duality via Lagrangian and Farkas' lemma (geometric interpretation)
  • examples: shortest path, max flow/min cut
  • game theory (minimax theorem)
  • ellipsoid method and applications
  • Karmarkar's algorithm

    • Semidefinite Programming
  • quadratic integer programming
  • goemans-williamson's max-cut algorithm
  • eigenvalue bound

    • Lattice Basis Reduction
  • diophantine approximation (continued fractions, Roth's thm)
  • simultaneous diophantine approximation (Dirichlet's thm)
  • the LLL algorithm
  • applications: integral systems, cryptosystems, Mertens' conjecture

    • Network Flows
  • min-cost circulation (eg, max flow, bipartite matching)
  • residuals, potentials, duality thm, primal-dual approach
  • algorithms: Klein, Tardos, Goldberg-Tarjan
    • Quantum computing
  • model
  • Shor's algorithms for factoring and discrete log
  • quantum error-correcting codes
  • Grover's search algorithm and its geometry