Algebraic and circuit complexity
2Complexity measures on symmetric group and beyond
Neta Dafni (Technion), Yuval Filmus (Technion), Noam Lifshitz (Hebrew University), Nathan Lindzey (CU Boulder), Marc Vinyals (Technion)
On the Complexity of #CSP^d
Jiabao Lin (Shanghai University of Finance and Economics)
On the complexity of isomorphism problems for tensors, groups, and polynomials I: Tensor Isomorphism-completeness
Joshua A. Grochow (University of Colorado, Boulder), Youming Qiao (University of Technology Sydney)
A Polynomial Degree Bound on Equations for Non-rigid Matrices and Small Linear Circuits
Mrinal Kumar (IIT Bombay), Ben Lee Volk (Caltech/UT Austin)
A Largish Sum-of-Squares Implies Circuit Hardness and Derandomization
Pranjal Dutta (Chennai Mathematical Institute), Nitin Saxena (IIT Kanpur), Thomas Thierauf (Aalen University)
ITCS 2021
Other Videos By Simons Institute for the Theory of Computing
| 2021-01-15 | The Strongish Planted Clique Hypothesis and Its Consequences |
| 2021-01-15 | Pipeline Interventions |
| 2021-01-15 | Pseudorandom Generators for Unbounded-Width Permutation Branching Programs |
| 2021-01-15 | Sharp Threshold Rates for Random Codes |
| 2021-01-15 | The Complexity of Finding Fair Independent Sets in Cycles |
| 2021-01-15 | Algorithmic Persuasion with Evidence |
| 2021-01-15 | Comparing computational entropies below majority (or: When is the dense model theorem false?) |
| 2021-01-15 | The entropy of lies: playing twenty questions with a liar |
| 2021-01-12 | Error Correcting Codes for Uncompressed Messages |
| 2021-01-12 | Algorithms and Hardness for Multidimensional Range Updates and Queries |
| 2021-01-12 | Algebraic and circuit complexity |
| 2021-01-12 | Online and streaming algorithms |
| 2021-01-12 | Algorithmic Game Theory |
| 2021-01-12 | Optimization |
| 2021-01-12 | Codes and information |
| 2021-01-12 | Machine Learning |
| 2021-01-11 | Circuits and communication |
| 2021-01-10 | Graph algorithms |
| 2021-01-10 | Algorithms |
| 2021-01-10 | GRADUATING BITS |
| 2021-01-10 | Algorithmic game theory |