Explicit SoS lower bounds from high-dimensional expanders

Explicit SoS lower bounds from high-dimensional expanders

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


Duration: 33:46
245 views
1

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

Explicit SoS lower bounds from high-dimensional expanders

Irit Dinur (Weizmann Institute of Science)
Yuval Filmus (Technion)
Prahladh Harsha (TIFR)
Madhur Tulsiani (Toyota Technological Institute at Chicago)



Other Videos By Simons Institute for the Theory of Computing


2021-01-15Black-Box Uselessness: Composing Separations in Cryptography
2021-01-15Tiered Random Matching Markets: Rank is Proportional to Popularity
2021-01-15Relaxing Common Belief for Social Networks
2021-01-15Total Functions in the Polynomial Hierarchy
2021-01-15Ordered Graph Limits and Their Applications
2021-01-15Shrinkage under random projections, and cubic formula lower bounds in AC^0
2021-01-15Interactive Proofs for Verifying Machine Learning
2021-01-15Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum
2021-01-15On the Complexity of #CSP^d
2021-01-15Sampling Arborescences in Parallel
2021-01-15Explicit SoS lower bounds from high-dimensional expanders
2021-01-15Two combinatorial MA-complete problems
2021-01-15Delegated Stochastic Probing
2021-01-15Is the space complexity of planted clique recovery the same as that of detection?
2021-01-15Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate
2021-01-15Bounds on the QAC0 Complexity of Approximating Parity
2021-01-15Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits
2021-01-15On the complexity of isomorphism problems for tensors, groups, and polynomials I: Tensor Isomorphism
2021-01-15On Basing Auxiliary-Input Cryptography on NP-hardness via Nonadaptive Black-Box Reductions
2021-01-15Distributed Quantum Proofs for Replicated Data
2021-01-15On Rich 2-to-1 Games