Talks
- Big Numbers: Fourth Annual Marvin I. Freedman Memorial Colloquium, Boston University, March 30, 2012.
- Quantum Computing and its Philosophical Implications: Yeshiva University, New York, NY, March 26, 2012
- Some Thoughts and Open Problems about Simulated Annealing and the
Adiabatic Algorithm: PCTS Quantum Statistical Mechanics Workshop,
Princeton University, Princeton, NJ, March 23, 2012
- Quantum Money from Hidden Subspaces:
Weizmann Institute, Rehovot, Israel, January 2, 2012; Tel Aviv
University, January 3, 2012; Ben-Gurion University of the Negev,
Beersheva, Israel, January 9, 2012; Hebrew University, Jerusalem,
Israel, January 11, 2012; University of Vienna, Austria, January 30,
2012; University College, London, UK, February 2, 2012; Duke University,
Durham, NC, March 28, 2012; Q+ Hangout on Google+, June 19, 2012; CSAIL Annual Review Meeting, Chatham, MA, June 26, 2012. Another version at CIFAR Meeting, Ottawa, Canada, November 15, 2012
- Problems with Post-Quantum Theories: "Why Quantum Mechanics?" Workshop, Beyond Center, Tempe, Arizona, December 12, 2011
- New Computational Insights from Quantum Optics:
MIT Theory of Computing Colloquium, October 4, 2011; UCLA, October 17,
2011; Princeton Quantum Computing Day, November 1, 2011; University of
Washington CS Theory Seminar, December 9, 2011; Heilbronn Quantum
Algorithms Day, Clifton Hill House, Bristol, UK, February 1, 2012;
University of Edinburgh, Scotland, July 10, 2012; Karles Invitational
Conference, Naval Research Laboratory, Washington DC, August 27, 2012. Shorter version at MIT CSAIL Annual Meeting, Chatham, MA, June 21, 2011
- Permanent and Determinant: MIT Math Club, September 27, 2011
- Prediction, Quantum Mechanics, and Free Will: Work in Progress Seminar, MIT Philosophy Department, September 15, 2011
- Quantum Money, A Progress Report: Microsoft Research New England, Cambridge, MA, June 24, 2011
- The Equivalence of Sampling and Searching:
International Computer Science Symposium in Russia (CSR), St.
Petersburg, June 14, 2011. Also Hebrew University, Jerusalem, Israel,
August 17, 2010; Complexity'2011 Rump Session, San Jose, CA, June 8,
2011
- Quantum Computing and the Limits of the Efficiently Computable:
Buhl Lecture, Department of Physics, Carnegie Mellon University,
Pittsburgh, PA, April 29, 2011; PiTP Lectures on Quantum Phenomena,
University of British Columbia, Vancouver, Canada, February 15, 2012;
Plenary Talk, IEEE Aerospace Conference, Big Sky, Montana, March 4,
2012; Invited Talk at LATIN'2012, Arequipa, Peru, April 16, 2012;
Distinguished Lecture at University of Edinburgh, Scotland, July 13,
2012. Another version at TIBCO, Palo Alto, CA, June 6, 2011. Another version at Tech Seminar, ITA, Cambridge, MA, March 2, 2011. Another version at String Theory Seminar, UC Berkeley,
January 18, 2011.
- The Limits of Computation: Quantum Computers and Beyond:
MIT150 Symposium on "Computation and the Transformation of Practically
Everything", MIT, April 12, 2011. Other versions at CSAIL Industrial
Affiliates Meeting, MIT, May 24, 2011; Computation for Design and
Optimization (CDO) Program Symposium, MIT, March 15, 2012; National
Science Board, Arlington, VA, May 3, 2012; Thomas Jefferson High School
for Science and Technology, Alexandria, VA, May 4, 2012.
- The Territory Around BQP - Results and Open Problems: Workshop on
Conceptual Foundations and Foils for Quantum Information Processing,
Perimeter Institute, Waterloo, Ontario, May 13, 2011.
- The Quantum Money Frontier: xQIT Conference on Difficult Problems in
Quantum Information Theory, MIT, Cambridge, MA, May 3, 2011.
- A Linear-Optical Proof that the Permanent is #P-Complete: Tel-Aviv University, Israel, March 22, 2011.
- The Permanents of Gaussian Matrices: Institute for Advanced Study,
Princeton, NJ, November 29, 2010; Theory Seminar, UC San Diego, January
24, 2011
- The Quest for Quantum Money: Theory Lunch, UC Berkeley,
January 19, 2011
- Resources for Linear-Optics Computation: MIT Quantum Information Group Meeting, November 30, 2010
- The Computational Complexity of Linear Optics:
Barriers in Computational Complexity II, Princeton, NJ, August 28,
2010; Microsoft Research New England, Cambridge, MA, September 22, 2010;
University of Rochester, Rochester, NY, October 18, 2010; JQI Meeting,
University of Maryland, College Park, MD, October 27, 2010; Boston
University, November 12, 2010; Technion, Haifa, Israel, January 4, 2011;
Computer Science Colloquium, UC San Diego, January 24, 2011. Another
version at Perimeter Institute,
Waterloo, Canada, January 25, 2010. Another
version at Southwest Quantum Information and Technology (SQuInT)
Workshop, Santa Fe, NM, February 19, 2010. Another
version at MIT, Quantum Information Science Seminar, April 26, 2010. Another version
at Computational Complexity Workshop, Banff Centre, Banff, Alberta,
August 2, 2010. Another version at iQUiSE Student Lunch, MIT, May 12,
2011.
- Has There
Been Progress on the P vs. NP Question?: MIT CSAIL Student Workshop (Keynote Talk), Endicott House, Beverly, MA, September 26, 2010. Earlier version at Barriers in Computational
Complexity workshop, Center for Computational Intractability, Princeton
University, August 25, 2009. Short version at MIT CSAIL Lunch,
September 27, 2007
- A Counterexample to the Generalized Linial-Nisan Conjecture: A
Sackcloth & Ashes Talk, Complexity Theory Workshop, Banff Centre,
Banff, Alberta, CA, August 3, 2010
- Quantum Complexity Theory: NATO Advanced Summer School in Quantum
Information Processing and Quantum Cryptography, Université de Montréal,
Montreal, Canada, June 24, 2010
- Arthur,
Merlin, and Black-Box Groups in Quantum Computing (Or, How Laci Babai
Did Quantum Stuff Without Knowing It): Combinatorics, Groups,
Algorithms, and Complexity (CGAC), Conference in Honor of Laci Babai's
60th Birthday, Ohio State University, Columbus, OH, March 24,
2010
- New Evidence
that Quantum Mechanics is Hard to Simulate on Classical Computers:
Hebrew University, Jerusalem, Israel, December 30, 2009; Weizmann
Institute of Science, Rehovot, Israel, January 3, 2010; Tel Aviv
University, January 10, 2010. Another version
at QIP'2010, Zürich, Switzerland, January 22, 2010. Short version
at CSAIL Lunch, MIT, December 10, 2009
- Efficient Simulation of Quantum Mechanics Collapses the Polynomial
Hierarchy: Complexity Theory Meeting, Oberwolfach, Germany, November 20,
2009
- BQP Versus
the Polynomial Hierarchy: Schloss Dagstuhl, Wadern, Germany, October
11, 2009; Complexity Theory Meeting, Oberwolfach, Germany, November 19,
2009; Institute for Quantum Computing, Waterloo, Ontario, January 26,
2010. Earlier versions at Princeton University, Center for
Intractability, January 30, 2009; Kavli Institute for Theoretical
Physics, University of California, Santa Barbara, September 22, 2009. Conference version
at ACM STOC'2010, Cambridge, MA, June 6, 2010.
- Quantum
Money: University of Washington CS theory seminar, Seattle, WA,
September 29, 2009; Dartmouth College computer science colloquium,
Hanover, NH, October 21, 2009; Perimeter Institute colloquium, Waterloo,
Ontario, January 27, 2010
- How Much
Information Is In A Quantum State?: Kavli Institute for Theoretical
Physics, University of California, Santa Barbara, September 24, 2009;
Applied Math and Computational Science Colloquium, University of
Pennsylvania, Philadelphia, December 4, 2009; Hebrew University,
Jerusalem, Israel, December 31, 2009; What Is Information? Workshop, Sde Boker, Israel (via live videoconference), January 7, 2013. Another version
at Physics Colloquium, ETH, Zürich, Switzerland, May 27, 2009. Short version
at CSAIL Annual Meeting, American Academy of Arts and Sciences,
Cambridge, MA, June 29, 2009; FQXi Conference on Foundational Questions
in Physics and Cosmology, Ponta Delgada, Azores, Portugal, July 8, 2009. Another version at American Physical Society Annual Meeting, Boston, MA, March 1, 2012; University of Edinburgh, Scotland, July 11, 2012.
- Quantum
Copy-Protection and Quantum Money: CCC'2009, Paris, France, July 17,
2009. Another
version at QIP, New Delhi, India, December 20, 2007. Other versions
at ETH, Zürich, Switzerland, May 26, 2009; 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
- Quantum
Complexity and Fundamental Physics: Quantum Information Science
Workshop, Vienna, VA, April 23, 2009. Another version
at NIST Colloquium, Gaithersburg, MD, May 29, 2009. Another version at
AAAS Annual Meeting, Vancouver, Canada, February 18, 2012.
- On the Need for Structure in Quantum Speedups: UC Berkeley Quantum
Computing Seminar, April 21, 2009
- The Limits of
Quantum Advice: MIT, March 16, 2009. Another version
at UC Berkeley Theory Seminar, April 20, 2009; CWI, Amsterdam,
Netherlands, January 12, 2010. Earlier versions at University of
Chicago CS theory seminar, January 9, 2009; Institute for Advanced
Study, Princeton, January 26, 2009. Short version
at QIP'2010, Zürich, Switzerland, January 18, 2010.
- Closed Timelike
Curves Make Quantum and Classical Computers Equivalent: QIP'09,
Santa Fe, New Mexico, January 15, 2009; iQUiSE lunch, MIT, January 23,
2009; Quantum Theory and Symmetries meeting, Lexington, Kentucky, July
21, 2009. Earlier versions at Complexity'2006, Prague, Czech Republic,
July 18, 2006; FQXi Conference on Foundational Questions in Physics and
Cosmology, Reykjavik, Iceland, July 24, 2007
- When Qubits
Go Analog: xQIT workshop, MIT, November 19, 2008. Another version
at CCC'08, College Park, MD, June 23, 2008
- The Past and Future of Closed Timelike Curves: MIT Math Club,
October 30, 2008
- Pretty-Good
Tomography, workshop on Quantum Estimation: Theory and Practice,
Perimeter Institute, Waterloo, Ontario, August 26, 2008
- The Complexity of Boolean Functions: Mini-course at MathCamp 2008,
Portland, OR, July 15-19, 2008
- 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
- 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; Penn State CS Colloquium,
November 10, 2008; City College of New York (CCNY) Physics Colloquium,
November 12, 2008. Another version
at National Science Foundation CISE Distinguished Lecture Series,
Arlington, VA, March 23, 2009; University of Virginia Computer Science
Colloquium, Charlottesville, VA, March 26, 2009. Short version at
Gathering for Gardner, Atlanta, Georgia, March 27, 2008; MIT, June 5,
2008; MIT, April 2, 2009
- 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
- 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]