Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > CLOSURE PROPERTIES:
Reports tagged with closure properties:
TR95-005 | 1st January 1995
Maciej Liskiewicz, RĂ¼diger Reischuk

The Sublogarithmic Alternating Space World

This paper tries to fully characterize the properties and relationships
of space classes defined by Turing machines that use less than
logarithmic space - may they be deterministic,
nondeterministic or alternating (DTM, NTM or ATM).

We provide several examples of specific languages ... more >>>


TR00-075 | 7th September 2000
Andreas Klein, Martin Kutrib

Deterministic Turing Machines in the Range between Real-Time and Linear-Time

Deterministic k-tape and multitape Turing machines with one-way,
two-way and without a separated input tape are considered. We
investigate the classes of languages acceptable by such devices with
time bounds of the form n+r(n) where r in o(n) is a sublinear
function. It is shown that there ... more >>>


TR04-024 | 26th March 2004
Thomas Thierauf, Thanh Minh Hoang

On Closure Properties of GapL

Revisions: 1 , Comments: 1

We show necessary and sufficient conditions that
certain algebraic functions like the rank or the signature
of an integer matrix can be computed in GapL.

more >>>

TR25-083 | 24th June 2025
C.S. Bhargav, Prateek Dwivedi, Nitin Saxena

A primer on the closure of algebraic complexity classes under factoring

Polynomial factorization is a fundamental problem in computational algebra. Over the past half century, a variety of algorithmic techniques have been developed to tackle different variants of this problem. In parallel, algebraic complexity theory classifies polynomials into complexity classes based on their perceived `hardness'. This raises a natural question: Do ... more >>>


TR25-084 | 28th June 2025
Somnath Bhattacharjee, Mrinal Kumar, Shanthanu Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf

Closure under factorization from a result of Furstenberg

We show that algebraic formulas and constant-depth circuits are \emph{closed} under taking factors. In other words, we show that if a multivariate polynomial over a field of characteristic zero has a small constant-depth circuit or formula, then all its factors can be computed by small constant-depth circuits or formulas ... more >>>




ISSN 1433-8092 | Imprint