Talks
Important Note:
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.
- Watermarking, Where To?: Workshop on Alignment, Trust, Watermarking, and Copyright Issues in LLMs, Simons Institute, Berkeley, CA, October 17, 2024
- Quantum Computing, Between Hope and Hype: US-India Workshop on Post-Quantum Cryptography, UCLA, Los Angeles, CA, September 16, 2024
- AI Safety and Theoretical Computer Science: Computer Science Colloquium, Oxford University, Oxford, UK, May 31, 2024; Computer Science Colloquium, Tel Aviv University, Tel Aviv, Israel, June 9, 2024; Computer Science Colloquium, Hebrew University, Jerusalem, Israel, June 17, 2024
- Circuit Conspiracies: Workshop on Near-Term Quantum Computers: Fault Tolerance + Benchmarking + Quantum Advantage + Quantum Algorithms, Simons Institute, Berkeley, CA, April 25, 2024
- Quantum Circuit Complexity II: Holography Journal Club, Physics Department, UT Austin, Austin, TX, April 5, 2024
- Quantum Circuit Complexity: Brown Bag Seminar, High-Energy Physics Group, UT Austin, Austin, TX, January 18, 2024
- The Future of Quantum Supremacy Experiments, Q2B Conference, Santa Clara, CA, December 5, 2023. Another version as Students' Choice Physics Colloquium, Arizona State University, Tempe, AZ, February 8, 2024
- Neurocryptography and AI Alignment: Natural Philosophy Forum Special Seminar, Johns Hopkins University, Baltimore, MD, October 4, 2023. Another version at Johns Hopkins Applied Physics Laboratory, Laurel, MD, October 6, 2023; Tom Goldstein Group Meeting, Computer Science Department, University of Maryland, College Park, MD, October 6, 2023. Another version at Mathematics Department, Stanford University, Stanford, CA, October 26, 2023; Atsec Crypto Module Bootcamp, Concordia University, Austin, TX, February 27, 2024
- The Computational Expressive Power of Two Children's Toys: UT Austin Undergraduate Math Club, Austin, TX, September 19, 2023
- What I'd Like Government Officials to Know About Near-Term Applications of Quantum Computing, Bureau of Intelligence and Research, US State Department (online), September 7, 2023
- Neurocryptography, Invited Plenary Talk at Crypto'2023, UCSB, Santa Barbara, CA, August 23, 2023
- Watermarking of Large Language Models, Workshop on Large Language Models and Transformers, Simons Institute, UC Berkeley, August 17, 2023; another version at Theory Colloquium, UT Austin, September 15, 2023; another version at Anthropic, San Francisco, CA, October 13, 2023; Responsible Machine Learning Summit, UCSB, Santa Barbara, CA, October 20, 2023
- Quantum Information Supremacy, Park City Math Institute (PCMI), Park City, Utah, July 27, 2023
- Verifiable NISQ Experiments: What I Hope Will Be Done, Quantum Summer Cluster Workshop, Simons Institute, UC Berkeley, Berkeley, CA, July 10, 2023; another version at IPAM CQC Program, UCLA, Los Angeles, CA, September 11, 2023; University of Tennesee, Knoxville, TN, November 29, 2023 (via Zoom); IBM T. J. Watson Research Center, Yorktown Heights, NY, August 6, 2024
- A Few Directions for Verifiable NISQ Experiments, NISQAH, Neve Ilan, Israel, June 7, 2023. Another version at Weizmann Institute of Science, Rehovot, Israel, June 12, 2023. Another version at Physics Department, Technion, Haifa, Israel, June 14, 2023. Another version at Park City Mathematics Institute (PCMI), Park City, Utah, July 25, 2023.
- Reform AI Alignment, CryptoXai.wtf, Zuzalu, Montenegro (via Zoom), May 7, 2023. Another version at Park City Math Institute (PCMI), Park City, Utah, July 28, 2023. Another version at Grand Opening of Institute for Foundations of Data Science, Yale University, New Haven, CT, September 22, 2023. Another version at Woodside High School, CA, February 16, 2024. Another version at EA Global X, Austin, TX, March 14, 2024
- Leaning Into Uninterpretability for AI Alignment, Alignment Workshop, OpenAI, San Francisco, CA, February 28, 2023; another version at Harvard AI Safety Team, Harvard University, Cambridge, MA, March 10, 2023
- Near-Term Quantum Advantage: Winter School on Contemporary Quantum Algorithms and Applications, Institute for Pure and Applied Mathematics (IPAM), UCLA, Los Angeles, CA, February 24, 2023
- How Much Information Is In A Quantum State?, CU Boulder Physics Colloquium, Boulder, CO, February 22, 2023. Another version at Computer Science Distinguished Lecture, Harvard University, Cambridge, MA, March 9, 2023; RIKEN Center for Quantum Computing, Japan (via Zoom), May 16, 2023.
- Watermarking GPT Outputs, OpenAI, San Francisco, CA, December 13, 2022. Another version at UT Austin Math Club, Austin, TX, October 18, 2022
- AI Safety, UT Austin Effective Altruist Club, Austin, TX, November 14, 2022. Another version at UT Austin ACM Chapter, Austin, TX, February 8, 2023. Another version at UT Austin Institute for Foundations of Machine Learning (IFML), Austin, TX, April 13, 2023.
- Discrete Bulk Reconstruction, Mathematical Physics Seminar, Rutgers University, Piscataway, NJ (via Zoom), July 6, 2022; Holography Seminar, UT Austin (via Zoom), September 16, 2022. Another version at IAS Workshop on Spacetime and Quantum Information, Princeton, NJ, December 7, 2022; UT Austin CS Theory Seminar, Austin, TX, January 13, 2023
- Recent Progress in Quantum Advantage, Quantum and Lattices Joint Reunion Workshop, Simons Institute, Berkeley, CA, June 13, 2022. Another version at NSF Workshop on Quantum Advantage and Next Steps, University of Chicago, IL, August 1, 2022; Another version at CQIQC, Fields Institute, Toronto, August 31, 2022
- How Much Structure Is Needed for Huge Quantum Speedups?, 28th Solvay Conference on Physics of Quantum Information, Brussels, Belgium, May 21, 2022; another version at ASC Colloquium, LMU, Munich, Germany (via Zoom), June 1, 2022
- On Quantum Computational Supremacy: Invited Lecture, 3rd International Symposium on Quantum Physics and Quantum Information Sciences (QPQIS), Beijing, China (virtual), December 1, 2021
- Why Philosophers Should Care About Computational Complexity: University of Pennsylvania Philosophy and Statistics Reading Group (via Zoom), July 20, 2021
- BQP After 28 Years: Invited Talk at Conference on Theory of Quantum Computation, Communication, and Cryptography (TQC'2021) (via Zoom), July 8, 2021; Invited Talk at FSTTCS, India (via Zoom), December 16, 2021; more recent version as Munich Center for Quantum Science and Technology (MCQST) Colloquium, Munich, Germany (via Zoom), April 26, 2022
- Favorite Open Problems Related to Quantum Query Complexity: TQC (via Zoom), Riga, Latvia, July 5, 2021
- Quantum Algorithms in 1 Hour: USACO Summer Camp (virtual), June 2, 2021
- Reflections on Quantum Computational Supremacy: VBFF Spring Review Meeting (virtual), May 21, 2021
- Quantum Supremacy: What It Does and Doesn't Mean: Oxford Scientific Society (via Zoom), May 6, 2021
- Quantum Computing: Beyond the Hype: WorldQuant (via Zoom), May 4, 2021
- The Zen Anti-Interpretation of Quantum Mechanics: Harvard University Philosophy of Physics Seminar (via Zoom), March 31, 2021
- Quantum Supremacy via BosonSampling, Theory and Practice: Quantum Colloquium Series, Simons Institute, Berkeley, CA (via Zoom), February 9, 2021; iQUiSE Seminar, MIT, Cambridge, MA (via Zoom), April 8, 2021
- Quantum Computational Supremacy: Schaffhausen Institute of Technology (SIT) Insights in Technology Conference (via Zoom), December 16, 2020; Distinguished Lecture, FCT Universidade Nova de Lisboa, Lisbon, Portugal (via Zoom), January 26, 2021; UT San Antonio (via Zoom), February 24, 2021; Physics Colloquium, UC San Diego (via Zoom), March 11, 2021; Physics and Astronomy Colloquium, University of Utah (via Zoom), March 23, 2021; Symposium on Frontiers in Quantum Information Science and Technology, Ohio State University (via Zoom), April 23, 2021; Quantum Science Seminar (via Zoom), May 20, 2021; Army Research Office (via MS Teams), June 7, 2021; OneQuantum Africa, Zimbabwe (via Zoom), June 23, 2021
- Quantum Computing: Fact vs. Fiction: Chicago Quantum Summit (via Zoom), November 12, 2020; SparkCognition (via Zoom), March 24, 2021; LASA High School, Austin, TX (via Zoom), April 12, 2021; ECESCON 12, Thessaloniki, Greece (via Zoom), April 23, 2021; National Grid (online), September 24, 2021
- The Busy Beaver Frontier: UT Austin Undergraduate Math Club (via Zoom), September 29, 2020; UC Davis Algebra and Discrete Mathematics Seminar / CS Colloquium (via Zoom), October 15, 2020; Rutgers University Math Colloquium, February 9, 2022
- Shadow Tomography of Quantum States: Progress and Prospects: IBM Informational Lens Workshop (held via Zoom), September 29, 2020; Quantum Information Group, Universitat Autonoma de Barcelona (UAB), Spain (via Zoom), December 3, 2020; Tripartite Quantum Colloquium, UBC, Vancouver, BC (via Zoom), July 28, 2021
- From Archimedes to Quantum Supremacy: Saturday Morning Math Group, University of Texas, Austin, TX, March 8, 2020; Picture Language Seminar, Department of Mathematics, Harvard University (via Zoom), May 26, 2020
- Mathematical Aspects of Quantum Supremacy Experiments: University of Houston Math Department, Houston, TX, February 19, 2020
- Thoughts and Open Problems About Random Circuit Sampling: Quantum Wave Bootcamp, Simons Institute, Berkeley, CA, January 31, 2020
- The Necromancy-Hardness of the Schrödinger's Cat Experiment: PiQuDos (Quantum Foundations Seminar), Perimeter Institute, Waterloo, Ontario, January 29, 2020
- Quantum Computational Supremacy And Its Applications: Perimeter Institute Colloquium, Waterloo, Ontario, January 29, 2020. Another version at Black Hole Initiative, Harvard-Smithsonian Center for Astrophysics, Cambridge, MA, February 4, 2020; CSAIL Hot Topics, MIT, Cambridge, MA, February 6, 2020; University of Houston Physics Department, Houston, TX, February 18, 2020; Hearne Eminent Lecture in Physics, Louisiana State University, Baton Rouge, LA, March 11, 2020; Supercomputing Frontiers Europe (by videoconference), April 1, 2020; International Center for Theoretical Physics (ICTP) Colloquium, Trieste, Italy (by videoconference), July 29, 2020; CERN Colloquium, Geneva, Switzerland (by videoconference), July 30, 2020; Purdue University ECE colloquium, West Lafayette, Indiana (by videoconference), August 6, 2020; SCI Summer Research Colloquium, Rice University, Houston, TX (by videoconference), August 7, 2020; Pittsburgh Quantum Institute, Pittsburgh, PA (by videoconference), August 20, 2020; Mathematical Sciences Research Institute (MSRI) Math Lovers' Forum (by videoconference), October 6, 2020; Institute for Mathematical and Statistical Innovation (IMSI) Opening Conference, University of Chicago (by videoconference), October 8, 2020; Yale Quantum Institute Colloquium, New Haven, CT (by videoconference), October 9, 2020; Stanford Linear Accelerator Center (SLAC) Colloquium (by videoconference), November 2, 2020; Texas Section of the American Physical Society (by videoconference), November 13, 2020; Lytle Lecture, Department of Electrical and Computer Engineering, University of Washington (by videoconference), November 19, 2020; Computer Science at Gran Sasso Science Institute / Reykjavik University, Iceland (by videoconference), November 30, 2020; Texas Section of the American Physical Society, Houston, TX, October 14, 2022; Saarbrücken-Jülich Quantum Information Colloquium, Germany, October 31, 2022
- The Quantum Potential: Panel Discussion with Jennifer Schenker and Jeremy O'Brien, World Economic Forum Annual Meeting, Davos, Switzerland, January 21, 2020
- Remarks on Huang's Proof of the Sensitivity Conjecture: Workshop on Algebraic Techniques in Computational Complexity, Banff Centre, Banff, Canada, July 8, 2019
- NP-complete Problems and Physics: Symposium on 50 Years of Complexity Theory (A Celebration of the Work of Stephen Cook), Fields Institute, University of Toronto, May 9, 2019. Another version as Distinguished Lecture, Hebrew University, Jerusalem, Israel, June 11, 2019; Director's Colloquium, Los Alamos National Lab, Los Alamos, NM, June 27, 2019; Park City Mathematics Institute (PCMI), Park City, UT, July 15, 2019
- Quantum Computing and the Quest for Quantum Computational Supremacy: SparkCognition, Austin, TX, January 22, 2019; UT San Antonio, March 8, 2019; Cirrus Logic, Austin, TX, August 20, 2019. Another version at UTCS Advisory Council Meeting, Austin, TX, October 26, 2018
- Gentle Measurement of Quantum States and Differential Privacy: Institute for Quantum Computing, University of Waterloo, Ontario, Canada, July 26, 2018; CS Theory Seminar, UT Austin, Austin, TX, August 31, 2018; Quantum Machine Learning Workshop, University of Maryland, College Park, MD, September 28, 2018. Another version at CQuIC Seminar, University of New Mexico, Albuquerque, NM, October 19, 2018. Another version at Theory Colloquium, MIT, Cambridge, MA, November 20, 2018; University of Technology Sydney, Australia, January 11, 2019. Another version at SQuInT, Albuquerque, NM, February 12, 2019; CS theory seminar, University of Chicago, February 28, 2019; Hebrew University CS theory seminar, Jerusalem, Israel, June 12, 2019. Another version at STOC, Phoenix, AZ, June 24, 2019. Another version at CMSA, Harvard University, Cambridge, MA, February 5, 2020
- Firewalls, AdS/CFT, and the Complexity of States and Unitaries -- A Computer Science Perspective: two lectures at Progress in Theoretical Physics (PiTP) summer school on "From Qubits to Spacetime," Institute for Advanced Study, Princeton, NJ, July 19-20, 2018
- Quantum Algorithms: Three lectures at Boulder School for Condensed Matter and Materials Physics, Boulder, CO, July 12-13, 2018
- Shadow Tomography, Gentle Measurements, and Differential Privacy: lightning talk, Challenges in Quantum Computation workshop, Simons Institute, UC Berkeley, Berkeley, CA, June 14, 2018
- Quantum Supremacy and its Applications: Challenges in Quantum Computation workshop, Simons Institute, UC Berkeley, Berkeley, CA, June 12, 2018. Another version at University of Colorado, Boulder, CO, July 11, 2018; "Programs, Minds, and Machines" workshop, UNAM, Mexico City, Mexico, August 9, 2018; Quantum Information for Developers (QuID) Hackathon, Zurich, Switzerland, September 12, 2018; Nathan Krasnopoler Memorial Lecture, Johns Hopkins University, Baltimore, MD, September 27, 2018; ECE Colloquium, USC, Los Angeles, CA, October 12, 2018; Physics Colloquium, University of New Mexico, Albuquerque, NM, October 20, 2018. Another version as Keynote at Q2B Conference, Computer History Museum, Mountain View, CA, December 12, 2018. Another version at Sandia National Labs, Albuquerque, NM, February 8, 2019; Argonne National Lab, March 1, 2019; CS theory seminar, University of Haifa, Israel, June 13, 2019. Another version as CS theory seminar, UT Austin, Austin, TX, October 11, 2019
- PDQP/qpoly=ALL: Hebrew University, Jerusalem, Israel, May 31, 2018
- Certified Randomness from Quantum Supremacy: Google, Santa Barbara, CA, May 11, 2018; Google, Venice Beach, CA, May 16, 2018; Wolf Prize Symposium for Charles Bennett and Gilles Brassard, Hebrew University, Jerusalem, Israel, May 30, 2018; PiQuDos seminar, Perimeter Institute, Waterloo, Canada, July 25, 2018; Microsoft Research, Redmond, WA, August 3, 2018. Another version at Beyond Crypto, A TCS Perspective, UCSB, Santa Barbara, CA, August 19, 2018; La Sapienza, Rome, Italy, September 14, 2018; Google X, Mountain View, CA, October 11, 2018; CS department, UCSD, San Diego, CA, March 20, 2019. Another version at TCS+ (via Zoom), May 3, 2023
- An Armory of Assumptions: It from Qubit Annual Meeting, Simons Foundation, New York, NY, December 8, 2017
- If The Universe Is A Computer, What Kind Of Computer Is It?: Bethe Ansatz, Hans Bethe House, Cornell University, Ithaca, NY, November 29, 2017
- Leonid, BosonSampling, and the Permanent: Leonid Gurvits 60th Birthday Celebration, CCNY, New York, NY, November 20, 2017
- New Results on Learning and Reconstruction of Quantum States: Weizmann Institute Theory Seminar, Rehovot, Israel, November 6, 2017. Another version at Hebrew University CS Theory Seminar, Jerusalem, Israel, November 8, 2017. Another version as Messenger Lecture, Cornell University CS Colloquium, Ithaca, NY, November 30, 2017
- Quantum Computing: UT Austin Development Board Meeting, Austin, TX, October 20, 2017; talk to Turing Scholars, Austin, TX, February 19, 2018; Tel Aviv University Economics Theory Seminar, Tel Aviv, Israel, March 13, 2018; Ben Gurion University CS Colloquium, Beersheba, Israel, April 24, 2018; Jane Street, New York, NY, August 1, 2018
- Black Holes, Firewalls, and the Limits of Quantum Computers: Simons Institute Theoretically Speaking Series, Berkeley, CA, October 18, 2017. Another version as CS Colloquium, Georgia Tech, Atlanta, GA, December 4, 2017
- Quantum Computing: QC Ware, Menlo Park, CA, October 17, 2017. Another version at IBM Research Labs, Haifa, Israel, March 14, 2018; Interdisciplinary Center, Herzliya, Israel, May 29, 2018
- Big Numbers: Festivaletteratura, Mantova, Italy, September 9, 2017; PubSpeak, Telluride House, Cornell University, December 1, 2017. Earlier version at Fourth Annual Marvin I. Freedman Memorial Colloquium, Boston University, March 30, 2012.
- GapP, Oracles, and Quantum Supremacy: Kurtz Festschrift Conference, Columbia, South Carolina, August 20, 2017
- PAC-Learning and Reconstruction of Quantum States: Plenary Talk, COLT'2017, Amsterdam, Netherlands, July 7, 2017. Another version at Frontiers of Quantum Information Physics workshop, Kavli Institute for Theoretical Physics, UCSB, Santa Barbara, October 12, 2017. Another version at Tel Aviv University CS theory seminar, Tel Aviv, Israel, October 24, 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 50th 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
- 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.
- 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; UT Austin Undergraduate Math Club, Austin, TX, February 20, 2018
- 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; Quantum Computing Club, LASA High School, Austin, TX, March 12, 2019. 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; Workshop on Quantum Computational Supremacy, Bristol, UK, August 16, 2017; Heidelberg Laureates Forum, Heidelberg, Germany, September 28, 2017; CS Colloquium, Technion, Haifa, Israel, November 7, 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. Another version at "Programs, Minds, and Machines" workshop, UNAM, Mexico City, Mexico, August 8, 2018
- Complexity-Theoretic Foundations of Quantum Supremacy Experiments: Quantum Algorithms Workshop, Aspen Center for Physics, Aspen, CO, March 25, 2016. Another version as Messenger Lecture, Cornell University Physics Department, Ithaca, NY, November 27, 2017. Another version as Physics Colloquium at Weizmann Institute, Rehovot, Israel, January 25, 2018
- 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
- 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; Probability Seminar, Tel Aviv University, December 25, 2017
- Separations in Quantum Query Complexity: Centre for Quantum Technologies, National University of Singapore, August 21, 2015
- 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
- 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
- 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
- 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
- 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
- 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. Another version at International Conference on Integrated Quantum Photonics, Rome, Italy, September 26 and 27, 2017. Another version at AMO Seminar, Physics Department, Weizmann Institute of Science, Rehovot, Israel, January 9, 2018
- Computational Complexity Underpinnings of the Harlow-Hayden Argument: Complementary, Fuzz, or Fire Workshop, Kavli Institute for Theoretical Physics, Santa Barbara, CA, August 22, 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
- The Ghost in the Quantum Turing Machine: Yakir Aharonov 80th Birthday Conference, Chapman University, Anaheim, CA, August 17, 2012. Another version at Mind and Language Seminar, Philosophy Department, NYU, New York, NY, March 5, 2024
- 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
- 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; 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. Another version at Technische Universität Dresden, Germany, August 28, 2017. Another version as Messenger Lecture, Cornell University, Ithaca, NY, November 28, 2017; CViCom, UNAM, Mexico City, Mexico, August 10, 2018
- 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.
- 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
[Return to home page]