Arnaldo Moura, Igor Carboni Oliveira

We propose a generalization of the traditional algorithmic space and

time complexities. Using the concept introduced, we derive an

unified proof for the deterministic time and space hierarchy

theorems, now stated in a much more general setting. This opens the

possibility for the unification and generalization of other results

that ...
more >>>

Deepanshu Kush, Shubhangi Saraf

In this paper, we prove strengthened lower bounds for constant-depth set-multilinear formulas. More precisely, we show that over any field, there is an explicit polynomial $f$ in VNP defined over $n^2$ variables, and of degree $n$, such that any product-depth $\Delta$ set-multilinear formula computing $f$ has size at least $n^{\Omega ... more >>>