Surveys and other writings

1. Recent progress on scaling algorithms and applications
   Ankit Garg, Rafael Oliveira
   EATCS complexity column (June 2018)
   
   

Publications

1. 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
   ITCS 2024
   
   

2. Low-depth arithmetic circuit lower bounds via shifted partials
   Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey
   ICALP 2023
   
   

3. Learning Generalized Depth Three Arithmetic Circuits in the Non-Degenerate Case
   Vishwas Bhargava, Ankit Garg, Neeraj Kayal, Chandan Saha
   RANDOM 2022
   
   

4. Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness
   Ankit Garg, Robin Kothari, Praneeth Netrapalli, Suhail Sherif
   NeurIPS 2021, QIP 2022
   
   

5. Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture
   Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif
   FSTTCS 2021
   
   

6. No quantum speedup over gradient descent for non-smooth convex optimization
   Ankit Garg, Robin Kothari, Praneeth Netrapalli, Suhail Sherif
   ITCS 2021, QIP 2021
   
   

7. Scalar Poincaré implies Matrix Poincaré
   Ankit Garg, Tarun Kathuria, Nikhil Srivastava
   Electronic Communications in Probability 2021
   
   

8. Learning sums of powers of low-degree polynomials in the non-degenerate case
   Ankit Garg, Neeraj Kayal, Chandan Saha
   FOCS 2020
   
   

9. Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings
   Ankit Garg, Christian Ikenmeyer, Visu Makam, Rafael Oliveira, Michael Walter, Avi Wigderson
   CCC 2020
   
   

10. Computational Extractors with Negligible Error in the CRS Model
    Ankit Garg, Yael Tauman Kalai, Dakshita Khurana
    EUROCRYPT 2020
    
    

11. 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 Oliveira, Michael Walter, Avi Wigderson
    FOCS 2019
    
    

12. More barriers for rank methods, via a "numeric to symbolic" transfer
    Ankit Garg, Visu Makam, Rafael Oliveira, Avi Wigderson
    FOCS 2019
    
    

13. Determinant equivalence test over finite fields and over Q
    Ankit Garg, Nikhil Gupta, Neeraj Kayal, Chandan Saha
    ICALP 2019
    
    

14. Classical lower bounds from quantum upper bounds
    Shalev Ben-David, Adam Bouland, Ankit Garg, Robin Kothari
    FOCS 2018, QIP 2018
    
    

15. Efficient algorithms for tensor scaling, quantum marginals and moment polytopes
    Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Oliveira, Michael Walter, Avi Wigderson
    FOCS 2018
    
    

16. Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing
    Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Oliveira, Avi Wigderson
    STOC 2018
    
    

17. A Matrix Expander Chernoff Bound
    Ankit Garg, Yin Tat Lee, Zhao Song, Nikhil Srivastava
    STOC 2018
    
    

18. Monotone Circuit Lower Bounds from Resolution
    Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov
    STOC 2018
    
    

19. Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory
    Peter Bürgisser, Ankit Garg, Rafael Oliveira, Michael Walter, Avi Wigderson
    ITCS 2018
    
    

20. Barriers for Rank Methods in Arithmetic Complexity
    Klim Efremenko, Ankit Garg, Rafael Oliveira, Avi Wigderson
    ITCS 2018
    
    

21. Separating quantum communication and approximate rank
    Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain, Robin Kothari, Troy Lee
    CCC 2017, QIP 2018
    
    

22. Rank bounds for design matrices with block entries and geometric applications
    Zeev Dvir, Ankit Garg, Rafael Oliveira, József Solymosi
    Discrete Analysis (March 2018)
    
    

23. Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via Operator Scaling
    Ankit Garg, Leonid Gurvits, Rafael Oliveira, Avi Wigderson
    STOC 2017, Geometric and Functional Analysis (Feb 2018)
    
    

24. Operator scaling: theory and applications
    Ankit Garg, Leonid Gurvits, Rafael Oliveira, Avi Wigderson
    FOCS 2016, QIP 2017
    
    

25. 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
    STOC 2016
    
    

26. Expected communication cost of distributed quantum tasks
    Anurag Anshu, Ankit Garg, Aram Harrow, Penghui Yao
    TQC 2016, IEEE Transactions on Information Theory (Nov 2018)
    
    

27. Near-optimal bounds on bounded-round quantum communication complexity of disjointness
    Mark Braverman, Ankit Garg, Young Kun Ko, Jieming Mao, Dave Touchette
    FOCS 2015, QIP 2016, SICOMP (Dec 2018)
    
    

28. Small value parallel repetition for general games
    Mark Braverman, Ankit Garg
    STOC 2015
    
    

29. On Communication Cost of Distributed Statistical Estimation and Dimensionality
    Ankit Garg, Tengyu Ma, Huy L. Nguyen
    NIPS 2014 (Oral)
    
    

30. Public vs private coin in bounded-round information
    Mark Braverman, Ankit Garg
    ICALP 2014
    
    

31. From information to exact communication
    Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein
    STOC 2013
    
    

32. Information lower bounds via self-reducibility
    Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein
    CSR 2013 (Best Paper)
    
    

33. Constructive extensions of two results on graphic sequences
    Ankit Garg, Arpit Goel, Amitabha Tripathi
    Discrete Applied Mathematics (Oct 2011)
    
    

34. CloudBridge: on integrated hardware-software consolidation
    Aritra Sen, Ankit Garg, Akshat Verma and Tapan Nayak
    ACM SIGMETRICS Performance Evaluation Review (Jan 2011)