Extractor-Based Approach To Memory-Sample Tradeoffs

Extractor-Based Approach To Memory-Sample Tradeoffs

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


Duration: 44:56
267 views
6

Sumegha Garg (Harvard University)
https://simons.berkeley.edu/talks/extractor-based-approach-memory-sample-tradeoffs
Rigorous Evidence for Information-Computation Trade-offs



Other Videos By Simons Institute for the Theory of Computing


2021-09-22An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor
2021-09-21On Some Optimization Problems Involving a Large Number of Matrices
2021-09-18Computational Barriers For Learning Some Generalized Linear Models
2021-09-18Towards Lower Bounds for Efficient Robust Estimation From Worst Case Assumptions
2021-09-18SQ Lower Bounds for Learning Halfspaces with Massart Noise
2021-09-17Non-Gaussian Component Analysis: Statistical Query Hardness and its Applications
2021-09-17The Estimation Error of General First Order Methods
2021-09-17Differential Privacy And The Complexity Of Simple Queries
2021-09-17Refutation and Spectrally Quiet Planting of Cuts and Colorings in Random Graphs
2021-09-17Optimal Spectral Recovery Of A Planted Vector In A Subspace
2021-09-16Extractor-Based Approach To Memory-Sample Tradeoffs
2021-09-16Average-Case Hardness in Proof Complexity
2021-09-16Tight Algorithmic Thresholds for Spin Glass Hamiltonians
2021-09-16The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials
2021-09-16Optimizing Noncommutative Polynomials: The SYK Model
2021-09-15Putting Quantum Supremacy on a Rigorous Footing
2021-09-15Mismatched Monte Carlo Algorithms For The Planted Clique Problem
2021-09-15Phase Retrieval In High Dimensions: Statistical And Computational Phase Transitions
2021-09-15All-or-Nothing Statistical and Computational Phase Transitions in Sparse Spiked Matrix Estimation
2021-09-15Signal Recovery With Generative Priors
2021-09-15Local Convexity Of The Tap Free Energy And Amp Convergence For Z2-Synchronization


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Rigorous Evidence for Information-Computation Trade-offs
Sumegha Garg