Ankit Garg

According to our database, Ankit Garg authored at least 37 papers between 2013 and 2026.

Collaborative distances:

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

2026

On Strengths and Limitations of Single-Vector Embeddings.

Archish S, Mihir Agarwal, Ankit Garg, Neeraj Kayal, Kirankumar Shiragur

CoRR, March, 2026

Incorporating Token Importance in Multi-Vector Retrieval.

Archish S, Ankit Garg, Kirankumar Shiragur, Neeraj Kayal

Proceedings of the Fortieth AAAI Conference on Artificial Intelligence, 2026

2024

Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning.

Pritam Chandra, Ankit Garg, Neeraj Kayal, Kunal Mittal, Tanmay Sinha

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023

Low-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization.

Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

Low-depth arithmetic circuit lower bounds via shifted partials.

Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey

Electron. Colloquium Comput. Complex., 2022

Learning Generalized Depth Three Arithmetic Circuits in the Non-Degenerate Case.

Vishwas Bhargava, Ankit Garg, Neeraj Kayal, Chandan Saha

Proceedings of the Approximation, 2022

2021

Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness.

Ankit Garg, Robin Kothari, Praneeth Netrapalli, Suhail Sherif

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

No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization.

Ankit Garg, Robin Kothari, Praneeth Netrapalli, Suhail Sherif

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

2020

Operator Scaling: Theory and Applications.

Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson

Found. Comput. Math., 2020

Learning sums of powers of low-degree polynomials in the non-degenerate case.

Ankit Garg, Neeraj Kayal, Chandan Saha

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

Search Problems in Algebraic Complexity, GCT, and Hardness of Generators for Invariant Rings.

Ankit Garg, Christian Ikenmeyer, Visu Makam, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson

Proceedings of the 35th Computational Complexity Conference, 2020

2019

Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings.

Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, Avi Wigderson

Electron. Colloquium Comput. Complex., 2019

Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes.

Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson

CoRR, 2019

Determinant Equivalence Test over Finite Fields and over Q.

Ankit Garg, Nikhil Gupta, Neeraj Kayal, Chandan Saha

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

More Barriers for Rank Methods, via a "numeric to Symbolic" Transfer.

Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, Avi Wigderson

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Towards a Theory of Non-Commutative Optimization: Geodesic 1st and 2nd Order Methods for Moment Maps and Polytopes.

Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Recent progress on scaling algorithms and applications.

Ankit Garg, Rafael Mendes de Oliveira

Electron. Colloquium Comput. Complex., 2018

A matrix expander Chernoff bound.

Ankit Garg, Yin Tat Lee, Zhao Song, Nikhil Srivastava

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Monotone circuit lower bounds from resolution.

Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing.

Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Mendes de Oliveira, Avi Wigderson

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Barriers for Rank Methods in Arithmetic Complexity.

Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Alternating Minimization, Scaling Algorithms, and the Null-Cone Problem from Invariant Theory.

Peter Bürgisser, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Efficient Algorithms for Tensor Scaling, Quantum Marginals, and Moment Polytopes.

Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson

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

Classical Lower Bounds from Quantum Upper Bounds.

Shalev Ben-David, Adam Bouland, Ankit Garg, Robin Kothari

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

2017

Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling.

Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Separating Quantum Communication and Approximate Rank.

Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain, Robin Kothari, Troy Lee

Proceedings of the 32nd Computational Complexity Conference, 2017

2016

Information Theoretic Relaxations in Complexity Theory.

Ankit Garg

PhD thesis, 2016

Algorithmic aspects of Brascamp-Lieb inequalities.

Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson

CoRR, 2016

Rank bounds for design matrices with block entries and geometric applications.

Zeev Dvir, Ankit Garg, Rafael Oliveira, József Solymosi

CoRR, 2016

Communication lower bounds for statistical estimation problems via a distributed data processing inequality.

Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, David P. Woodruff

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing.

Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Small Value Parallel Repetition for General Games.

Mark Braverman, Ankit Garg

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness.

Mark Braverman, Ankit Garg, Young Kun-Ko, Jieming Mao, Dave Touchette

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

On Communication Cost of Distributed Statistical Estimation and Dimensionality.

Ankit Garg, Tengyu Ma, Huy L. Nguyen

Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

Public vs Private Coin in Bounded-Round Information.

Mark Braverman, Ankit Garg

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

From information to exact communication.

Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein

Proceedings of the Symposium on Theory of Computing Conference, 2013

Information Lower Bounds via Self-reducibility.

Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein

Proceedings of the Computer Science - Theory and Applications, 2013