
Ainesh Bakshi
Email: abakshi (at) cs (dot) cmu (dot) edu
Office: GHC 5103

I am a third year PhD student at Carnegie Mellon University. I am extremely fortunate to be coadvised by Pravesh Kothari and David Woodruff. I am broadly interested in Theoretical Computer Science and
my current research interests are algorithms for randomized linear algebra, convex relaxations, the sumofsquares meta algorithm and provable guarantees for learning problems.
Previously, I was an undergrad at Rutgers, New Brunswick, where I had the pleasure of working with Martin FarachColton
and Pranjal Awasthi on external memory algorithms and clustering respectively.
Publications
 Robust Linear Regression: Optimal Rates in Polynomial Time
Ainesh Bakshi, Adarsh Prasad
Preprint [arXiv] .
 ListDecodable Subspace Recovery via SumofSquares
Ainesh Bakshi, Pravesh Kothari
Preprint [arXiv].
 Testing Positive SemiDefiniteness via Random Submatrices
Ainesh Bakshi, Nadiia Chepurko, Rajesh Jayaram
FOCS 2020 (to appear) [arXiv].
 OutlierRobust Clustering of Nonspherical Mixtures
Ainesh Bakshi, Pravesh Kothari
FOCS 2020 (to appear) [arXiv]
Conference version to be merged with this paper.
 Robust and Sample Optimal Algorithms for PSD Low Rank Approximation
Ainesh Bakshi, Nadiia Chepurko, David Woodruff
FOCS 2020 (to appear) [arXiv], [Talk @ WOLA'20].
 Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams
Ainesh Bakshi, Nadiia Chepurko, David Woodruff
APPROX 2020 (to appear) [arXiv].
 Robust CommunicationOptimal Distributed Clustering Algorithms
Pranjal Awasthi, Ainesh Bakshi, Nina Balcan, Colin White, David Woodruff
ICALP 2019 [arXiv].
 Learning Two Layer Rectified Neural Networks in Polynomial Time
Ainesh Bakshi, Rajesh Jayaram,
David Woodruff
COLT 2019 [arXiv].
 Sublinear Time LowRank Approximation of Distance Matrices
Ainesh Bakshi,
David Woodruff
NeurIPS 2018, Selected for Spotlight Presentation [arXiv], [Talk @ CMU TL].
Undergraduate Work

"How to Fragment your File System"
A. Conway,
A. Bakshi,
Y. Jiao,
Y. Zhan,
M. Bender,
W. Jannen,
R. Johnson,
B. Kuzmaul,
D. Porter,
J. Yuan,
M. FarachColton
;login: magazine, vol. 42(2), 2017.

"File Systems fated for Senescence? Nonsense, Says Science!"
A. Conway,
A. Bakshi,
Y. Jiao,
Y. Zhan,
M. Bender,
W. Jannen,
R. Johnson,
B. Kuzmaul,
D. Porter,
J. Yuan,
M. FarachColton
Proceedings of the 15th USENIX Conference on File and Storage Technologies (FAST '17), Santa Clara, CA, February 2017.

"Non Dominated Sorting Genetic Algorithm for Chance Constrained Supplier Selection Model with Volume Discounts"
R. Agarwal,
A. Bakshi
ACIIDS, Lecture Notes in Computer Science pp. 465–474, Apr 2014.

"A Novel Feature Selection and Extraction Technique for Classification"
K. Goel,
R. Vohra
A. Bakshi
ICFHR 2014, pp. 104109.

"Autonomous Robot Navigation: Path Planning on a DetailPreserving ReducedComplexity Representation of 3D Point Clouds"
R. Sant,
N. Kulkarni,
A. Bakshi,
K. Goel,
S. Kapur
ICFHR 2014, pp. 104109.
Teaching