Seminar

Mon, Mar 19, 2018

The current seminar is the Computation, Geometry, Logic seminar.

S2 2019 - Deep learning and reinforcement learning

In semester two of 2019 we studied reasoning in the context of deep reinforcement learning with an aim to understand AlphaGo and related breakthroughs, such as AlphaStar. Along the way we looked at deep learning more generally. Some relevant background information:

There are three main components of AlphaGo: Monte-Carlo tree search, deep learning and reinforcement learning, and we will have talks on all three aspects. One important running theme will be the dichotomy between problems with small and large state spaces, and the corresponding need for function approximation (the successful incorporation of which is what makes AlphaGo scientifically interesting).

Talk schedule:

  • Lecture 0: Geoff Hinton video “Deep learning” (brief notes by DM)
  • Lecture 1: Daniel Murfet “Introduction to reinforcement learning” (notes | video)
  • Lecture 2: James Clift “Turing and Intelligent Machinery” (notes | video | Turing’s paper)
  • Lecture 3: Thomas Quella “Hopfield networks and statistical mechanics” (notes | video)
  • Lecture 4: Will Troiani “Universal approximation by feedforward networks” (notes | paper)
  • Lecture 5: Susan Wei “Deep learning as a continuous dynamical system” (video | paper)
  • Lecture 6: Daniel Murfet “AlphaGo” (slides | video)
  • Lecture 7: Mingming Gong “Convolutional neural networks”

There is a bonus talk:

  • Rohan Mitta “Introduction to Formal Proof Verification in Lean” 13-9-19

Remarks

  • There is an interesting historical connection between talks 2 and 3. In his article “Now what” Hopfield recalls working for a year on random networks before inventing his associative memory networks (Hopfield clarified in an email that he rejected Turing’s approach because of the globally synchronised clock that it requires).
  • On the topic of formal proofs, see Kevin Buzzard’s recent talk “The future of mathematics?”.
  • Silver on classic games 1:43:40 “If there’s one thing to take away from this, it’s that really doing things in the principled way - you have to believe in your principles and you have to believe that you can overcome all of this knowledge that it feels like you should be building into the system. But actually each time you put knowledge into a system you’re really handicapping it, and if you really go back to the beginning and find the right principle to learn for itself it will do better eventually.” (on this note see the bitter lesson)

Background on deep learning and reinforcement learning:

Interesting theory papers:

S1 2019 - Topological quantum computing

The aim of the seminar in semester one of 2019 was to understand topological error correcting codes and how they enable universal quantum computers. The primary organisers for this were Thomas Quella and Charles Hill. This is a remarkable application of topology to computation: one promising approach to making quantum computing work in practice is based on the homology and cohomology of surfaces. Moreover, some of our neighbours are at the forefront of building quantum computers based on these ideas. An attractive feature of the subject is the sheer boldness of the underlying ideas, for example in Deutsch’s paper on universal quantum computation he writes in a section titled “Programming physics”:

To view the Church-Turing hypothesis as a physical principle does not merely make computer science a branch of physics. It also makes part of experimental physics into a branch of computer science. The existence of a universal quantum computer Q implies that there exists a program for each physical process.

For an entree to quantum computing, see the following recent talks:

  • 2018 Australian of the Year Michelle Simmons “The Einstein Lecture: The Quantum Computing Revolution” (material on implementations of error correction from about 49:00).
  • Jason Alicea “Topological Quantum Computing: Plenty of Room in the Middle” 2018.
  • Lecture 1: James Clift “Universal Turing Machines” (notes)
  • Lecture 2: Will Troiani “Reversible Turing Machines” (notes)
  • Lecture 3: Thomas Quella “Crash course in quantum mechanics” (notes)
  • Lecture 4: Isaac David Smith “Feynman’s quantum circuits” (notes)
  • Lecture 5: Isaac David Smith “Deutsch’s universal quantum computer (Part 1)”
  • Lecture 6: Sam Tonetto and Gary Mooney “On the complexity of Ising spin glass models”
  • Lecture 7: Stephane Dartois “Deutsch’s universal quantum computer (Part 2)”
  • Lecture 8: Charles Hill “Applications of quantum computers 1: Algorithms”
  • Lecture 9: Charles Hill “Applications of quantum computers 2: Quantum annealers”
  • Lecture 10: Thomas Quella “Physical realisations of quantum computers”
  • Lecture 11: James Clift “Classical error correcting codes” (notes)
  • Lecture 12: Will Troiani “Crash course in homology and cohomology” (notes)
  • Lecture 13: Isaac David Smith “Quantum error correcting codes” (notes | video)
  • Lecture 14: Isaac David Smith “Stabiliser formalism and the toric code” (notes | video)
  • Lecture 15: Thomas Quella “Matrix product states and tensor networks” (notes | video)
  • Lecture 16: Charles Hill “Open problems for mathematicians”

Primary references:

