Talks
- The Complexity of Boolean Functions: Mini-course at MathCamp 2008, Portland, OR, July 15-19, 2008
- Advice Coins: CCC'2008, College Park, Maryland, June 23, 2008
- Quantum Copy-Protection: QIP, New Delhi, India, December 20, 2007. Earlier versions at Perimeter Institute, March 6, 2006; Banff Centre, Banff, Canada, August 28, 2006; UC Berkeley quantum lunch, December 8, 2006; Caltech IQI seminar, January 16, 2007
- The Power of Unentanglement: CIFAR Annual Meeting, Newport, Rhode Island, October 27, 2007
- Complexity Tutorial: CIFAR Annual Meeting, Newport, Rhode Island, October 26, 2007
- Are Quantum States Exponentially Extravagant?:
Max-Planck-Institut für Quantenoptik, Garching, Germany, October 4, 2007. Earlier versions at Complexity Theory Meeting, Oberwolfach, Germany, June 9, 2005; QICL
Workshop, Perimeter Institute, Waterloo, Canada, July 20, 2005; ERATO Conference on Quantum Information Science, Tokyo, Japan, August 28, 2005
- Has There Been Progress on the P vs. NP Question?: MIT CSAIL Lunch, September 27, 2007
- Algebrization: A New Barrier in Complexity Theory: MIT Theory of Computing Colloquium, September 11, 2007; Institute for Advanced Study, Princeton, September 17, 2007; University of Latvia, Riga, October 2, 2007; Schloss Dagstuhl, Wadern, Germany, October 11, 2007; Harvard Theory Seminar, October 15, 2007; Carnegie Mellon, November 9, 2007; University of Toronto, January 25, 2008; STOC'2008, Victoria, British Columbia, May 20, 2008
- The Limits of Quantum Computers: University of Waterloo, February 19, 2007; University of Chicago, March 6, 2007; Princeton University, March 8, 2007; MIT, March 12, 2007; University of Washington, April 12, 2007; Stanford, April 16, 2007; Caltech, April 18, 2007; UC Berkeley, April 23, 2007; Cornell, April 26, 2007; CSR'2007, Ekaterinburg, Russia, September 6, 2007 (via live videoconference); Wornell Group Meeting, MIT, November 29, 2007; Dayalbagh Educational Institute, Agra, India, December 22, 2007; MIT Lincoln Laboratory, April 25, 2008; Brookhaven National Laboratory, June 10, 2008; Foo Camp, Sebastopol, CA, July 12, 2008; MathCamp, Portland, OR, July 16, 2008. Another version at SIPB Cluedump, MIT, December 3, 2007. Short version at Gathering for Gardner, Atlanta, Georgia, March 27, 2008; MIT, June 5, 2008
- Pseudorandom States: Perimeter Institute, October 30, 2006
- The Learnability of Quantum States: MIT, May 15, 2006; University of Washington, May 25, 2006; Haines Junction, Yukon Territory, May 31, 2006; Institute for Advanced Study, Princeton, July 11, 2006; Banff Centre, Banff, Canada, August 31, 2006; University of Waterloo, September 15, 2006; Perimeter Institute, September 20, 2006; Institut für Quantenoptik und Quanteninformation, Innsbruck, Austria, October 10, 2006; Yale University, October 16, 2006; University of Toronto, October 20, 2006; UC Davis Math Colloquium, December 5, 2006; UC Berkeley Theory Lunch, December 6, 2006; QIP, Brisbane, Australia, February 3, 2007
- Oracles Are Subtle But Not Malicious:
Complexity'2006, Prague, Czech Republic, July 20, 2006. Also UC Berkeley Computer Science Theory Seminar, April 4, 2005; Caltech Center for Mathematics of Information Seminar, April 22, 2005; CWI, Amsterdam,
Netherlands, May 31, 2005. Infomercial at Complexity'2005, San Jose, June 13, 2005
- The Quantum Complexity of Time Travel: Complexity'2006, Prague, Czech Republic, July 18, 2006; FQXi Conference on Foundational Questions in Physics and Cosmology, Reykjavik, Iceland, July 24, 2007
- Computational Complexity -- Why Is It So Hard?: University of Queensland, Brisbane, Australia, December 13, 2005 (Part I); December 20, 2005 (Part II); December 22, 2005 (Part III)
- Quantum Versus Classical Proofs and Advice: ERATO Office, Kyoto, Japan, September 2, 2005; Fields Institute, University of Toronto, October 7, 2005; Centre for Quantum Computing, Cambridge University,
November 30, 2005; University of Queensland, Brisbane, Australia, December 19, 2005; Center for Logic and Computation, Instituto Superior Técnico, Lisbon, Portugal, January 13, 2006
- Quantum Complexity Theory: QICL Workshop, Perimeter Institute, July 18, 2005
- The Postselection Principle:
Computer Science Colloquium, McGill University, Montreal, February 12,
2005; Computer Science Theory Lunch, Princeton University, February 25,
2005
- Formula Size Lower Bounds and Quantum States:
DIMACS Theoretical Computer Science Seminar, Rutgers University,
September 28, 2004. Another version at Schloss Dagstuhl, Wadern, Germany, October 12, 2004; UC Berkeley Quantum Reading Group, April 15, 2005
- NP-complete Problems and Physical Reality: Perimeter Institute, July 28, 2004. Listen to streaming audio (requires RealPlayer). Also
Columbia University, September 14, 2004; Banff Centre, Banff, Canada, September 20, 2004; UC Berkeley Theory Lunch, April 13, 2005; Caltech, April 28, 2005; University of Queensland Physics Colloquium, Brisbane, Australia, December 16, 2005
- The Complexity of Agreement: STOC, Baltimore, MD, May 24, 2005; MIT Algorithms and Complexity Seminar, November 15, 2007. Earlier version at UC Berkeley Theory Lunch, February 4, 2004.
Also CWI, Amsterdam, Netherlands, June 2,
2004; Institute for Advanced Study, Princeton, October 5, 2004
- Quantum States That Pack An Exponential Punch: Lorentz Center, Leiden, Netherlands, May 24, 2004
- Is Quantum Mechanics An Island In Theoryspace?: UC Berkeley Quantum Reading Group, April 2, 2004
- MARKOVIA, A Quantum Lower Bound Saga Spanning Three
Centuries: UC Berkeley, February 6, 2004. Shorter version at Institute
for Advanced Study, Princeton, October 5, 2004
- Quantum Advice and the Glorious Return of the Polynomial Method: UC Berkeley Quantum Reading Group, January 30, 2004
- Multilinear Formulas and Skepticism of Quantum Computing:
Institute for Quantum Information, Caltech, September 23,
2003; UC Berkeley, October 7, 2003; Institute for Advanced Study
, Princeton,
November 3, 2003; Bell Labs, Murray Hill, NJ, November 6, 2003; IBM
T.J. Watson Research Center, Yorktown Heights, NY, January 6, 2004; QIP'2004, Waterloo, Canada, January 15, 2004 (version with bonus features). Shorter version at STOC, Chicago, IL, June 13, 2004
- Lower Bounds for Local Search by Quantum Arguments:
University of Michigan, Ann Arbor, July 2, 2003; University of
Waterloo, August 11, 2003; University of Western Ontario Math
Colloquium, August 14, 2003; UC Berkeley Quantum Reading Group, August 29, 2003; UC Berkeley Probability Seminar, March 3, 2004. Shorter version at STOC, Chicago, IL, June 14, 2004
- The Max-Flow Min-Cut Theorem and the Foundations of Quantum Mechanics: MSRI/BIRS Workshop on Quantum Algorithms and Complexity, Banff Centre, Banff, Canada, June 20, 2003
- Quantum Lower Bounds You Haven't Seen Before II: MSRI/BIRS Workshop
on Quantum Algorithms and Complexity, Banff Centre, Banff, Canada, June 18, 2003
- Is P Versus NP Formally Undecidable?: UC Berkeley, February 14, 2003
- Why 3 Dimensions?: New Hope-Solebury high school, January 8,
2003
- Quantum Search of Spatial Regions:
IBM Almaden Research Center, January 31, 2003; Los Alamos National
Laboratory, March 6, 2003; Tel Aviv University, May 20, 2003. Shorter version
at QIP (Quantum Information Processing), MSRI, Berkeley CA, December 16, 2002; QUBIT'2003, Technion, Haifa, Israel, April 10, 2003; UC
Berkeley, October 7, 2003; FOCS, Cambridge, MA, October 12, 2003. Watch
on streaming video (requires RealPlayer).
- Quantum Lower
Bounds: Introductory Workshop on Quantum Computing, MSRI, Berkeley, August 29, 2002. Watch
on streaming video (requires RealPlayer). See also earlier version:
prelim exam talk, UC Berkeley, September 14, 2001; quantum reading group, UC Berkeley, February 27, 2002
- Quantum Computing and Dynamical Quantum Models:
quantum computing seminar, UC Berkeley, May 14, 2002; Imperial College,
London, August 14, 2002; University of Bristol, August 15, 2002; Hebrew
University, Jerusalem, May 28, 2003; Quantum Theory: Reconsideration of Foundations, Växjö, Sweden, June 2, 2003
- Quantum Lower Bound for the Collision Problem: quantum computing seminar, UC Berkeley,
November 6, 2001; DARPA QuIST Workshop (Dallas, TX), November 28, 2001;
Caltech, November 29, 2001; Hebrew University of Jerusalem, January 10, 2002; Tel Aviv
University, January 10, 2002; QIP (Yorktown Heights, NY), January 17, 2002;
Berkeley-DARPA meeting, February 12, 2002; ACM STOC'2002 (Montreal, Canada),
May 21, 2002; Weizmann Institute, Rehovot, Israel, May 11, 2003
- Meditations on Recursive Fourier Sampling: UC Berkeley Theory Lunch, April
4, 2002
- A Treehugger's Nightmare, or Read-Once Boolean Function Trees and Why I
Hate Them: UC Berkeley, February 22, 2002
- Discrete Schrödinger Stochastic Processes: UC Berkeley, April 20, 2001
- Algorithms for Boolean Function Query Properties: Bell Labs, August 17,
2000 and UC Berkeley, October 13, 2000
- Quantum
Computing and AI: Cornell AI seminar, October 20, 1999
- The
Mathematics of RoboSoccer: Cornell Mathematics Club, September 29, 1999
Notes:
- Use these slides at your own risk! They reflect what I thought at the time I gave the talks --
so sometimes what they say is outdated or inaccurate. When in doubt, refer to my papers or send me an email.
- Some time ago, I promised myself I wouldn't become the
sort of academic who keeps saying the same thing over and over with
minor variations. Unfortunately, although this is a good principle for
papers, it doesn't work for talks. You have to give the same
spiel at place after place, and you keep tweaking it based on the
audiences' backgrounds and the feedback you got the last time. That's
why a lot of the presentations above overlap each other.
[Return to home page]