Thinking Algorithmically About Impossibility

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=7uplycLvraw


Duration: 55:22
4,420 views
75

Ryan Williams, Stanford University
Simons Institute Open Lectures, Fall 2015
https://simons.berkeley.edu/events/openlectures2015-fall-2



Other Videos By Simons Institute for the Theory of Computing


2015-10-19Consensus Expectations and Conventions
2015-10-19Privacy, Substitutes, and Optimization in Deferred-Acceptance Clock Auctions
2015-10-19Dynamics of Evolving Social Groups
2015-10-19On the Borders of Border’s Theorem
2015-10-19The Query Complexity of Correlated Equilibria
2015-10-19Econometrics for Learning Agents
2015-10-19Robustness and Separation in Multidimensional Mechanism Design
2015-10-19First Price Auctions with General Information Structures: Implications for Bidding and Revenue
2015-10-19Revenue Maximization in Interdependent Value Settings
2015-10-19Competition and Simple Auctions
2015-10-08Thinking Algorithmically About Impossibility
2015-10-01Satisfiability Algorithms Based on Concentrated Shrinkage
2015-10-01Generalizations of the Gate Elimination Method
2015-10-01Addition is Exponentially Harder than Counting for Shallow Monotone Circuits
2015-10-01Graph Automorphism and Circuit Size
2015-10-01On the Power of Gradually Increasing Independence
2015-10-01Local Reductions
2015-10-01Explicit Two-Source Extractors and Resilient Functions
2015-10-01Lower Bounds by Birkhoff Interpolation
2015-10-01On the Existence of Optimal Algorithms
2015-10-01Probabilistic Polynomials and Hamming Nearest Neighbors


Tags:
Simons Institute
Computer science
theory of computation
open lecture
ryan williams
complexity
Computational Complexity Theory (Field Of Study)
theory of algorithms
uc berkeley