Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > COMPUTATIONAL COMPLEXITY:
Reports tagged with Computational Complexity:
TR97-017 | 5th May 1997
Marek Karpinski, Juergen Wirtgen, Alexander Zelikovsky

#### An Approximation Algorithm for the Bandwidth Problem on Dense Graphs

The bandwidth problem is the problem of numbering the vertices of a
given graph $G$ such that the maximum difference between the numbers
of adjacent vertices is minimal. The problem has a long history and
is known to be NP-complete Papadimitriou [Pa76]. Only few special
cases ... more >>>

TR97-041 | 18th September 1997
Marek Karpinski, Juergen Wirtgen

#### On Approximation Hardness of the Bandwidth Problem

The bandwidth problem is the problem of enumerating
the vertices of a given graph $G$ such that the maximum
difference between the numbers of
adjacent vertices is minimal. The problem has a long
history and a number of applications
and is ... more >>>

TR19-150 | 24th October 2019
Stanislav Žák

#### A Logical Characteristic of Read-Once Branching Programs

We present a mathematical model of the intuitive notions such as the
knowledge or the information arising at different stages of
computations on branching programs (b.p.). The model has two
appropriate
properties:\\
i) The "knowledge" arising at a stage of computation in question is
derivable from the "knowledge" arising ... more >>>

TR22-056 | 18th April 2022
Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand

#### Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity

The classical coding theorem in Kolmogorov complexity states that if an $n$-bit string $x$ is sampled with probability $\delta$ by an algorithm with prefix-free domain then K$(x) \leq \log(1/\delta) + O(1)$. In a recent work, Lu and Oliveira [LO21] established an unconditional time-bounded version of this result, by showing that ... more >>>

ISSN 1433-8092 | Imprint