A Compression Algorithm for AC^0[p] Circuits Using Certifying Polynomials

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


Duration: 48:59
372 views
1

Srikanth Srinivasan, Indian Institute of Technology Bombay
Connections Between Algorithm Design and Complexity Theory
https://simons.berkeley.edu/talks/srikanth-srinivasan-2015-09-30



Other Videos By Simons Institute for the Theory of Computing


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
2015-10-01A Compression Algorithm for AC^0[p] Circuits Using Certifying Polynomials
2015-10-01Human Computation
2015-10-01Approaches to Bounding the Exponent of Matrix Multiplication
2015-09-18Learning and Efficiency in Games
2015-09-09Proof of NEXP Not in ACC
2015-09-09Computational Complexity of Polynomial Time Problems: Introduction
2015-09-09Derandomization to Boolean Circuit Lower Bounds
2015-09-09Circuit Analysis Algorithms
2015-09-09Satisfiability Algorithms II
2015-09-09Hardness for Dynamic Problems; Conclusion and Future Research
2015-09-09The Easy Witness Lemma


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