Explanation of the talk schedule: the aim by the end of the semester is to understand what a universal quantum computer is [D] and how the surface code introduced in [DKLP] and elaborated in [C] solves the main problem that one faces in actually physically realising such a computer, namely, quantum error correction. To understand what a universal quantum computer is, one has to first know what universal computation means (hence, Universal Turing Machines) and what reversible computation means, and to understand quantum error correction it is important to have seen classical error correction.

Other useful links:

S2 2018 - Topos theory and categorical logic

Our aim in the second semester of 2018 was to understand how to use adjoint functors and topoi to organise mathematical knowledge, following Mac Lane and Moerdijk’s book “Sheaves in Geometry and Logic”. For an explanation of this aim see the seminar announcement and the first lecture below. The seminar is supported by funding from Data61, DST group and ACEMS as part of a collaboration which aims to develop new tools to aid human reasoning about mathematics and software.

Talk schedule:

  • Lecture 1: Daniel Murfet “An invitation to topos theory” (notes | video)
  • Lecture 2: Daniel Murfet “The Curry-Howard correspondence (Part 1)” (notes | video | more notes | response to Sam’s question)
  • Lecture 3: Will Troiani “Monads and programs” (notes | video)
  • Lecture 4: James Clift “The definition of a topos (Part 1)” (notes | video)
  • Lecture 5: James Clift “The definition of a topos (Part 2)” (notes | video)
  • Lecture 6: Patrick Elliott “Sheaves of sets (Part 1)” (notes | video)
  • Lecture 7: Patrick Elliott “Sheaves of sets (Part 2)” (notes | video)
  • Lecture 8: Will Troiani “Higher-order logic and topoi (Part 1)” (notes | video)
  • Lecture 9: Daniel Murfet “Higher-order logic and topoi (Part 2)” (notes | video)
  • Lecture 10: Patrick Elliott “Sheaves form a topos (Part 1)” (notes | video)
  • Lecture 11: Patrick Elliott “Sheaves form a topos (Part 2)” (notes | video)
  • Lecture 12: Daniel Murfet “Classifying topoi (Part 1)” (notes | video)
  • Lecture 13: James Clift “Higher-order logic and topoi (Part 3)” (notes | video)
  • Lecture 14: Will Troiani “The classifying space of rings” (notes)
  • Lecture 15: Daniel Murfet “Abstraction and adjunction” (notes | video1)

References:

S2 2016 - Curry-Howard correspondence

Our aim was to read Sorensen and Urzyczyn’s book “Lectures on the Curry-Howard isomorphism”, up to the proof of the original Curry-Howard correspondence (between simply-typed lambda calculus and intuitionistic logic) in Chapter 4.

  • Will Troiani “Introduction to lambda calculus and the Church-Rosser Theorem” (lecture notes | old notes 1 | old notes 2)
  • 9-8 Samuel Lyons “All partial recursive functions are lambda-definable” (Section 1.7, lecture notes)
  • 16-8 James Clift “Simply-typed lambda calculus and strong normalisation” (Chapter 3, lecture notes)
  • 23-8 Shawn Standefer “Introduction to natural deduction” (Chapter 2, lecture notes)
  • 30-8 Daniel Murfet “The category of simply-typed lambda terms” (lecture notes)
  • 6-9 Shawn Standefer “Kripke semantics of intuitionistic logic” (lecture notes)
  • 13-9 No talk, instead we’ll watch Wadler’s Propositions as types and discuss
  • 20-9 Daniel Murfet “The category of simply-typed lambda terms II” (lecture notes and an appendix)
  • 4-10 Daniel Murfet “The Curry-Howard principle” (lecture notes)
  • 11-10 James Clift “System F: Polymorphic lambda calculus” (lecture notes)
  • 18-10 Will Troiani “System F in the real world: Haskell and functional programming” (lecture notes) (the referenced talk by Rich Hickey is “Simple made easy”)

Thanks to Camillo Fiorentini for noticing errors in the original notes for the lecture on strong normalisation, and for suggesting the fix (incorporated in the current version).

References:

S2 2016 - Topological field theory

Our aim was to read Kock’s book on the equivalence between closed 2D TFTs and commutative Frobenius algebras. The talks:

  • 28-7 Daniel Murfet “Topological Quantum Field Theory in two dimensions” (slides).
  • 4-8 Patrick Elliott “Introduction to Frobenius algebras” (lecture notes).
  • 11-8 Michelle Strumila “The cobordism category 2Cob” (beginning of Chapter 1, lecture notes).
  • 18-8 Omar Foda “Supersymmetry and Morse theory” (references are Witten’s paper and Nicolas Mee’s thesis).
  • 1-9 Patrick Elliott “The category of Frobenius algebras” (lecture notes).
  • 8-9 Thomas Quella “Chern-Simons theory as an example of a TQFT” (lecture notes).
  • 15-9 Campbell Wheeler “Symmetric monoidal categories and functors” (lecture notes).
  • 13-10 Daniel Murfet “The cobordism category” (lecture notes).

References: