All reports by Author Nikhil Balaji:

__
TR23-163
| 30th October 2023
__

Nikhil Balaji, Samir Datta#### USSR is in P/poly

__
TR16-143
| 15th September 2016
__

Nikhil Balaji, Nutan Limaye, Srikanth Srinivasan#### An Almost Cubic Lower Bound for $\Sigma\Pi\Sigma$ Circuits Computing a Polynomial in VP

__
TR14-183
| 25th December 2014
__

Nikhil Balaji, Andreas Krebs, Nutan Limaye#### Skew Circuits of Small Width

__
TR13-177
| 10th December 2013
__

Eric Allender, Nikhil Balaji, Samir Datta#### Low-depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs

Revisions: 1

__
TR13-131
| 17th September 2013
__

Nikhil Balaji, Samir Datta#### Collapsing Exact Arithmetic Hierarchies

Revisions: 1

Nikhil Balaji, Samir Datta

The Sum of Square Roots (SSR) problem is the following computational problem: Given positive integers $a_1, \dots, a_k$, and signs $\delta_1, \dots, \delta_k \in \{-1, 1\}$, check if $\sum_{i=1}^k \delta_i \sqrt{a_i} > 0$. The problem is known to have a polynomial time algorithm on the real RAM model of computation, ... more >>>

Nikhil Balaji, Nutan Limaye, Srikanth Srinivasan

In this note, we prove that there is an explicit polynomial in VP such that any $\Sigma\Pi\Sigma$ arithmetic circuit computing it must have size at least $n^{3-o(1)}$. Up to $n^{o(1)}$ factors, this strengthens a recent result of Kayal, Saha and Tavenas (ICALP 2016) which gives a polynomial in VNP with ... more >>>

Nikhil Balaji, Andreas Krebs, Nutan Limaye

A celebrated result of Barrington (1985) proved that polynomial size, width-5 branching programs (BP) are equivalent in power to a restricted form of branching programs -- polynomial sized width-5 permutation branching programs (PBP), which in turn capture all of NC1. On the other hand it is known that width-3 PBPs ... more >>>

Eric Allender, Nikhil Balaji, Samir Datta

We present improved uniform TC$^0$ circuits for division, matrix powering, and related problems, where the improvement is in terms of ``majority depth'' (initially studied by Maciel and Therien). As a corollary, we obtain improved bounds on the complexity of certain problems involving arithmetic circuits, which are known to lie in ... more >>>

Nikhil Balaji, Samir Datta

We provide a uniform framework for proving the collapse of the hierarchy, $NC^1(\mathcal{C})$

for an exact arithmetic class $\mathcal{C}$ of polynomial degree. These hierarchies collapses all the way down to the third level of the ${AC}^0$-hierarchy, ${AC^0_3}(\mathcal{C})$. Our main collapsing exhibits are the classes \[\mathcal{C} \in \{{C}_={NC^1}, {C}_={L}, {C}_={SAC^1}, {C}_={P}\}.\]

more >>>