- PAC-Learning and Reconstruction of Quantum States: Plenary Talk, COLT'2017, Amsterdam, Netherlands, July 7, 2017

- The Church-Turing Thesis and Physics: Plenary Talk, Computability in Europe (CiE) 2017, Turku, Finland, June 13, 2017

- A New Theorem on Batch Quantum State Tomography: IQIM Group Meeting, Caltech, February 8, 2017; MIT Quantum Information Group Meeting, Cambridge, MA, June 30, 2017

- The Collatz 3x+1 Problem, A Lecture That Will Hopefully Terminate Eventually: Saturday Morning Math Group, University of Texas, Austin, January 28, 2017

- Quantum Computing and the Interpretation of Quantum Mechanics: École Normale Supérieure de Lyon, France, December 13, 2016

- The Circuit Complexity of Detecting Macroscopic Superpositions: It from Qubit Collaboration Annual Meeting, Simons Foundation, New York, NY, December 8, 2016; It from Qubit Complexity Workshop, Stanford University, March 20, 2017

- AdS/CFT and Computational Complexity: High-Energy Theory Seminar, Physics Department, University of Texas, Austin, TX, November 29, 2016; High-Energy Physics Informal Seminar, Caltech, February 8, 2017

- Quantum Computing: Keynote Talk, UTCS 50
^{th}Anniversary Celebration, University of Texas, Austin, TX, October 28, 2016; Distinguished Lecture, University of Oregon, Eugene, OR, November 17, 2016; Turing Scholars, University of Texas, Austin, TX, November 30, 2016; G Research Lecture, London, UK, December 12, 2016; Claude Bernard University, Lyon, France, December 14, 2016. Another version at Austin Quantum Computing Meetup, Bazaarvoice, Austin, TX, May 24, 2017

- A Theorem About Recombinase-Based State Machines: Lieberman-Aiden Lab, Baylor College of Medicine, Houston, TX, October 21, 2016

- Quantum Supremacy: Office of Science and Technology Policy QIS Forum, Eisenhower Executive Office Building, White House Complex, Washington DC, October 18, 2016. Another version at UTCS Faculty Lunch, October 26, 2016. Another version at UT Austin Physics Colloquium, Austin, TX, November 9, 2016.

- Avi's Permanent Impact On Me: Avi Wigderson's 60th Birthday Conference, Institute for Advanced Study, Princeton, NJ, October 5, 2016

- The Complexity and Computability Theory of Time Travel: UT Austin Theory of Computing Colloquium, Austin, TX, August 26, 2016. Another version at Workshop on Computational Complexity and High Energy Physics, University of Maryland, College Park, MD, August 31, 2017

- Did Einstein Kill Schrödinger's Cat?: Panel discussion at New York Academy of Sciences (with Daniel Harlow and Brian Swingle), June 29, 2016

- Quantum Computing: National Youth Science Camp, Bartow, West Virginia, June 23, 2015. Another version at National Youth Science Camp, Bartow, West Virginia, June 24, 2016. Another version at Explore UT Day, UT Austin, March 4, 2017. Another version at Women in Computer Science Club, LASA High School, Austin, TX, March 29, 2017; Student ACM Chapter, UT Austin, April 18, 2017. Another version at Lakeway Men's Breakfast Club, Austin, TX, April 19, 2017

- Quantum Supremacy: Strachey Lecture, University of Oxford, UK, May 24, 2016. Another version at Quarc Meeting, Microsoft Research, Redmond, WA, July 15, 2016; Semi-Quantum Computing Workshop, Institute for Quantum Computing, Waterloo, Canada (via videoconference), August 17, 2016. Another version at Banff Complexity Theory Workshop, Banff, Canada, September 8, 2016. Another version at CS Theory Seminar, Tel Aviv University, Israel, December 20, 2016. Another version at Physics of the Universe Summit (POTUS), SpaceX, Hawthorne, CA, January 7, 2017; Babushka Forum, Institute for Computational Engineering and Sciences, University of Texas, Austin, January 27, 2017. Another version at Physics Colloquium, Caltech, Pasadena, CA, February 9, 2017. Another version at Southwest Quantum Information Technology (SQuInT) Conference, Louisiana State University, Baton Rouge, LA, February 25, 2017. Another version at UC Santa Barbara CS Department, Distinguished Spring Colloquium, Santa Barbara, CA, May 26, 2017; CWI, Amsterdam, Netherlands, July 10, 2017; IBM T. J. Watson Research Center, Yorktown Heights, NY, July 28, 2017. Another version at Workshop on Quantum Computational Supremacy, Bristol, UK, August 16, 2017

