Proper Learning Algorithms from Lower Bounds for Arithmetic Circuits

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


Duration: 1:02:34
760 views
11

Neeraj Kayal (Microsoft Research India)
https://simons.berkeley.edu/talks/neeraj
Algebraic Methods



Other Videos By Simons Institute for the Theory of Computing


2018-12-06Formal Series and Non-Commutative Computations
2018-12-06Complete Derandomization of Identity Testing of Read-Once Formulas
2018-12-06PIT Questions in Invariant Theory
2018-12-06Analyzing Alternating Minimization Algorithms Using Algebraic Methods
2018-12-05Algebraic Dependence is Not Hard (& Filling the GCT Chasm)
2018-12-05A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits
2018-12-05Reconstruction of Non-Degenerate Homogeneous Depth Three Circuits
2018-12-05The Edge of Physics: Crafting a Non-Fiction Narrative that Combines Science with Travel Writing
2018-12-05An Improved Depth Reduction for Syntactically Multilinear Circuits
2018-12-05Fine-Grained Algorithms and Complexity of Solving Polynomial Systems of Equations
2018-12-05Proper Learning Algorithms from Lower Bounds for Arithmetic Circuits
2018-12-04Generalized Matrix Completion and Algebraic Natural Proofs
2018-12-04Recent Progress on Representation Theoretic Multiplicities in GCT
2018-12-04Kronecker and Plethysm Coefficients in Geometric Complexity Theory: ...
2018-12-04An Instance of Symbolic Determinant Identity Testing via *-algebras
2018-12-04Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree
2018-12-04Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
2018-12-03Proof Complexity Lower Bounds from Graph Expansion and Combinatorial Games
2018-12-03Orbits of Monomials and Factorization into Products of Linear Forms
2018-12-03Invariant Theory for Computer Scientists
2018-12-03Geometric Complexity Theory: No Occurrence Obstructions for Determinant vs Permanent


Tags:
Simons Institute
Theory of Computing
Theory of Computation
Theoretical Computer Science
Computer Science
UC Berkeley
Algebraic Methods
Neeraj Kayal