16 citations · 20 across the 6 of their papers we have counts for
6 papers · 1 filter
Low-depth arithmetic circuit lower bounds via shifted partials
Prashanth Amireddy, Ankit Garg, Neeraj Kayal +2
We prove super-polynomial lower bounds for low-depth arithmetic circuits using the shifted partials measure [Gupta-Kamath-Kayal-Saptharishi, CCC 2013], [Kayal, ECCC 2012] and the a…
Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture
Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif
We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on input…
Learning sums of powers of low-degree polynomials in the non-degenerate case
Ankit Garg, Neeraj Kayal, Chandan Saha
We develop algorithms for writing a polynomial as sums of powers of low degree polynomials. Consider an -variate degree- polynomial which can be written as $$f = c_1Q_1^{…
More barriers for rank methods, via a "numeric to symbolic" transfer
Ankit Garg, Visu Makam, Rafael Oliveira +1
We prove new barrier results in arithmetic complexity theory, showing severe limitations of natural lifting (aka escalation) techniques. For example, we prove that even optimal ran…
Barriers for Rank Methods in Arithmetic Complexity
Klim Efremenko, Ankit Garg, Rafael Oliveira +1
Arithmetic complexity is considered simpler to understand than Boolean complexity, namely computing Boolean functions via logical gates. And indeed, we seem to have significantly m…
Near-optimal bounds on bounded-round quantum communication complexity of disjointness
Mark Braverman, Ankit Garg, Young Kun Ko +2
We prove a near optimal round-communication tradeoff for the two-party quantum communication complexity of disjointness. For protocols with rounds, we prove a lower bound of $\…