Showing cs.CCShow all
3 papers · 1 filter
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.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…
cs.CC2015
Read-once polynomials: 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 expresse…