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 >>>

Elmar Böhler, Christian Glaßer, Daniel Meister

SBP is a probabilistic promise class located

between MA and AM \cap BPPpath. The first

part of the paper studies the question of whether

SBP has many-one complete sets. We relate

this question to the existence of uniform

enumerations. We construct an oracle relative to

which SBP and AM do ...
more >>>

Elmar Böhler

A clone is a set of functions that is closed under generalized substitution.

The set FP of functions being computable deterministically in polynomial

time is such a clone. It is well-known that the set of subclones of every

clone forms a lattice. We study the lattice below FP, which ...
more >>>

Henning Wunderlich

In an unpublished Russian manuscript Razborov proved that a matrix family with high

rigidity over a finite field would yield a language outside the polynomial hierarchy

in communication complexity.

We present an alternative proof that strengthens the original result in several ways.

In particular, we replace rigidity by the strictly ...
more >>>