The aim of this workshop is to discuss recent theoretical results and experiments related to randomized and quantum algorithms. Topics of interest include, but are not limited to: random walk, quantum walk, probabilistic and quantum finite automata, quantum automata with mixed states, description of probabilistic and quantum finite automata by means of second order logics.
The workshop will be co-located with Joint MFCS & CSL 2010, 23-27 August 2010, Brno, Czech republic.
Call for papers
Submissions of interesting theoretical and mathematical results related to constraints are encouraged. Topics include (but are not limited to):
• Randomized algorithms and their complexity.
• Quantum algorithms and their complexity.
• Languages recognizable by finite quantum automata of all types.
• Expressibility of recognizable languages by statements of second-order logic.
• Randomized and quantum query algorithms.
• Postselection quantum automata and other “fantasy” models of computation.
Survey talks, preliminary results, developments of published results, and work in progress are welcome.
Submissions should be submitted by sending a PDF file of the paper in LNCS format of Springer not exceeding 12 pages to: Rusins.Freivalds@mii.lu.lv.
Joint submissions to conferences other than MFCS 2010 are not allowed. It is assumed that if a paper is accepted to MFCS 2010, it is automatically withdrawn from our workshop.