Stasys Jukna

Combinatorial Methods in Complexity Theory

Lecture Notes


Sorry, the manuscript is no more avilable on-line.
Topics 1,6,7,10,11,12,14 appeared in my book  Extremal Combinatorics: With Applications in Computer Science
The remaining topics (as well as some other ones) will appear on-line in section ``Further topics''  on the home page of the book.

Vorlesungsankündigung

Preface and TOC (postscript)
 

Contents :

  1. "Decision Trees: The Depth" 
    2. Minterms and maxterms of Boolean functions
    Disjunctive/conjunktive normal forms
    Decision trees
    Nondeterminism cannot reduce the depth substantially
  2. "Decision Trees: The Size"
    3. DT size versus DNF/CNF size - the upper bound
  3. "Lower Bounds via Spectral Arguments" 
    4. The spectral argument
    Explicit lower bounds
  4. "Read-Once Branching Programs"
    5. Deterministic read-once
    Mixed Boolean functions
    Lower bounds for CLIQUE and MATCHING
    Non-deterministic read-once
  5. "Bounded Width Branching Programs"
    6. Barrington's result
  6. "Lower Bounds for Resolution"
    7. Direct proof of Haken's exponential lower bound for The pigeonhole principle
    Resolution proofs as searching branching programs
  7. "Search Problems and Random Walks"
    8. Long words over small alphabet
    Short words over large alphabet
  8. "Combinational Circuits: Asymptotic Bounds"
    9. Shannon's lower and Lupanov's upper bounds for allmost all functions.
    An explicit 2n-o(1) lower bound for threshold functions
    [Optional reading:] Complexity of addition and multiplication
  9. "Boolean Formulae"
    10. Formula size versus depth (Spira's simulation)
    The method of random restrictions
    Nechiporuk's lower bound 
  10. "Boolean Formulas" (continued) 
    11. Krapchenko's theorem, Matrix method
    Razborov's lower bound for monotone formulae
  11. "Monotone Circuits" (Razborov's result revised)
    12. Haken's method of Counting Bottlenecks
    The general (and easy!) lower bound
    Applications: Explicit exponential lower bounds
  12. "AC^0 circuits and Switching Lemma"
    13. New (very nice and constructive) proof due to Razborov
    Application to constant-depth circuits
  13. "Bounded-Depth Circuits Over {PARITY, AND} 
    14. Razborov's approximation lemma
    Exponential lower bound for the Majority
  14. "Monotone Span Programs"
    15. Upper bound for odd-factor function
    General lower bounds criterion
    Explicit lower bounds for Paley graphs
  15. "Combinatorial Games" 
    16. Voting polynomials
    The flipping cards game
  16. "Communication Complexity" 
    17. Communication games and the depth of circuits
    The rank lower bound
    Randomized communication complexity
  17. "Communication Complexity and Circuit Depth" 
    18. Concrete application of communication complexity method
    Communication game FORK, its complexity
    The amplification argument 
Back to my home page