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


TR25-135 | 13th September 2025
Jules Armand, Prateek Dwivedi, Nutan Limaye, Magnus Rahbek Dalgaard Hansen, Srikanth Srinivasan, Sébastien Tavenas

On Closure Properties of Read-Once Oblivious Algebraic Branching Programs

We investigate the closure properties of read-once oblivious Algebraic Branching Programs (roABPs) under various natural algebraic operations and prove the following.
- Non-closure under factoring: There is a sequence of explicit polynomials $(f_n(x_1,\ldots, x_n))_n$ that have poly(n)-sized roABPs such that some irreducible factor of $f_n$ does not have roABPs ... more >>>




ISSN 1433-8092 | Imprint