Titlebook: STACS 2000; 17th Annual Symposiu Horst Reichel,Sophie Tison Conference proceedings 2000 Springer-Verlag Berlin Heidelberg 2000 Automat.algo

obstinate

The Boolean Hierarchy of NP-Partitions,. Whereas the structure of the latter hierarchy is rather simple the structure of the boolean hierarchy of .-partitions over NP for . ≥ 3 turns out to be much more complicated. We establish the Embedding Conjecture which enables us to get a complete idea of this structure. This conjecture is supported by several partial results.

组成

起波澜

licence

使熄灭

Average-Case Quantum Query Complexity,assical algorithms. Under non-uniform distributions the gap can even be super-exponential. We also prove some general bounds for average-case complexity and show that the average-case quantum complexity of MAJORITY under the uniform distribution is nearly quadratically better than the classical complexity.

Ebct207

Bias Invariance of Small Upper Spans,ed upwards.) The proof introduces two new techniques, namely, the . of a martingale for one probability measure to a martingale for an induced probability measure, and a new, improved . of one bias sequence to another. Consequences for the BPP versus E problem and small span theorems are derived.

HERTZ

Succinct Representations of Model Based Belief Revision,ly, we show that Dalal’s and Weber’s operators can be compiled one into the other via a formalism whose model checking is in NP. All of our results also hold when iterated revision, for one or more of the operators, is considered.

天真

congenial

About Cube-Free Morphisms,unpublished result of Leconte: A binary morphism is cube-free if and only if the images of all cube-free words of length 7 are cube-free..We also prove that, given an alphabet . containing at least two letters, the monoid of cube-free endomorphisms on . is not finitely generated.

occurrence

The Data Broadcast Problem with Preemption,ed. We show that this problem is .-hard, even in the simple setting where the broadcast costs are zero, and give some practical 2-approximation algorithms for broadcasting messages. We also show that preemption can improve the quality of the broadcast by an arbitrary factor.