Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Juraj Hromkovic:

TR21-049 | 1st April 2021
Juraj Hromkovic

Kolmogorov complexity and nondeterminism versus determinism for polynomial time computations

Revisions: 1

We call any consistent and sufficiently powerful formal theory that enables to algorithmically in polynomial time verify whether a text is a proof \textbf{efficiently verifiable mathematics} (ev-mathematics). We study the question whether nondeterminism is more powerful than determinism for polynomial time computations in the framework of ev-mathematics. Our main results ... more >>>

TR15-159 | 28th September 2015
Juraj Hromkovic

Why the Concept of Computational Complexity is Hard for Verifiable Mathematics

Mathematics was developed as a strong research instrument with fully verifiable argumentations. We call any formal theory based on syntactic rules that enables to algorithmically verify for any given text whether it is a proof or not algorithmically verifiable mathematics (AV-mathematics for short). We say that a decision problem L ... more >>>

TR12-162 | 26th October 2012
Hans-Joachim Boeckenhauer, Juraj Hromkovic, Dennis Komm, Sacha Krug, Jasmin Smula, Andreas Sprock

The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity

Revisions: 1

The advice complexity of an online problem describes the additional information both necessary and sufficient for online algorithms to compute solutions of a certain quality. In this model, an oracle inspects the input before it is processed by an online algorithm. Depending on the input string, the oracle prepares an ... more >>>

TR01-066 | 28th September 2001
Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger

On Multipartition Communication Complexity

We study k-partition communication protocols, an extension
of the standard two-party best-partition model to k input partitions.
The main results are as follows.

1. A strong explicit hierarchy on the degree of
non-obliviousness is established by proving that,
using k+1 partitions instead of k may decrease
the communication complexity from ... more >>>

TR00-076 | 24th August 2000
Juraj Hromkovic, Juhani Karhumaki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert

Measures of Nondeterminism in Finite Automata

While deterministic finite automata seem to be well understood, surprisingly
many important problems
concerning nondeterministic finite automata (nfa's) remain open.

One such problem area is the study of different measures of nondeterminism in
finite automata and the
estimation of the sizes of minimal nondeterministic finite automata. In this
paper the ... more >>>

TR00-027 | 11th April 2000
Pavol Duris, Juraj Hromkovic, Katsushi Inoue

A Separation of Determinism, Las Vegas and Nondeterminism for Picture Recognition

The investigation of the computational power of randomized computations
is one of the central tasks of current complexity and algorithm theory.
In this paper for the first time a "strong" separation between the power
of determinism, Las Vegas randomization, and nondeterminism for a compu-
ting model is proved. The computing ... more >>>

TR99-031 | 2nd September 1999
Hans-Joachim Böckenhauer, Juraj Hromkovic, Ralf Klasing, Sebastian Seibert, Walter Unger

Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem

The investigation of the possibility to efficiently compute
approximations of hard optimization problems is one of the central
and most fruitful areas of current algorithm and complexity theory.
The aim of this paper is twofold. First, we introduce the notion of
stability of approximation algorithms. This notion is shown to ... more >>>

TR99-007 | 10th March 1999
Juraj Hromkovic, Georg Schnitger

On the Power of Las Vegas II: Two-Way Finite Automata

The investigation of the computational power of randomized
computations is one of the central tasks of current complexity and
algorithm theory. This paper continues in the comparison of the computational
power of LasVegas computations with the computational power of deterministic
and nondeterministic ones. While for one-way ... more >>>

TR97-029 | 20th August 1997
Pavol Duris, Juraj Hromkovic, Jose' D. P. Rolim, Georg Schnitger

On the Power of Las Vegas for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations

The study of the computational power of randomized
computations is one of the central tasks of complexity theory. The
main goal of this paper is the comparison of the power of Las Vegas
computation and deterministic respectively nondeterministic
computation. We investigate the power of Las Vegas computation for ... more >>>

ISSN 1433-8092 | Imprint