Ankit Garg

I am a fifth year PhD student in the Department of Computer Science at Princeton University. I am fortunate to be advised by Mark Braverman. Before coming here, I finished my undergraduate studies in the Department of Computer Science and Engineering at Indian Institute of Technology, Delhi.

I am interested in Theoretical Computer Science, particularly in applications of information theory in communication complexity and complexity theory. I am currently supported by a Simons Graduate Award in TCS and a Siebel Scholarship.

Ankit Garg,
Department of Computer Science,
Princeton University,
35, Olden Street,
Princeton, NJ - 08544



lastname AT cs dot princeton dot edu
lastname AT princeton dot edu

A deterministic polynomial time algorithm for non-commutative rational identity testing

- with Leonid Gurvits, Rafael Oliveira and Avi Wigderson

Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality

- with Mark Braverman, Tengyu Ma, Huy Nguyen and David Woodruff

Near-optimal bounds on bounded-round quantum communication complexity of disjointness

- with Mark Braverman, Young Kun Ko, Jieming Mao, Dave Touchette
56th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2015.
19th Conference on Quantum Information Processing, QIP 2016. [ECCC]

Small value parallel repetition for general games

- with Mark Braverman
47th Annual Symposium on the Theory of Computing, STOC 2015. [ECCC]

On Communication Cost of Distributed Statistical Estimation and Dimensionality

- with Tengyu Ma and Huy Nguyen
28th Annual Conference on Neural Information Processing Systems, NIPS 2014. Oral presentation [arxiv]

Public vs private coin in bounded-round information

- with Mark Braverman
41st International Colloquium on Automata, Languages, and Programming, ICALP 2014. [ECCC]

From information to exact communication

- with Mark Braverman, Denis Pankratov and Omri Weinstein
45th ACM Symposium on the Theory of Computing, STOC 2013. [ECCC]

Information lower bounds via self-reducibility

- with Mark Braverman, Denis Pankratov and Omri Weinstein
8th International Computer Science Symposium, CSR 2013. Best paper award [ECCC]
Undergraduate Research

Constructive extensions of two results on graphic sequences

- with Arpit Goel and Amitabha Tripathi
Discrete Applied Mathematics , 2011. You can find the paper here.

CloudBridge: on integrated hardware-software consolidation

- with Aritra Sen, Akshat Verma and Tapan Nayak
29th International Symposium on Computer Performance, Modeling, Measurement and Evaluation, 2011. Find it here.