Kevin Tian

CoRR, 2024

Testing Calibration in Subquadratic Time.

[BibT_eX]

[DOI]

Lunjia Hu

Chutong Yang

CoRR, 2024

A CS guide to the quantum singular value transformation.

[BibT_eX]

[DOI]

Ewin Tang

Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

Linear-Sized Sparsifiers via Near-Linear Time Discrepancy Theory.

[BibT_eX]

[DOI]

Victor Reis

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization.

[BibT_eX]

[DOI]

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

Black-Box k-to-1-PCA Reductions: Theory and Applications.

[BibT_eX]

[DOI]

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

2023

Quadratic Speedups in Parallel Sampling from Determinantal Distributions.

[BibT_eX]

[DOI]

Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, 2023

Private Convex Optimization in General Norms.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Revisiting Area Convexity: Faster Box-Simplex Games and Spectrahedral Generalizations.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Structured Semidefinite Programming for Recovering Structured Preconditioners.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2023

Matrix Completion in Almost-Verification Time.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

ReSQueing Parallel and Private Stochastic Convex Optimization.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Semi-Random Sparse Recovery in Nearly-Linear Time.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Sampler.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

Iterative methods for structured algorithmic data science.

[BibT_eX]

[DOI]

PhD thesis, 2022

Improved Sampling-to-Counting Reductions in High-Dimensional Expanders and Faster Parallel Determinantal Sampling.

[BibT_eX]

[DOI]

CoRR, 2022

Clustering mixture models in almost-linear time via list-decodable mean estimation.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods.

[BibT_eX]

[DOI]

Yujia Jin

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

2021

Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Robust Regression Revisited: Acceleration and Improved Estimation Rates.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

List-Decodable Mean Estimation in Nearly-PCA Time.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration.

[BibT_eX]

[DOI]

Michael B. Cohen

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Structured Logconcave Sampling with a Restricted Gaussian Oracle.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

2020

Semi-Streaming Bipartite Matching in Fewer Passes and Less Space.

[BibT_eX]

[DOI]

Yujia Jin

CoRR, 2020

Well-Conditioned Methods for Ill-Conditioned Systems: Linear Regression with Semi-Random Noise.

[BibT_eX]

[DOI]

CoRR, 2020

Composite Logconcave Sampling with a Restricted Gaussian Oracle.

[BibT_eX]

[DOI]

CoRR, 2020

Positive semidefinite programming: mixed, parallel, and width-independent.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing.

[BibT_eX]

[DOI]

Jerry Li

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Acceleration with a Ball Optimization Oracle.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Coordinate Methods for Matrix Games.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Information Exposure From Relational Background Knowledge on Social Media.

[BibT_eX]

[DOI]

Shuo Liu

Lisa Singh

Proceedings of the 7th IEEE International Conference on Data Science and Advanced Analytics, 2020

Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2020

2019

Locating Errors in Faulty Formulas.

[BibT_eX]

[DOI]

Sampath Kannan

ACM Trans. Algorithms, 2019

A Direct Õ(1/ε) Iteration Parallel Algorithm for Optimal Transport.

[BibT_eX]

[DOI]

CoRR, 2019

A Direct tilde{O}(1/epsilon) Iteration Parallel Algorithm for Optimal Transport.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Variance Reduction for Matrix Games.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

A Rank-1 Sketch for Matrix Multiplicative Weights.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

2018

Coordinate Methods for Accelerating 𝓁<sub>∞</sub> Regression and Faster Approximate Maximum Flow.

[BibT_eX]

[DOI]

CoRR, 2018

CoVeR: Learning Covariate-Specific Vector Representations with Tensor Decompositions.

[BibT_eX]

[DOI]

Teng Zhang

James Zou

Proceedings of the 35th International Conference on Machine Learning, 2018

Coordinate Methods for Accelerating ℓ∞ Regression and Faster Approximate Maximum Flow.

[BibT_eX]

[DOI]

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Optimally Learning Populations of Parameters.

[BibT_eX]

[DOI]

Weihao Kong

Gregory Valiant

CoRR, 2017

K-mer Set Memory (KSM) Motif Representation Enables Accurate Prediction of the Impact of Regulatory Variants.

[BibT_eX]

[DOI]

Proceedings of the Research in Computational Molecular Biology, 2017

Learning Populations of Parameters.

[BibT_eX]

[DOI]

Weihao Kong

Gregory Valiant

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

2016

Detecting Character Dependencies in Stochastic Models of Evolution.

[BibT_eX]

[DOI]

Deeparnab Chakrabarty

Sampath Kannan