All video recordings and presentation slides are saved in this Box folder: https://ucdavis.box.com/s/oln1uis9rzkc0w8qidr15a1vq4y15x7o.
Check also Daniel's commentary on our weekly meetings at his homepage at https://tobias.cs.ucdavis.edu/quantum-complexity-reading-group-started-102022.html.
Spring 2023
25 April 2023: Random Oracle Separations and Forrelation.
18 April 2023: Complexity Zoology and Forrelation.
11 April 2023: Robert Sander's code of Complexity Zoology: https://rjsworks.wordpress.com/complexity-zoology/.
Winter 2023
7 February 2023: Discussion on the Aaronson-Wigderson notion of algebrization and looking at oracles as a family of Boolean polynomials.
31 January 2023: Review of interactive proof classes from QC Since Democritus and some discussion about algebrization as a proof barrier.
24 January 2023: Expander graphs and the basic concepts in Dinur's proof of the classical PCP theorem.
17 January 2023: Calculating the Kauffman and Jones polynomials of the Hopf link.
10 January 2023: Proof of BQP/qpoly ⊆ PP/poly. Classical version of the PCP theorem and its variants.
3 January 2023: Interactive proofs and related complexity theory from Aaronson's Quantum Computing Since Democritus chapter 17.
Fall 2022
27 December 2022: After Christmas orientation. Some plans to discuss the Jones polynomial in the context of the quantum circuit model.
29 November 2022: Introduction to the quantum PCP conjecture and its relation to the NLTS conjecture.
22 November 2022: Advice, Oracle Separation, QMA & QCMA
15 November 2022: QMA-Completeness of Local Hamiltonian Problem - Part I
8 November 2022: Reductions in Classical Complexity and Hamiltonian Complexity Part 2
1 November 2022: Hamiltonian Complexity Part 1