Connections Between Hardness and Randomness in the Algebraic Setting

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


Duration: 1:01:38
286 views
0

Russell Impagliazzo, UC San Diego
Fine-Grained Complexity and Algorithm Design Boot Camp
http://simons.berkeley.edu/talks/russell-impagliazzo-2015-09-04



Other Videos By Simons Institute for the Theory of Computing


2015-10-01A Compression Algorithm for AC^0[p] Circuits Using Certifying Polynomials
2015-10-01Satisfiability Algorithms for Small Depth Circuits with Symmetric Gates
2015-10-01Sublinear Space Complexity
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-09Connections Between Hardness and Randomness in the Algebraic Setting
2015-09-09Parameterized Reductions
2015-09-09Exponential-Time Algorithms
2015-09-09Satisfiability Algorithms I
2015-09-09Circuit Complexity and Connections II
2015-09-09Circuit Complexity and Connections I
2015-09-09Boolean Hardness to Randomization
2015-09-09Consequences of ETH: Tight Bounds for Various Problems
2015-09-09Recent Advances in FPT and Exact Algorithms for NP-Complete Problems
2015-09-09Consequences of SETH: Tight Bounds for Some More Problems
2015-09-09Sparsification Lemma and ETH


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