Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > COMPLEXITY MEASURE:
Reports tagged with complexity measure:
TR09-025 | 11th March 2009
Arnaldo Moura, Igor Carboni Oliveira

A New Look at Some Classical Results in Computational Complexity

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


TR22-064 | 2nd May 2022
Deepanshu Kush, Shubhangi Saraf

Improved Low-Depth Set-Multilinear Circuit Lower Bounds

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




ISSN 1433-8092 | Imprint