- Can Computers Become Conscious?: Seven Pines Symposium "Big questions: some fundamental problems in physics," Stillwater, MN, May 14, 2016

- The P Versus NP Problem: Keynote Talk, Hudson River Undergraduate Mathematics Conference, Saint Michael's College, Colchester, VT, April 2, 2016; École Normale Supérieure de Lyon, France, December 15, 2016

- Complexity-Theoretic Foundations of Quantum Supremacy Experiments: Quantum Algorithms Workshop, Aspen Center for Physics, Aspen, CO, March 25, 2016

- The Complexity of States and Unitary Transformations: From Quantum Money to Black Holes, course at Bellairs Research Institute, Holetown, Barbados, February 21-25, 2016

- Recent Results in Quantum Query Complexity: Is Grover the Best Possible?, CS theory seminar, Hebrew University, Jerusalem, Israel, January 13, 2016

- Explorations in Universality: Ada Lovelace Bicentenary Lecture on Computability, Hebrew University, Jerusalem, Israel, December 31, 2015; CS Theory Seminar, Tel Aviv University, Tel Aviv, Israel, January 5, 2016

- The Largest Possible Quantum Speedups: ThinkQ Workshop, IBM T.J. Watson Research Center, Yorktown Heights, NY, December 2, 2015; Physics Colloquium, Technion, Haifa, Israel, January 4, 2016; TCS+ online seminar, January 20, 2016

- The Unconscious Expander: Workshop on Integrated Information Theory, NYU, New York, NY, November 13, 2015

- Computational Complexity and Fundamental Physics: IST Lecture, IST, Klosterneuberg, Austria, October 21, 2015; Public Lecture, Wheeler Opera House, Aspen, CO, March 23, 2016; Colloquium, Renaissance Technologies, Setauket, NY, April 19, 2016

- Can computer science help physicists resolve the firewall paradox?: ScienceWriters2015, MIT, Cambridge, MA, October 11, 2015

- Permanents of Gaussian Matrices: MIT Math Club, September 10, 2013; Harvard University Probability Seminar, September 16, 2015; University of Chicago Math Colloquium, Chicago, IL, October 15, 2015; Geometry and Analysis Joint Seminar, Math Department, Texas A&M University, College Station, TX, March 10, 2017

- Separations in Quantum Query Complexity: Centre for Quantum Technologies, National University of Singapore, August 21, 2015

- Common Knowledge and Aumann's Agreement Theorem: SPARC summer camp on applied rationality, Berkeley, CA, August 14, 2015. Another version at ESPR summer camp on applied rationality, London, UK, August 19, 2017

- Black Holes, Firewalls, and the Complexity of States and Unitaries: Perimeter Institute, Waterloo, Ontario, Canada, May 27, 2015; Centre for Quantum Technologies Colloquium, National University of Singapore, August 20, 2015; Oxford OASIS Seminar, University of Oxford, May 25, 2016. Another version as plenary talk at 2015 Asian Quantum Information Science (AQIS) conference, Seoul, South Korea, August 25, 2015. Another version at Workshop on the Frontiers of Quantum Information and Computer Science, University of Maryland, College Park, MD, September 30, 2015. Another version at Geometry Seminar, Department of Mathematics, UT Austin, Austin, TX, September 22, 2016

- What More Than Turing-Universality Do You Want?: Beyond Center Workshop on Nature as Computation, Tempe, AZ, May 4, 2015. Another version at CSAIL Review Meeting, Harwich, MA, June 29, 2015

- How Pervasive Is Incompleteness?: George Washington University, Washington DC, April 3, 2015

- The Classification of Reversible Bit Operations: UT Austin CS Theory Seminar, Austin, TX, March 4, 2015; MIT Undergraduate Math Association, Cambridge, MA, March 10, 2015; UC Berkeley CS Theory Seminar, Berkeley, CA, August 14, 2015

