original ) (raw )
Robustness Meets Algorithms Jacob Steinhardt Learning Topic Models -- Provably and Efficiently David Blei Disentangling Gaussians Santosh Vempala Belkin and Sinha
Model Stealing for Any Low-Rank Language Model Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics Precise Error Rates for Computationally Efficient Testing Edit Distance Robust Watermarks via Indexing Pseudorandom Codes Structure Learning of Hamiltonians from Real-time Evolution Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning High-Temperature Gibbs States are Unentangled and Efficiently Preparable Quanta Quantum Information Processing (QIP 2025) Invited Plenary The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximation Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actions The Power of an Adversary in Glauber Dynamics Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles Learning Quantum Hamiltonians at Any Temperature in Polynomial Time Quanta Invited to the SIAM Journal on Computing Special Issue for STOC 2024 Quantum Information Processing (QIP 2024) Invited Plenary Provable Benefits of Score Matching Spotlight Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systems A New Approach to Learning Linear Dynamical Systems Planning and Learning in Partially Observable Systems via Filter Stability Distilling Model Failures as Directions in Latent Space Spotlight Provably Auditing Ordinary Least Squares in Low Dimensions From Algorithms to Connectivity and Back: Finding a Giant Component in Random k-SAT Robust Voting Rules from Algorithmic Robust Statistics Learning in Observable POMDPs, without Computationally Intractable Oracles Robust Model Selection and Nearly-Proper Learning for GMMs Polynomial Time Guarantees for the Burer-Monteiro Method Minimax Rates for Robust Community Detection Can Q-Learning be Improved with Advice? Learning GMMs with Nearly Optimal Robustness Guarantees Kalman Filtering with Adversarial Corruptions A No-go Theorem for Acceleration in the Hyperbolic Plane Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination Learning to Sample from Censored Markov Random Fields Settling the Robust Learnability of Mixtures of Gaussians Algorithmic Foundations for the Diffraction Limit Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability Spotlight Tensor Completion Made Practical Learning Structured Distributions from Untrusted Batches: Faster and Simpler Learning Some Popular Gaussian Graphical Models without Condition Number Bounds Spotlight Rigorous Guarantees for Tyler's M-estimator via Quantum Expansion Parallels Between Phase Transitions and Circuit Complexity? Better Algorithms for Estimating Non-Parametric Models in Crowd-Sourcing and Rank Aggregation Efficiently Learning Structured Distributions from Untrusted Batches Spectral Methods from Tensor Networks Invited to the SIAM Journal on Computing Special Issue for STOC 2019 Learning Restricted Boltzmann Machines via Influence Maximization Beyond the Low-Degree Algorithm: Mixtures of Subcubes and Their Applications How Many Subpopulations is Too Many? Exponential Lower Bounds for Inferring Population Histories Journal of Computational Biology Special Issue for RECOMB 2019 The Paulsen Problem Made Simple Improved Bounds for Sampling Colorings via Linear Programming Efficiently Learning Mixtures of Mallows Models Optimality and Suboptimality of PCA I: Spiked Random Matrix Models Robustly Learning a Gaussian: Getting Optimal Error, Efficiently Message-Passing Algorithms for Synchronization Problems over Compact Groups Information Theoretic Properties of Markov Random Fields, and their Algorithmic Applications Learning Determinantal Point Processes with Moments and Cycles Being Robust (in High Dimensions) Can Be Practical Maximum Likelihood Estimation of Determinantal Point Processes Approximate Counting, the Lovasz Local Lemma and Inference in Graphical Models A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem SIAM Journal on Computing Special Issue for FOCS 2016 Robust Estimators in High Dimensions without the Computational Intractability Invited to Communications of the ACM, Research Highlights SIAM Journal on Computing Special Issue for FOCS 2016 Provable Algorithms for Inference in Topic Models How Robust are Reconstruction Thresholds for Community Detection? Noisy Tensor Completion via the Sum-of-Squares Hierarchy Mathematical Programming, Series B Special Issue Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree Simple, Efficient and Neural Algorithms for Sparse Coding Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices New Algorithms for Learning Incoherent and Overcomplete Dictionaries Smoothed Analysis of Tensor Decompositions A Polynomial Time Approximation Scheme for Fault-tolerant Distributed Storage A Polynomial Time Algorithm for Lossy Population Recovery Algorithms and Hardness for Robust Subspace Recovery A Practical Algorithm for Topic Modeling with Provable Guarantees Invited to Communications of the ACM, Research Highlights An Information Complexity Approach to Extended Formulations An Almost Optimal Algorithm for Computing Nonnegative Rank Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders Algorithmica Special Issue for Machine Learning Learning Topic Models -- Going Beyond SVD Computing a Nonnegative Matrix Factorization -- Provably SIAM Journal on Computing Special Issue for STOC 2012 Nearly Complete Graphs Decomposable into Large Induced Matchings and their Applications On Entropy and Extensions of Posets Efficient and Explicit Coding for Interactive Communication Pareto Optimal Solutions for Smoothed Analysts SIAM Journal on Computing Special Issue for STOC 2011 Dueling Algorithms MIT News Capacitated Metric Labeling Settling the Polynomial Learnability of Mixtures of Gaussians Invited to Communications of the ACM, Research Highlights Vertex Sparsifiers and Abstract Rounding Algorithms Efficiently Learning Mixtures of Two Gaussians Extensions and Limits to Vertex Sparsification Vertex Sparsification and Oblivious Reductions SIAM Journal on Computing Special Issue for FOCS 2009 Some Results on Greedy Embeddings in Metric Spaces Invited )