Total Function Problems in the Polynomial Hierarchy

Channel:

Subscribers:

68,700

Published on February 19, 2021 5:28:52 AM ● Video Link: https://www.youtube.com/watch?v=UDsWFyuQe0w

Duration: 50:56

754 views

Christos Papadimitriou (Columbia University)
https://simons.berkeley.edu/talks/tbd-269
50 Years of Satisfiability: The Centrality of SAT in the Theory of Computing

Other Videos By Simons Institute for the Theory of Computing

2021-03-01	Neural Network guided Grammar Filtering For Syntax-Guided Synthesis
2021-02-26	The Complexity of Computing a Tarski Fixed Point of a Monotone Function, With Applications to Games
2021-02-25	Richard M. Karp Distinguished Lecture — Automated Formal Program Repair
2021-02-25	Quantum Algorithmic Measurements \| Quantum Colloquium
2021-02-25	Encodings Showcase
2021-02-24	Deep Dive into CDCL Pseudo-Boolean Solvers (focusing on the implementation in Sat4j)
2021-02-23	Quantum Algorithms for Hamiltonian Simulation \| Quantum Colloquium
2021-02-22	Syntax-Guided Program Synthesis
2021-02-19	Rational Synthesis
2021-02-18	On the Usefulness of the Strong Exponential Time Hypothesis
2021-02-18	Total Function Problems in the Polynomial Hierarchy
2021-02-17	Combining SAT and Computer Algebra for Circuit Verification
2021-02-11	Hypotheses about Satisfiability and their Consequences
2021-02-11	Existentially Polytime Theorems
2021-02-09	The Rise of Approximate Model Counting: Beyond Classical Theory and Practice of SAT
2021-02-09	Quantum Supremacy via Boson Sampling: Theory and Practice \| Quantum Colloquium
2021-02-08	Reactive Synthesis
2021-02-06	Using SAT Solvers to Prevent Causal Failures in the Cloud
2021-02-05	Programming Z3
2021-02-05	Approximate Counting and Sampling
2021-02-04	Pseudo-Boolean Solving and Optimization

Tags:

Simons Institute

theoretical computer science

UC Berkeley

Computer Science

Theory of Computation

Theory of Computing

50 Years of Satisfiability: The Centrality of SAT in the Theory of Computing

Christos Papadimitriou