- Exploring the Limits of the Efficiently Computable: University of Maryland CS Department, College Park, MD, February 20, 2015. Another version at UT Austin CS Department, Austin, TX, March 3, 2015; University of Michigan CS Department, College Park, MD, April 13, 2015. Another version at Princeton CS Department, Princeton, NJ, April 29, 2015. Another version at University of Waterloo CS Department, Waterloo, Ontario, Canada, May 26, 2015; University of Illinois Urbana-Champaign CS Department, Urbana-Champaign, IL, May 28, 2015; Rutgers University, Piscataway, NJ, June 2, 2015

- Computational Phenomena in Physics: Lens of Computation on the Sciences Conference, Institute for Advanced Study, Princeton, NJ, November 22, 2014

- When Exactly Do Quantum Computers Provide A Speedup?: Yale Quantum Institute Seminar, Yale University, New Haven, CT, October 10, 2014. Another version at UT Austin Physics Colloquium, Austin, TX, November 19, 2014; Applied and Interdisciplinary Mathematics Seminar, Northeastern University, Boston, MA, November 25, 2014; Hebrew University Physics Colloquium, Jerusalem, Israel, January 5, 2015; Computer Science Colloquium, Technion, Haifa, Israel, January 8, 2015; Stanford University Physics Colloquium, January 27, 2015

- Could A Quantum Computer Have Subjective Experience? Quantum Foundations of a Classical Universe workshop, IBM TJ Watson Research Center, Yorktown Heights, NY, August 13, 2014

- The Computational Power of Charles's Digi-Comp II (plus embedded video): CSAIL Annual Review Meeting, Wild and Crazy Ideas Session, Harwich, MA, June 24, 2014

- A Question About Quantum Finite Automata: CCC'2014 Rump Session, Vancouver, British Columbia, June 11, 2014. Earlier version at Complexity Theory Meeting, Banff Centre, Banff, Alberta, Canada, July 9, 2013

- AM with Multiple Merlins: CCC'2014, Vancouver, British Columbia, June 11, 2014. Earlier version at Complexity Theory Meeting, Banff Centre, Banff, Alberta, Canada, July 9, 2013

- Quantum Computing and Fundamental Physics: Computing the Future MAC'50 Symposium, MIT CSAIL, Cambridge, MA, May 28, 2014

- God Indeed Plays Dice (What You Need to Know About Quantum Mechanics): Leading Jewish Minds Lunchtime Seminar Series, MIT Hillel, Cambridge, MA, April 25, 2014

- Forrelation: A Problem that Optimally Separates Quantum from Classical Computing: Aspen Winter Conference on Advances in Quantum Algorithms, Aspen Center for Physics, Aspen, CO, March 14, 2014. Another version at UT Austin Theory of Computing Seminar, Austin, TX, November 21, 2014; Hebrew University CS Theory Seminar, Jerusalem, Israel, December 31, 2014; Weizmann Institute Foundations of Computer Science Seminar, Rehovot, Israel, January 4, 2015; Tel Aviv University CS Theory Seminar, Tel Aviv, Israel, January 6, 2015; EPFL, Lausanne, Switzerland, January 16, 2015; Stanford University CS Theory Seminar, January 29, 2015. Conference version at STOC'2015, Portland, Oregon, June 16, 2015

- Verification of BosonSampling Devices: Simons Institute Workshop on Quantum Games and Protocols, UC Berkeley, Berkeley, CA, February 28, 2014

- Remarks on the Physical Church-Turing Thesis: FQXi International Conference on the Physics of Information, Vieques Island, Puerto Rico, January 7, 2014. Click here for video.

- Complexity Theory and Quantum Optics: Mini-course at Instituto de Física, Universidade Federal Fluminense (UFF), Niterói, Rio de Janiero State, Brazil, December 16-20, 2013. Lecture notes by Ernesto Galvăo and others. Another version at the 31st Jerusalem Winter School in Theoretical Physics, Hebrew University, Jerusalem, Israel, December 30, 2013 - January 2, 2014. Click here for video.

