Talks

Paul Beame - Talks

• Lower Bounds, EPIT 2023 : Le Kaléidoscope de la Complexité, Ile d'Oléron, June 2023.
  • Circuit Complexity
  • Proof Complexity
  • Communication Complexity
• Proof Complexity 2020: A Survey, BIRS Workshop on Proof Complexity, January 2020.
• The Limits of Proof, Simons Institute for Theoretical Computer Science Open Lecture, November 2018.
• Switching Lemmas and Proof Complexity, Dagstuhl Workshop on Proof Complexity, January 2018.
• Knowledge Compilation: Representations and Lower Bounds, Dagstuhl Workshop on Recent Trends in Knowledge Compilation, September 2017.
• Branching Programs and Time-Space Tradeoffs, Nexus of Information and Computation Theories, Institut Henri Poincare, Paris, February 2016
  • Part 1: Branching Programs and Lower Bounds for Multi-output Functions
  • Part 2: Analyzing Boolean Functions on Restricted Branching Programs.
  • Part 3: Analyzing Single-Output Functions on General Branching Programs
  • Extra: Time-Space Tradeoffs for Computing Error-Correcting Codes
• A Tutorial Introduction to Proof Complexity Dagstuhl Workshop on Theory and Applications of Satisfiability Testing, April 2015.
• Communication Complexity: An Introduction and Survey with Open Problems Barriers in Complexity Workshop II, Princeton, NJ, August 2010.
• Satisfiability and Unsatisfiability: Proof Complexity and Algorithms Invited talk at SAT 05, St. Andrews, June 2005.
• Phase Transitions in Proof Complexity and Satisfiability Search AAAS Annual Meeting, Seattle, February 2004.
• Techniques for Time-Space Tradeoff Lower Bounds for Branching Programs:
  Part I and Part II McGill Workshop on Branching Programs, Montreal, May 2002.
• Time-Space Tradeoff Lower Bounds for Nonuniform Computation Invited talk at CCC 2000, Florence, July 2000.