Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality

Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality

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


Category:
Vlog
Duration: 34:43
279 views
3

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

Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality

Esty Kelman (Tel Aviv University)
Subhash Khot (NYU)
Guy Kindler (Hebrew University)
Dor Minzer (MIT)
Muli Safra (Tel-Aviv University)



Other Videos By Simons Institute for the Theory of Computing


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
2021-01-15Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality
2021-01-15Circuit Depth Reductions
2021-01-15Dynamic inference in probabilistic graphical models
2021-01-15A Largish Sum-of-Squares Implies Circuit Hardness and Derandomization
2021-01-15Metrical Service Systems with Transformations
2021-01-15Tight Hardness Results for Training Depth-2 ReLU Networks
2021-01-15Polynomial-time trace reconstruction in the low deletion rate regime
2021-01-15Self-testing of a single quantum device under computational assumptions
2021-01-15Circular Trace Reconstruction
2021-01-15Comparison Graphs: a Unified Method for Uniformity Testing
2021-01-15Complexity measures on symmetric group and beyond