- On the Computational Complexity of Decoding Hawking Radiation: Quantum Information Group Meeting, MIT, Cambridge, MA, November 15, 2013; Bulk Microscopy from Holography and Quantum Information Meeting, Princeton Center for Theoretical Science (PCTS), Princeton University, November 23, 2013; COST-WIS Workshop on Black Holes and Quantum Information, Weizmann Institute of Science, Rehovot, Israel, January 12, 2014; iQUiSE Lunch, MIT, February 13, 2014; QuICS Workshop on Quantum Information and Computer Science, University of Maryland, East Hyattsville, MD, March 31, 2014; CSAIL Research Spotlight, MIT, Cambridge, MA, September 11, 2014. Click here for video.

- BosonSampling: BBN Technologies, Cambridge, MA, October 30, 2013; IEEE Photonics Society Quantum Optics/Engineering Workshop, MIT Lincoln Laboratory, Lexington, MA, April 30, 2014. Another version at Stanford Institute for Theoretical Physics, Stanford, CA, February 21, 2014. Another version at Kick-Off Workshop for Optimal Quantum Measurements for Scalable Quantum Technologies, MIT, Cambridge, MA, April 18, 2014. Another version at UT Austin Complex Quantum Systems Seminar, Austin, TX, November 20, 2014. Another version as plenary talk at International Conference on Mathematical Physics (ICMP), Santiago, Chile, July 29, 2015

- The Kind of Stuff I Think About: LIDS (Laboratory for Information and Decision Systems) Lunch, MIT, October 29, 2013

- Computational Complexity and Physics: Clay Research Conference, Mathematical Institute, University of Oxford, UK, October 3, 2013

- Computational Complexity Underpinnings of the Harlow-Hayden Argument: Complementary, Fuzz, or Fire Workshop, Kavli Institute for Theoretical Physics, Santa Barbara, CA, August 22, 2013

- From EPR to BQP: Quantum Computing as 21
^{st}-Century Bell Violation: Invited Talk, CQIQC Conference (50 Years of Violating Inequalities), University of Toronto, Canada, August 16, 2013

- Private-Key Quantum Money: Invited Talk, QCrypt'2013, Waterloo, Canada, August 8, 2013

- Quantum Mechanics: What's It Good For?: Microsoft Faculty Summit, Redmond, WA, July 16, 2013

- The Collision Lower Bound After 12 Years: QStart Conference, Institute for Advanced Studies, Hebrew University, Jerusalem, Israel, June 25, 2013

- P versus NP: Villefranche Meeting, Cap Estel, France, June 11, 2013

- Quantum Computing and Information Tutorial: Information Theory Summer School, Purdue University, West Lafayette, Indiana, June 4, 2013

- So You Think Quantum Computing Is Bunk?: Microsoft Research New England Colloquium, Cambridge, MA, April 10, 2013

- Hidden Variables as Fruitful Dead Ends: From Monopoles to Fault-Tolerant Quantum Computation (Conference in Honor of John Preskill's 60
^{th}Birthday), Caltech, Pasadena, CA, March 15, 2013

- Superiority of the Latke: The Unexpected Convergence of Quantum Mechanics and Common Sense: MIT Annual Latke-Hamentashen Debate, February 6, 2013

- Quantum Information and the Brain: Invited Talk at NIPS 2012, Stateline (Lake Tahoe), NV, December 4, 2012. Another version at Moses Seminar, MIT, December 7, 2012

- Proving Without Explaining, And Verifying Without Understanding: Symposium on the Nature of Proof, University of Pennsylvania, Philadelphia, PA, November 9, 2012

- Hawking Quantum Wares at the Classical Complexity Bazaar: JQI Workshop on Quantum Information Science in Computer and Natural Sciences, University of Maryland, College Park, September 29, 2012

- The Ghost in the Quantum Turing Machine: Yakir Aharonov 80
^{th}Birthday Conference, Chapman University, Anaheim, CA, August 17, 2012

- The Coffee Automaton: Quantifying the Rise and Fall of Complexity in Closed Systems: Philosophy of Cosmology Meeting, Florence, Italy, July 26, 2012; also Hebrew University, Jerusalem, Israel, July 18, 2012.

- 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, Harwich, 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, Harwich, 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

- A Scientifically-Supportable Notion of Free Will In Only 6 Controversial Steps: The Looniest Talk I've Ever Given In My Life: Setting Time Aright (FQXi Conference), Copenhagen, Denmark, August 31, 2011

