Ainesh Bakshi

According to our database, Ainesh Bakshi authored at least 32 papers between 2013 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

High-Temperature Gibbs States are Unentangled and Efficiently Preparable.

Ainesh Bakshi, Allen Liu, Ankur Moitra, Ewin Tang

CoRR, 2024

File System Aging.

Alex Conway, Ainesh Bakshi, Arghya Bhattacharya, Rory Bennett, Yizheng Jiao, Eric Knorr, Yang Zhan, Michael A. Bender, William Jannen, Rob Johnson, Bradley C. Kuszmaul, Donald E. Porter, Jun Yuan, Martin Farach-Colton

CoRR, 2024

An Improved Classical Singular Value Transformation for Quantum Machine Learning.

Ainesh Bakshi, Ewin Tang

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

2023

A quasi-polynomial time algorithm for Multi-Dimensional Scaling via LP hierarchies.

Ainesh Bakshi, Vincent Cohen-Addad, Samuel B. Hopkins, Rajesh Jayaram, Silvio Lattanzi

CoRR, 2023

Learning quantum Hamiltonians at any temperature in polynomial time.

Ainesh Bakshi, Allen Liu, Ankur Moitra, Ewin Tang

CoRR, 2023

A New Approach to Learning Linear Dynamical Systems.

Ainesh Bakshi, Allen Liu, Ankur Moitra, Morris Yau

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Near-Linear Time Algorithm for the Chamfer Distance.

Ainesh Bakshi, Piotr Indyk, Rajesh Jayaram, Sandeep Silwal, Erik Waingarten

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

Tensor Decompositions Meet Control Theory: Learning General Mixtures of Linear Dynamical Systems.

Ainesh Bakshi, Allen Liu, Ankur Moitra, Morris Yau

Proceedings of the International Conference on Machine Learning, 2023

Subquadratic Algorithms for Kernel Matrices via Kernel Density Estimation.

Ainesh Bakshi, Piotr Indyk, Praneeth Kacham, Sandeep Silwal, Samson Zhou

Proceedings of the Eleventh International Conference on Learning Representations, 2023

Krylov Methods are (nearly) Optimal for Low-Rank Approximation.

Ainesh Bakshi, Shyam Narayanan

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

2022

Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation.

Ainesh Bakshi, Piotr Indyk, Praneeth Kacham, Sandeep Silwal, Samson Zhou

CoRR, 2022

Low-Rank Approximation with 1/ε^1/3 Matrix-Vector Products.

Ainesh Bakshi, Kenneth L. Clarkson, David P. Woodruff

CoRR, 2022

Robustly learning mixtures of <i>k</i> arbitrary Gaussians.

Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, Santosh S. Vempala

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

Low-rank approximation with <i>1/ε^1/3</i> matrix-vector products.

Ainesh Bakshi, Kenneth L. Clarkson, David P. Woodruff

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

2021

Robust linear regression: optimal rates in polynomial time.

Ainesh Bakshi, Adarsh Prasad

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time.

Ainesh Bakshi, Pravesh K. Kothari

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

Learning a Latent Simplex in Input Sparsity Time.

Ainesh Bakshi, Chiranjib Bhattacharyya, Ravi Kannan, David P. Woodruff, Samson Zhou

Proceedings of the 9th International Conference on Learning Representations, 2021

2020

Robustly Learning Mixtures of k Arbitrary Gaussians.

Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, Santosh S. Vempala

CoRR, 2020

Outlier-Robust Clustering of Non-Spherical Mixtures.

Ainesh Bakshi, Pravesh Kothari

CoRR, 2020

List-Decodable Subspace Recovery via Sum-of-Squares.

Ainesh Bakshi, Pravesh Kothari

CoRR, 2020

Outlier-Robust Clustering of Gaussians and Other Non-Spherical Mixtures.

Ainesh Bakshi, Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, Sushrut Karmalkar, Pravesh K. Kothari

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

Robust and Sample Optimal Algorithms for PSD Low Rank Approximation.

Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff

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

Testing Positive Semi-Definiteness via Random Submatrices.

Ainesh Bakshi, Nadiia Chepurko, Rajesh Jayaram

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

Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams.

Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff

Proceedings of the Approximation, 2020

2019

Robust Communication-Optimal Distributed Clustering Algorithms.

Pranjal Awasthi, Ainesh Bakshi, Maria-Florina Balcan, Colin White, David P. Woodruff

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Learning Two Layer Rectified Neural Networks in Polynomial Time.

Ainesh Bakshi, Rajesh Jayaram, David P. Woodruff

Proceedings of the Conference on Learning Theory, 2019

2018

Sublinear Time Low-Rank Approximation of Distance Matrices.

Ainesh Bakshi, David P. Woodruff

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

2017

How to Fragment Your File System.

Alex Conway, Ainesh Bakshi, Yizheng Jiao, Yang Zhan, Michael A. Bender, William Jannen, Rob Johnson, Bradley C. Kuszmaul, Donald E. Porter, Jun Yuan, Martin Farach-Colton

login Usenix Mag., 2017

File Systems Fated for Senescence? Nonsense, Says Science!

Alexander Conway, Ainesh Bakshi, Yizheng Jiao, William Jannen, Yang Zhan, Jun Yuan, Michael A. Bender, Rob Johnson, Bradley C. Kuszmaul, Donald E. Porter, Martin Farach-Colton

Proceedings of the 15th USENIX Conference on File and Storage Technologies, 2017

2014

A Novel Feature Selection and Extraction Technique for Classification.

Kratarth Goel, Raunaq Vohra, Ainesh Bakshi

Proceedings of the 14th International Conference on Frontiers in Handwriting Recognition, 2014

Non Dominated Sorting Genetic Algorithm for Chance Constrained Supplier Selection Model with Volume Discounts.

Remica Aggarwal, Ainesh Bakshi

Proceedings of the Intelligent Information and Database Systems - 6th Asian Conference, 2014

2013

Autonomous Robot Navigation: Path Planning on a Detail-Preserving Reduced-Complexity Representation of 3D Point Clouds.

Rohit Sant, Ninad Kulkarni, Ainesh Bakshi, Salil Kapur, Kratarth Goel

Proceedings of the Computer Vision Systems - 9th International Conference, 2013