References

References will be updated as the course progresses: [ pdf ] [ bibtex ]

• Locally decodable codes: [Kerenidis and de Wolf, 2004]

• GapCVP(sqrt(n)) in co-NP: [Aharonov and Regev, 2005]
  For more on lattices, see the lecture notes for a course taught by Oded Regev.

• Polynomials from quantum algorithms: [Beals, Buhrman, Cleve, Mosca, and de Wolf, 2001],   [Grover, 1996]

• Degree of AND-OR formulae: [Ambainis, Childs, Reichardt, Spalek, Zhang, 2007]

• Closure of PP under intersection: [Aaronson, 2005]

• Spectral adversary bound for quantum query complexity: [Hoyer, Lee, Spalek, 2007]

• Spectral adversary bound for classical formula size: [Laplante, Lee, Szegedy, 2005]

• Adversary-type bound for classical decision trees: [Aaronson, 2006]

• Cryptosystems based on worst-case hardness of lattice problems: [Peikert, 2009] and [ Regev, 2005]

• Area laws and approximation by matrix product states: [Hastings, 2007]
  Also see the slides from Hastings' talk at QIP 2009.