- Quantum Money, A Progress Report: Microsoft Research New England, Cambridge, MA, June 24, 2011

- Causal Computational Learning Theory: Wild And Crazy Ideas Session (WACI), MIT CSAIL Annual Meeting, Harwich, MA, June 21, 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; D. E. Shaw and Company, New York, NY, November 25, 2013; American Physical Society Editorial Offices, Ridge, NY, November 26, 2013; University of Maryland Physics Colloquium, College Park, MD, April 1, 2014. 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. Another version at Physics Colloquium, University of Illinois Urbana-Champaign, October 23, 2013. Another version at Sidney Pacific Distinguished Lecture Series, MIT, Cambridge, MA, November 14, 2013; Optimizely, San Francisco, CA, March 7, 2014; Mathematics and Statistics Seminar, University of North Carolina, Greensboro, April 28, 2014. Another version at the Cornell Computer Science 50th Anniversary Celebration, Cornell University, Ithaca, NY, October 2, 2014. Another version at CERN Colloquium, Meyrin, Switzerland, January 15, 2015. Another version at String Theory Seminar, UC Berkeley, January 18, 2011. Another version at UT Austin Dean's Scholars Distinguished Lecture, March 2, 2015. Another version at Unspeakable Talk Series, Singapore Science Centre, August 19, 2015. Another version at Industrial Liaison Program, MIT, September 16, 2015. Another version for Computer Science Colloquium, Rice University, Houston, TX, October 20, 2016. Another version as Plenary Talk, Information Theory and Applications (ITA), San Diego, CA, February 13, 2017

- 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. Another version for SuperUROP Presentation, MIT, Cambridge, MA, September 25, 2014. Another version for American Association for the Advancement of Science Annual Meeting, Boston, MA, February 19, 2017

- 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.

- Quantum Computing with Noninteracting Bosons: Symposium for Michael Freedman's 60
^{th}Birthday, Kavli Institute for Theoretical Physics, Santa Barbara, CA, April 16, 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

- Toiling in Feynman's Shadow: Quantum Computing and the Limits of the Efficiently Computable: TEDxCaltech, Pasadena, CA, January 14, 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

- Solving Hard Problems With Light: CSAIL Industrial Affiliates Meeting, MIT, May 26, 2010

- Quantum Computing With Closed Timelike Curves: New Directions in the Foundations of Physics, MAA Carriage House, Washington DC, May 1, 2010

- The Future of Computer Science, and Why Every Other Major Sucks By Comparison: Winning talk at the Professor Talent Show, MIT Campus Preview Weekend, April 10, 2010. Also Professor Talent Show, MIT Campus Preview Weekend, April 9, 2011.

- 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
60
^{th}Birthday, Ohio State University, Columbus, OH, March 24, 2010

- Generating Random Stabilizer States: A Theorem in Search of an Application, QIP'2010, Zürich, Switzerland, January 20, 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

- Impagliazzo's Worlds in Arithmetic Complexity: Workshop on Complexity and Cryptography: Status of Impagliazzo's Worlds, Center for Computational Intractability, Princeton, NJ, June 5, 2009

- 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

- The Polynomial Method in Quantum and Classical Computing: Tutorial at FOCS 2008, Philadelphia, PA, October 25, 2008. Another version at MIT Math Club, February 26, 2009

- Pretty-Good Tomography, workshop on Quantum Estimation: Theory and Practice, Perimeter Institute, Waterloo, Ontario, August 26, 2008

- How to Solve Longstanding Open Problems in Quantum Computing Using Only Fourier Analysis, workshop on Analytic Tools in Computational Complexity, Banff Centre, Banff, Canada, August 5, 2008

- The Complexity of Boolean Functions: Mini-course at MathCamp 2008, Portland, OR, July 15-19, 2008

- The Power of Unentanglement: CCC'2008, College Park, Maryland, June 25, 2008

- An Invitation to Quantum Complexity Theory: QIP, New Delhi, India, December 17, 2007

- Quantum Double Feature: NYU Theory Day, Courant Institute of Mathematical Sciences, December 7, 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

- 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

- Experimental Complexity Theory: "Wild Ideas Session," MIT CSAIL Annual Meeting, Harwich, MA, June 26, 2007

