All reports by Author Anuj Tawari:

__
TR18-146
| 18th August 2018
__

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

__
TR18-020
| 30th January 2018
__

Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari#### Computing the maximum using $(\min, +)$ formulas

Comments: 1

__
TR15-204
| 14th December 2015
__

Meena Mahajan, Anuj Tawari#### Sums of read-once formulas: How many summands suffice?

Revisions: 2

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

Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari

We study computation by formulas over $(min, +)$. We consider the computation of $\max\{x_1,\ldots,x_n\}$

over $\mathbb{N}$ as a difference of $(\min, +)$ formulas, and show that size $n + n \log n$ is sufficient and necessary. Our proof also shows that any $(\min, +)$ formula computing the minimum of all ...
more >>>

Meena Mahajan, Anuj Tawari

An arithmetic read-once formula (ROF) is a formula (circuit of fan-out

1) over

$+, \times$ where each variable labels at most one leaf.

Every multilinear polynomial can be expressed as the sum of ROFs.

In this work, we prove, for certain multilinear polynomials,

a tight lower bound ...
more >>>