All reports by Author Rainer Schuler:

__
TR04-059
| 21st June 2004
__

Beatrice List, Markus Maucher, Uwe Schöning, Rainer Schuler#### Randomized Quicksort and the Entropy of the Random Number Generator

__
TR03-010
| 13th February 2003
__

Sven Baumer, Rainer Schuler#### Improving a probabilistic 3-SAT Algorithm by Dynamic Search and Independent Clause Pairs

__
TR00-081
| 5th September 2000
__

Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe#### On the difference between polynomial-time many-one and truth-table reducibilities on distributional problems

__
TR98-037
| 29th June 1998
__

Johannes Köbler, Rainer Schuler#### Average-Case Intractability vs. Worst-Case Intractability

Beatrice List, Markus Maucher, Uwe Schöning, Rainer Schuler

The worst-case complexity of an implementation of Quicksort depends

on the random number generator that is used to select the pivot

elements. In this paper we estimate the expected number of

comparisons of Quicksort as a function in the entropy of the random

source. We give upper and lower bounds ...
more >>>

Sven Baumer, Rainer Schuler

The satisfiability problem of Boolean Formulae in 3-CNF (3-SAT)

is a well known NP-complete problem and the development of faster

(moderately exponential time) algorithms has received much interest

in recent years. We show that the 3-SAT problem can be solved by a

probabilistic algorithm in expected time O(1,3290^n).

more >>>

Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe

In this paper we separate many-one reducibility from truth-table

reducibility for distributional problems in DistNP under the

hypothesis that P neq NP. As a first example we consider the

3-Satisfiability problem (3SAT) with two different distributions

on 3CNF formulas. We show that 3SAT using a version of the

standard distribution ...
more >>>

Johannes Köbler, Rainer Schuler

We use the assumption that all sets in NP (or other levels

of the polynomial-time hierarchy) have efficient average-case

algorithms to derive collapse consequences for MA, AM, and various

subclasses of P/poly. As a further consequence we show for

C in {P(PP), PSPACE} that ...
more >>>