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

1. Pick a topic or a set of papers and read it thoroughly.
2. Pick a problem or an application where you can apply the idea.
3. Research your application and propose a problem that you can solve.
4. Write down your solution.

• Quantum Computing: Papers & Articles; News; Lots of Related Links; See paper by Bernstein and Vazirani "Quantum Complexity Theory" (postscript form); See paper by Ambianis "A New Protocol and Lower Bounds for Quantum Coin Flipping"; Also see the collection of downloadable papers at tIgor Markov's Quantum Computing Circuits course website;
• Molecular Computing: Seminal Paper by Leonard M. Adleman "Molecular Computation of Solutions to Combinatorial Problems"; Other Publications; Erik's Molecular Computation page; See paper by Reif "Alternative Computational Models: A Comparison of Biomolecular and Quantum Computation"; See paper by Reif "Paradigms for Biomolecular Computation" ; See paper by Paun and Salomaa "From DNA Recombination to DNA Computing Via Formal Languages" ; See paper by Castellanos, Paun, et al. "Computing with Membranes: P Systems with Worm-Objects" ;
• Alternating Turing Machines: See the classic paper titled "Alternation" by Chandra, Kozen and Stockmeyer, Journal of the ACM, Vol. 28, No. 1, 1981, pages 114-133.
• Pebble Games and Time-Space Tradeoffs: See 2 classic papers (1) "On Time Versus Space" by Hopcroft, Paul and Valiant, Journal of the ACM, Vol. 24, No. 2, 1977, pages 332-337, AND (2) "Space Bounds for a Game on Graphs", by Paul, Tarjan, and Celoni, Mathematical Systems Theory, Vol. 10, 1977, pages 239-251.
• Probabilistic Turing Machines: See another classic paper by Gill titled "Computational Complexity of Probabilistic Turing Machines", SIAM Journal on Computing, Vol. 6, No. 4, 1977, pages 675-695.
• Information Theory: There is a book by Gregory Chaitin titled "Algorithmic Information Theory" (on reserve in Library), and two articles by him: (1) "On the length of programs for computing finite binary sequences", Journal of the ACM, Vol. 13, 1966, pages 547-569, AND (2) "A theory of program size formally equivalent to information theory", Journal of the ACM, Vol. 22, 1975, pages 329-340.
• Oracle Turing Machines and Relativizations: Yet another classic paper titled "Relativizations on the P=NP question", by Baker, Gill and Solovay, SIAM Journal on Computing, Vol. 4, 1975, pages 431-442.
• The Power of Interaction and Arthur-Merlin Games: See the following 3 papers: Lund, Fortnow, Karloff and Nisan: "Algebraic Methods for Interactive Proof Systems", Journal of the ACM, pages 859-868; Shamir: "IP = PSPACE", Journal of the ACM, pages 869-877; Shen: "IP = PSPACE: Simplified Proof", Journal of the ACM, pages 878-880.
• Parallel Models of Computation: See a recent paper by Juurlink and Wijshoff "A quantitative comparison of parallel computation models" to find lots of reference to parallel models of computations and parallel machines that have been built.
• Miscellaneous Models See book by Gary Flake titled Computational Beauty of Nature (placed in the reference section in the library) - this book views interesting topics such as Fractals, Chaos, Complex systems, and Adaptation from a computational viewpoint. For example, what is an L-system? what is an IFS? how can it help you to model a tree from a garden? What is a cellular automata and how are they classified? What is Conway's "Game of Life"? What are applications of these models? What is a neural network and what are its applications? How do they learn or acquire knowledge? What are phase transitions and its applications? What are self-organizing maps and their applications? What are hidden markov models and what are they useful for?