- Quantum Versus Classical Proofs and Advice: Complexity'2007, San Diego, CA, June 14, 2007; NEC Quantum Computing Workshop, Princeton, NJ, September 21, 2007

- 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

- Computational Intractability as a Law of Physics: Caltech Physics Colloquium, January 18, 2007; University of Chicago, March 7, 2007; Princeton Physics Department, March 9, 2007; Clarkson University, November 12, 2007

- Computational Complexity and the Anthropic Principle: Stanford Institute for Theoretical Physics, December 15, 2006

- Pseudorandom States: Perimeter Institute, October 30, 2006

- What Have I Learned From Physicists/Computer Scientists And What Else Would I Like to Learn From Them? (joint with Dave Bacon): Royal Society, London, October 13, 2006. Also see the opening skit

- 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

- QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols: Complexity'2006, Prague, Czech Republic, July 19, 2006

- 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

- What Google Won't Find: The Ultimate Physical Limits of Search: Google, Mountain View, CA, August 24, 2005; Google, Cambridge, MA, August 17, 2007

- 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

- The Amazing Power of Postselection: QIP 2005, MIT, January 17, 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

- Limitations of Quantum Advice and One-Way Communication: IEEE Complexity 2004, Amherst, MA, June 24, 2004; Institute for Quantum Computing, University of Waterloo, July 6, 2004. Earlier version at UC Berkeley, November 21, 2003

- 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

- Limits on Efficient Computation in the Physical World: Dissertation Talk, UC Berkeley, April 26, 2004. Also Institute for Advanced Study, Princeton, October 28, 2004; Perimeter Institute, March 15, 2006

- Quantum Computing and Hollywood: San Jose State University Computer Science Colloquium, April 15, 2004

- Is Quantum Mechanics An Island In Theoryspace?: UC Berkeley Quantum Reading Group, April 2, 2004

- Improved Simulation of Stabilizer Circuits: UC Berkeley Quantum Computing Seminar, March 9, 2004. Earlier version at UC Berkeley, December 10, 2003

- Quantum Polynomial Time and the Human Condition: GRC Quantum Information Workshop, Ventura, CA, February 23, 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

- The Complexity of Sampling Histories: Perimeter Institute, August 5, 2003

- BQP/qpoly Is Contained In EXP/poly: IEEE Complexity 2003, Ĺrhus, Denmark, July 8, 2003; UC Berkeley Theory Lunch, October 1, 2003

- 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

- Cosmology and Complexity Classes: MIT Center for Theoretical Physics, March 18, 2003; quantum computing seminar, UC Berkeley, March 11, 2003

- Is P Versus NP Formally Undecidable?: UC Berkeley, February 14, 2003

- Why 3 Dimensions?: New Hope-Solebury high school, January 8, 2003

- The Prime Facts, From Euclid To AKS: New Hope-Solebury middle school, January 7, 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).

- The Future (and Past) of Quantum Lower Bounds by Polynomials: Workshop on Algebraic Methods in Quantum and Classical Models of Computation, Schloss Dagstuhl, Wadern, Germany, October 17, 2002

- Quantum Certificate Complexity: IEEE Complexity 2003, Ĺrhus, Denmark, July 8, 2003. Earlier version at MSRI, Berkeley, October 1, 2002

- Quantum Lower Bounds You Haven't Seen Before: MSRI Workshop on Quantum Algorithms and Complexity, Banff Centre, Banff, Canada, September 24, 2002

- 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 Computing for High School Students: New Hope-Solebury high school, June 3, 2002

- Computation, Quantum Theory, and You: qual exam talk, UC Berkeley, May 13, 2002

- Quantum Computing: What's It Good For?: Avaya Labs, Tel Aviv, January 10, 2002

- 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

- Stylometric Clustering: University of Toronto, March 30, 2000

- Quantum Computing and AI: Cornell AI seminar, October 20, 1999

- The Mathematics of RoboSoccer: Cornell Mathematics Club, September 29, 1999

- Optimal Demand-Oriented Topology for Hypertext Systems: ACM SIGIR'97, July 29, 1997; Bell Labs Database Seminar, August 5, 1997; Cornell AI Seminar, April 29, 1998

**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.