Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR98-071 | 26th November 1998
Itsik Pe'er, Ron Shamir

The median problems for breakpoints are NP-complete

The breakpoint distance between two $n$-permutations is the number
of pairs that appear consecutively in one but not in the other. In
the median problem for breakpoints one is given a set of
permutations and has to construct a permutation that minimizes the
sum of breakpoint ... more >>>


TR98-070 | 7th December 1998
RĂ¼diger Reischuk

Can Large Fanin Circuits Perform Reliable Computations in the Presence of Noise?


For ordinary circuits with a fixed upper bound on the maximal fanin
of gates it has been shown that logarithmic redundancy is necessary and
sufficient to overcome random hardware faults.
Here, we consider the same question for unbounded fanin circuits that
in the noiseless case can compute ... more >>>


TR98-069 | 7th December 1998
RĂ¼diger Reischuk, Thomas Zeugmann

An Average-Case Optimal One-Variable Pattern Language Learner


A new algorithm for learning one-variable pattern languages from positive data
is proposed and analyzed with respect to its average-case behavior.
We consider the total learning time that takes into account all
operations till convergence to a correct hypothesis is achieved.

For almost all meaningful distributions
defining how ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint