All reports by Author Prajakta Nimbhorkar:

__
TR24-041
| 1st March 2024
__

Pranav Bisht, Nikhil Gupta, Prajakta Nimbhorkar, Ilya Volkovich#### Launching Identity Testing into (Bounded) Space

__
TR18-146
| 18th August 2018
__

Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari#### Shortest path length with bounded-alternation $(\min, +)$ formulas

Pranav Bisht, Nikhil Gupta, Prajakta Nimbhorkar, Ilya Volkovich

In this work, we initiate the study of the space complexity of the Polynomial Identity Testing problem (PIT).

First, we observe that the majority of the existing (time-)efficient ``blackbox'' PIT algorithms already give rise to space-efficient ``whitebox'' algorithms for the respective classes of arithmetic formulas via a space-efficient ...
more >>>

Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari

We study bounded depth $(\min, +)$ formulas computing the shortest path polynomial. For depth $2d$ with $d \geq 2$, we obtain lower bounds parametrized by certain fan-in restrictions on all $+$ gates except those at the bottom level. For depth $4$, in two regimes of the parameter, the bounds are ... more >>>