Topics:

Here is a list (probably too large) of things we may cover:

Church's thesis: My proof (an auxiliary figure) Church's (weak) thesis is false for N Newtonian point masses but becomes (strongly) true for relativistic non-point masses
Information and entropy :
- E.T. Jaynes. Information theory and statistical mechanics, Physical Review, 106,4 (May 1957) 620-630.
- limits on bit rate and bit density from thermodynamics and other arguments
  - N.H.Margolus & L.B.Levitin: The maximum speed of dynamical evolution, (T. Toffoli, M. Biafore, and J. Leao, eds.) PhysComp96, pages 208-211.
  - J.D. Bekenstein: Energy cost of information transfer, Physical Review Letters}, 46:623--626, 1981.
  - J.D. Bekenstein: Universal upper bound on entropy-to-energy ratio for bounded systems, Physical Review D, 23(2) (January 1981) 287-298.
  - J.D. Bekenstein: Entropy content and information flow in systems with limited energy, Physical Review D, 30,8 (1984) 1669-1679.
  - W.D. Smith: Fundamental physical limits on information storage
  - W.D. Smith: Fundamental physical limits on information flux
- reversible computing - no power needed (?)
  - C.H.Bennett: Time/space trade-offs for reversible computation, SIAM J. Computing, 18,4 (1989) 766-776.
  - R.Y.Levine & A.T. Sherman: A Note on Bennett's Time-Space Tradeoff for Reversible Computation, SIAM J. on Computing 19,4 (1990) 673-677.
  - C.H.Bennett: Demons, engines, and the second law, Scientific American (1987) 108-116.
  - C.H.Bennett & Rolf Landauer: The Fundamental Limits of Computation, Scientific American(July 1985) 48-56 (38-53 in some versions).
  - C.H.Bennett: Notes on the History of Reversible Computation, IBM J. Research and Development 32,1 (1988) 16-23.
  - C.H.Bennett: The logical reversibility of computation, IBM J. Res. Devel. 6 (1979) 525-532. IBM JR&D 17 (1973) 525-532.
  - C.H.Bennett: Thermodynamics of computation, a review, Int.J.Theor.Phys. 21 (1982) 905-940. (Special issue on computation.)
  - E.Fredkin & T.Toffoli: Conservative logic, Int.J.Theor.Phys. 21 (1982) 219-253.
  - T.Toffoli: Bicontinuous extensions of invertible combinatorial functrions, Math.Systems Theory 14 (1981) 13-23.
  - L.Priese: On a simple combinatorial structure sufficient for studying nontrvial self reproduction, J.Cybernetics 6 (1976) 101-137.
  - Knight's reversible CMOS logic papers here e.g. Younis, S.G. and Knight, Jr., T.F.: Asymptotically Zero Energy Split-Level Charge Recovery Logic, International Workshop on Low Power Design (1994) 177-182.
  - Knight's ideas date to "Hot clock nMOS" by C.L.Seitz et al Chapel hill conference on VLSI 1 (1985), and discussed in Feynman's book.
  - P.Benioff: Quantum mechanical models of Turing machines that dissipate no energy, Phys.Rev.Lett. 48 (1982) 1581-1585.

