Smoothed CSP Refutation Is As Easy As Random, For Both Efficient Algorithms And Certificates

Smoothed CSP Refutation Is As Easy As Random, For Both Efficient Algorithms And Certificates

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


Duration: 57:41
535 views
7

Pravesh K. Kothari (Carnegie Mellon University)
https://simons.berkeley.edu/talks/smoothed-csp-refutation-easy-random-both-efficient-algorithms-and-certificates
Rigorous Evidence for Information-Computation Trade-offs



Other Videos By Simons Institute for the Theory of Computing


2021-09-14A Few Simple Average-Case Reduction Techniques And Their Surprising Effectiveness
2021-09-14Are Generative Models The New Sparsity?
2021-09-14To Be (Hard) or Not Be:...
2021-09-14The Overlap Gap Property For Inference: Power And Limitations
2021-09-14Computational Barriers to Estimation from Low-Degree Polynomials
2021-09-14Charting the Landscape of Memory/Data Tradeoffs in Continuous Optimization: ...
2021-09-14New Techniques For Proving Fine-Grained Average-Case Hardness
2021-09-14Robust Parameter Estimation For Random Graphs
2021-09-14Planted Geometric Matching Problems
2021-09-13Sum Of Squares Lower Bounds Versus Low-Degree Polynomial Lower Bounds
2021-09-13Smoothed CSP Refutation Is As Easy As Random, For Both Efficient Algorithms And Certificates
2021-09-13On Implicit Regularization in Deep Learning
2021-09-13On the Power of Preconditioning in Sparse Linear Regression
2021-09-13Towards Credible and Effective Data-Driven Decision-Making
2021-09-13Primal--Dual Optimization and Application to Sampling
2021-09-13Data Efficient Methods for Reinforcement Learning
2021-09-13Theoretical Foundations of Data-Driven Algorithm Design
2021-09-13Distribution-Free Robustness
2021-09-13Pseudorandom Generators and Small-Space Derandomization
2021-09-13Preconditioning and Locality in Algorithm Design
2021-09-13Query, Communication and Discrepancy


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Rigorous Evidence for Information-Computation Trade-offs
Pravesh K. Kothari