COT 5420: Theory of Computation I -- Fall 01
Semester Project

• Quantum Computing: Papers & Articles; News; Lots of Related Links.
• Molecular Computing: Seminal Paper by Leonard M. Adleman "Molecular Computation of Solutions to Combinatorial Problems; Other Publications; Erik's Molecular Computation page.
• Arthur-Merlin Games
• Interactive Proof Systems
• Primality Testing
• Polynomial-Time Hierarchy
• Stochastic Grammars
• Kolmogorov Complexity
• Lower Bound Proofs
• Information Theoretic Lower Bounds
• Crossing Sequence Techniques
• Splicing Systems
• Communication Complexity Theory
• Pebble Games
• Time-Space Tradeoffs
• Turing Machines with Oracles and ${\cal P} = {\cal NP}$
• Complexity of Chess and Go
• Circuit Complexity
• One-way Functions and Cryptography
• Complexity of Counting Problems
• Ant Colony Optimization: See ACO