error correcting codes - Spielman's computationally efficient codes
reliable computing with unreliable computational elements
- Spielman: Highly Fault-Tolerant Parallel Computation
- Spielman & Sipser: expander codes
- Spielman: Linear-time encodable and decodable ECCs
- R.L. Dobrushin and S.I. Ortyukov: Upper bound for the redundancy of self-correcting arrangements of unreliable functional elements, Prob. Info. Transmission 13 (1977) 203-218.
- Toom and Gacs ??
- P.Gacs: Reliable computation with cellular automata, J. Computer Systems Sci., 32(32) (1986) 15-78.
- P.Gacs & J.Reif. A simple 3d real-time reliable cellular array, J. Computer Systems Sci. 36 (1986) 125-147.
- N.Pippenger: Developments in the synthesis of reliable organisms from unreliable components, In J.Glimm, J.Impagliazzo, and I.Singer, editors: The legacy of John von Neumann, volume 50 of Proc. symp. pure math., AMS, 1990.
- N.Pippenger: On networks of noisy gates, Proc. IEEE Symp. Foundations of Computer Sci., 26 (1985) 30-38.
- N.Pippenger: Reliable computation by formulas in the presence of noise, IEEE Trans. Info. Theory, IT-34,2 (1988) 194-197.
Cellular Automata
- Tommaso Toffoli: Computation and Construction Universality of Reversible Cellular Automata, JCSS 15,2 (1977) 213-231.
VLSI theory
- B.M. Chazelle and L.Monier. A model of computation for VLSI with related complexity results, Journal of the ACM, 32,3 (1985) 573-588.
- G.Bilardi, M.Pracchi, F.P.Preparata: A critqiue of network speed in VLSI models of computation, IEEE J. solid state circuits SC-17 (Aug. 1982) 696-702.
- Henessy & Paterson: computer arithmetic appendix???
- Thomas Lengauer: VLSI theory, 836-868 in J.van Leeuwen, editor: Handbook of theoretical computer science volume A, MIT Press, 1990.
- J.Vuillemin: A combinatorial limit to the computing power of VLSI circuits, IEEE Trans. Computers C-32, 3 (March 1983) 294-300.
mechanical systems made of rigid parts - their computational power
- lecture notes by me
quantum computers:
- SIAM J. Computing 26,5 (Oct 1997) special issue on quantum computing
- Universal quantum gate set: Phys. Rev. A 52 (1995) 3457-3467.
- Shor's quantum factoring algorithm, SIAM J. Computing 26 (1997) 1484-1509.
- Grover's quantum searching algorithm (Brassard analysis); quant-ph/9605034 [abs, src, ps] : ???? Title: Tight bounds on quantum searching Authors: Michel Boyer (Universite de Montreal), Gilles Brassard (Universite de Montreal), Peter Hoeyer (Odense University), Alain Tapp (Universite de Montreal) Comments: 8 pages, LaTeX2e, PhysComp 96 submission
Quantum error correcting codes;
- P.W.Shor: "Scheme for reducing decoherence in quantum computer memory," Phys. Rev. A 52 (1995) 2493
- E.M.Rains, R.H.Hardin, P.W.Shor, N.J.A.Sloane: A Nonadditive Quantum Code, Phys. Rev. Lett. 79 (1997) 953-954.
Quantum "purification" and "teleportation";
- C.H. Bennett, G. Brassard, C. Cripeau, R. Jozsa, A. Peres, and W. Wootters: Teleporting an unkown quantum state by dual classical and EPR channels. Physical Review Letter , 70:1895-1898, 1993.
decoherence
- E.Joos & H.D.Zeh: The emergence of classical properties through interaction with the environment, Zeitschr. Phys. B 59 (1985) 223-243.
- K.Hepp & E.H.Lieb: Phase transitions in reservoir driven open systems with applications to lasers and superconductors, Helvetica Physica Acta 46 (1973) 573-603
- W.Unruh & W.H.Zurek: ??
- A.O.Caldiera and A.J.Leggett: Path integral approach to quantum brownian motion, Physica A 121 (1983) 587-616
- R.P.Feynman & F.L.Vernon Jr.: Ann. Phys. (NY) 24 (1963) 118-
- W.H.Zurek: Decoherence and the transition from quantum to classical, Physics Today 44 (1991) 36-44.
- W.H.Zurek: Phys. Review D 26 (1982) 1862-
classical information theory
- C.E. Shannon. Probability of error for optimal codes in a gaussian channel, Bell Syst. Tech. J. 38,3 (May 1959) 611-656.
- C.E. Shannon & W.Weaver. The mathematical theory of communication, Univ. Illinois Press, Urbana, 1949.
quantum information theory
Quantum cryptography
- Stephen Wiesner: "Conjugate Coding," SIGACT News 15 (1983), p. 77
- Bennett, C. H., Bessette, F., Brassard, G., Salvail, L. and Smolin, J., "Experimental quantum cryptography", J. Cryptology 5,1 (1992) 3-28.
- Bennett, C. H., Brassard, G. and Ekert, A. K., "Quantum cryptography", Scientific American, (October 1992) 50-57.
- Kilian, J., "Founding cryptography on oblivious transfer", Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 1988, pp. 20 - 31.
- Mayers, D., "Unconditionally secure quantum bit committment is impossible", Physical Review Letters 78 (1997) 3414-3417.
- Quantum crypto bibliography
offbeat ways to view quantum and classical mechanics (path integrals, Wigner picture, Nelson picture, Hamilton-Jacobi equation)
- E.Nelson: Derivation of the Schrodinger equation from newtonian mechanics, Physical Review 150,4 (1966) 1079-1085.
- Lecture notes by me
Josephson junctions
- Feynman lecture notes in physics volume 3, final chapter
- D.J.Scalopino: "Josephson effects" article in "Encylopedia of physics"
- Likharev: Josephson junction computers ``rapid single flux logic''
- Lecture notes by me