3 papers
cs.CC2020
Dynamic Complexity of Expansion
Samir Datta, Anuj Tawari, Yadu Vasudev
Dynamic Complexity was introduced by Immerman and Patnaik \cite{PatnaikImmerman97} (see also \cite{DongST95}). It has seen a resurgence of interest in the recent past, see \cite{Da…
cs.LO2020
Dynamic complexity of Reachability: How many changes can we handle?
Samir Datta, Pankaj Kumar, Anish Mukherjee +3
In 2015, it was shown that reachability for arbitrary directed graphs can be updated by first-order formulas after inserting or deleting single edges. Later, in 2018, this was exte…
cs.CC2016
Sums of read-once formulas: How many summands suffice?
Meena Mahajan, Anuj Tawari
An arithmetic read-once formula (ROF) is a formula (circuit of fan-out 1) over where each variable labels at most one leaf. Every multilinear polynomial can be expressed…