Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Rüdiger Reischuk:

TR19-146 | 31st October 2019
Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau

Dynamic Kernels for Hitting Sets and Set Packing

Computing kernels for the hitting set problem (the problem of
finding a size-$k$ set that intersects each hyperedge of a
hypergraph) is a well-studied computational problem. For hypergraphs
with $m$ hyperedges, each of size at most~$d$, the best algorithms
can compute kernels of size $O(k^d)$ in ... more >>>

TR17-114 | 1st July 2017
Maciej Li\'skiewicz, Matthias Lutter, Rüdiger Reischuk

Proper Learning of k-term DNF Formulas from Satisfying Assignments

In certain applications there may only be positive samples available to
to learn concepts of a class of interest,
and this has to be done properly, i.e. the
hypothesis space has to coincide with the concept class,
and without false positives, i.e. the hypothesis always has be a subset ... more >>>

TR17-046 | 8th March 2017
Sebastian Berndt, Maciej Li\'skiewicz, Matthias Lutter, Rüdiger Reischuk

Learning Residual Alternating Automata

Residuality plays an essential role for learning finite automata.
While residual deterministic and nondeterministic
automata have been understood quite well, fundamental
questions concerning alternating automata (AFA) remain open.
Recently, Angluin, Eisenstat, and Fisman have initiated
a systematic study of residual AFAs and proposed an algorithm called AL*
-an extension of ... more >>>

TR15-010 | 19th January 2015
Maciej Li\'skiewicz, Rüdiger Reischuk, Ulrich Wölfel

Security Levels in Steganography -- Insecurity does not Imply Detectability

This paper takes a fresh look at security notions for steganography --
the art of encoding secret messages into unsuspicious covertexts
such that an adversary cannot distinguish the resulting stegotexts from original covertexts.
Stegosystems that fulfill the security notion used so far, however, are quite inefficient.
This ... more >>>

ISSN 1433-8092 | Imprint