Addition is Exponentially Harder than Counting for Shallow Monotone Circuits

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


Duration: 15:16
224 views
2

Igor Oliveira, Columbia University
Connections Between Algorithm Design and Complexity Theory
https://simons.berkeley.edu/talks/igor-oliveira-2015-10-01



Other Videos By Simons Institute for the Theory of Computing


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
2015-10-01Derandomization via Robust Algebraic Circuit Lower Bounds
2015-10-01Chasing Lower Bounds
2015-10-01Anti-Concentration for Polynomials of Independent Random Variables


Tags:
Simons Institute
UC Berkeley
computer science
theory of computing
Fine-Grained Complexity and Algorithm Design
Igor Oliveira