A Polynomial Degree Bound on Equations for Non-rigid Matrices and Small Linear Circuits

A Polynomial Degree Bound on Equations for Non-rigid Matrices and Small Linear Circuits

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


Duration: 26:50
112 views
2

12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
http://itcs-conf.org/

A Polynomial Degree Bound on Equations for Non-rigid Matrices and Small Linear Circuits

Mrinal Kumar (IIT Bombay)
Ben Lee Volk (Caltech/UT Austin)



Other Videos By Simons Institute for the Theory of Computing


2021-01-15Circular Trace Reconstruction
2021-01-15Comparison Graphs: a Unified Method for Uniformity Testing
2021-01-15Complexity measures on symmetric group and beyond
2021-01-15The Variable-Processor Cup Game
2021-01-15Even the Easiest(?) Graph Coloring Problem is not Easy in Streaming!
2021-01-15Approximately Strategyproof Tournament Rules in the Probabilistic Setting
2021-01-15A New Model for Ant Trail Formation and its Convergence Properties
2021-01-15The Quantum Supremacy Tsirelson Inequality
2021-01-15Sample efficient identity testing and independence testing of quantum states
2021-01-15Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution
2021-01-15A Polynomial Degree Bound on Equations for Non-rigid Matrices and Small Linear Circuits
2021-01-15Pipeline Interventions
2021-01-15Pseudorandom Generators for Unbounded-Width Permutation Branching Programs
2021-01-15Sharp Threshold Rates for Random Codes
2021-01-15The Complexity of Finding Fair Independent Sets in Cycles
2021-01-15Algorithmic Persuasion with Evidence
2021-01-15Comparing computational entropies below majority (or: When is the dense model theorem false?)
2021-01-15The entropy of lies: playing twenty questions with a liar
2021-01-12Error Correcting Codes for Uncompressed Messages
2021-01-12Algorithms and Hardness for Multidimensional Range Updates and Queries
2021-01-12Algebraic and circuit complexity