Rusins Freivalds (Ed.)

Randomized Algorithms

Proceedings of International Workshop Brno, Czech Republik, August 27-28, 1998

• Title
• Preface

Invited papers:

Marek Karpinski:

• On the computational power of randomized branching programs

Gilles Brassard, Claude Crépeau, Dominic Mayers and Louis Salvail:

• The security of quantum bit commitment schemes

Andris Ambainis:

• Randomization in learning theory

Regular papers:

Farid Ablayev, Marek Karpinski and Rustam Mubarakzjanov:

• On BPP versus NP$\bigcup $coNP for ordered read-once branching programs

Eric Allender and Shiyu Zhou:

• Uniform inclusions in nondeterministic logspace

Richard F. Bonner:

• Randomization of positive linear learning algorithms in Banach function lattices

Dainis Geidmanis, Janis Kaneps and Tomas Larfeldt :

• Single-letter languages accepted by alternating and probabilistic pushdown automata

Anssi Kautonen, Ville Leppanen and Martti Penttonen :

• Thinning Protocols for routing h-relations in complete networks

Bruce Litow and Olivier de Vel :

• On digital images which cannot be generated by small generalised stochastic automata

Boris D. Lubachevsky :

• Why hard disks pack easier

Michele Mosca :

• Quantum searching, counting and amplitude amplification by eigenvector analysis

Marius Zimand:

• Efficient privatization of random bits

---

ISSN 1433-8092 | Imprint