Surveys and other writings

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

Publications

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

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

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

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

5. 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
   
   

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

7. 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
   
   

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

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

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

11. 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
    
    

12. 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
    
    

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

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

15. 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
    
    

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

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

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

19. 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)
    
    

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

21. 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
    
    

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

23. 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)
    
    

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

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

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

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

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

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

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