Concrete Models of Computation CS 497 JE: Spring 2003 Jeff Erickson TuTh 11:00-12:15 256 Mechanical Engineering Building

This course will survey methods for proving that certain computational problems are inherently difficult. Since it is virtually impossible to reason about the difficulty of problems in abstract computing models like Turing machines (hence the whole P vs. NP vs. PSPACE mess), most complexity lower bounds are developed in more restricted models of computation, tailored to the problem at hand. Most of the material will be orthogonal to topics covered in a more traditional abstract computational complexity course (like CS/ECE/Math 479).

Schedule so far: January 21: Introduction, decision trees, determinisic versus randomized complexity January 23: More on decision trees, Fibonacci search, the "Little Birdie" Principle, partial orders January 28: lower bounds for selection January 30: Sorting with partial information, the 1/3-2/3 conjecture, Brunn-Minkowski symmetrization. [Copies of Chapter 21.3 of Matousek's book are available outside my office door.] Homework 1 due February 18. Erratum: Problem 3 should say "find the k largest elements in sorted order" February 11: Boolean decision trees, evasiveness, certificate complexity, n-card Monte, graph connectivity, Hruska (iterated median-of-3), C(n) < R(n) < D(n) < C(n)2 Feburary 13: Odd properties are evasive, unbalanced properties are evasive, "at most k 1s" is evasive, the Aanderaa-Karp-Rosenberg conjecture Feburary 18: permutation groups, The Rivest-Vuillemin theorem, nontrivial monotone properties of n-vertex graphs are weakly evasive when n is a prime power Homework 2 due March 4. February 20: nontrivial monotone graph properties are weakly evasive for all n, simplicial complexes, noncollapsible complexes are evasive February 25: No <cough> class today <sniff>. Uuuuugggh. Sorry. February 27: Linear decision trees, algebraic decision trees, Omega(n log n) lower bounds for everything under the sun March 4: Algebraic computation trees, real RAMs, n-1 lower bound for finding the maximum via generic width Homework 3 due March 20. March 6: Polynomial-depth linear decision trees for Knapsack via Meiser's point-location algorithm March 11: Lower bounds for computing polynomials; Horner's rule is optimal without preprocessing and almost optimal in the worst case after preprocessing coefficients; degree of transcendance March 13: "On the complexity of halfspace area queries" No class March 18 and 20; Jeff was out of town. No class March 25 and 27; it's spring break. April 1: Communication complexity: one way communication; two-way communication; partition into disjoint monochromatic minors; fooling sets April 3: Non-determinsitic communication protocol; cover by overlapping monochromatic minors; generic determinstic protocol from minimal cover; space-time tradeoffs for single-tape Turing machines April 8: Multi-party communication ("Indian poker"): forbidden k-patterns, Ramsey theory April 10: Randomized protocols, one-sided error, fingerprints, bais, discrepancy, eigenvectors and eigenvalues Homework 4 due April 23. April 15: Pseudorandom number generators April 17: Yao's Lemma (distributional complexity = randomized complexity): easy proof of the useful direction, linear programming duality April 22: Yao's lemma for algorithms with errors: 2 Re(F) < D2e(F) April 24: Circuit complexity: Basics, at least k, most functions are hard (Shannon) but we have no specific bad examples April 29: Shannon's bound is tight; circuit depth vs. communication complexity May 1,6: Smolensky's exponential lower bound for constant-depth, unbounded-fanin circuits for PARITY: (1) Any function with small size and depth can be approximated by a polynomial of low degree over Z3; (2) If PARITY can be approximated by a polynomial of degree sqrt{n}, then every function can be approximated by a polynomial of degree n/2 + sqrt{n}. Take-home final due May 16.

Administrivia:

• Credit: 1 hour
• Course work: Several problem sets, probably a take-home final exam
• Prerequisites: CS 373 or CS 375 or my permission. Algorithmically and/or mathematically mature undergraduates are welcome.
• Will this satisfy the graduate theory course requirement? Only if you are a theory student. If you think this applies to you, talk to me in person.

Possible course topics:

• Decision trees: searching, sorting, and selection; evasiveness of string and graph properties; deterministic vs. randomized (vs. quantum?) complexity
• Range searching models: pointer machines; indexability; semigroup and group arithmetic
• Algebraic complexity: straight-line programs; branching programs; algebraic decision and computation trees; pebbling games; space/time tradeoffs
• Circuit complexity: lower bounds for monotone circuits; size/depth/fan-in tradeoffs
• Sorting networks: expanders; the AKS network
• Communication complexity: two-party and multi-party protocols; VLSI area/time tradeoffs
• Real-number computing: real RAMs; the Blum-Shub-Smale model
• Quantum computing: Grover and Shor's algorithms; quantum circuits and decision trees

Suggested reading:

(This list will expand as the course progresses.)

• Recommended textbook: John E. Savage. Models of Computation: Exploring the Power of Computing. Addison-Wesley, 1998. See also Savage's complexity course at Brown.

• Pankaj K. Agarwal and Jeff Erickson. Geometric range searching and its relatives. Advances in Discrete and Computational Geometry, pages 1-56. AMS Press, 1999.
• Bernard Chazelle. The Discrepancy Method: Randomness and Complexity. Cambridge University Press, 2001.
• Catherine E. Chronaki. A survey of evasiveness: Lower bounds on the decision-tree complexity of Boolean functions, Technical Report, Computer Science Department, University of Rochester, 1990.
• László Lovasz and Neal E. Young. Lecture notes on evasiveness of graph properties. Technical Report CS-TR-317-91, Computer Science Department, Princeton University, 1991. ArXiv:cs.CC/0205031.
• Jiri Matousek. Lectures on Discrete Geometry. Springer-Verlag, 2002.