13-15 September 2007
Zuerich, Switzerland
***************************************************************
Call for Papers
SAGA 2007
4th Symposium on Stochastic Algorithms, Foundations, and Applications
Zurich, September 13-15, 2007
http://saga07.inf.ethz.ch
Organised by ETH Zurich,
Department of Computer Science
CH-8092 Zurich, Switzerland
***************************************************************
Scope:
The 4th Symposium on Stochastic Algorithms, Foundations and
Applications (SAGA'07) will be held September 13-15, 2007, at ETH
Zurich (in Switzerland). It offers the opportunity to present original
research on the design and analysis of randomized algorithms,
complexity theory of randomized computations, random combinatorial
structures, implementation, experimental evaluation and real-world
application of stochastic algorithms. In particular, the focus of
SAGA'07 is on investigating the power of randomization in
algorithmics, and on the theory of stochastic processes especially
within realistic scenarios and applications. Thus, the interest of the
symposium ranges from the study of theoretical fundamentals of
randomized computation to experimental algorithmics related to
stochastic approaches.
Topics:
Original research papers (including significant work-in-progress and
work identifying and exploring directions of future research) or
state-of-the-art surveys are invited on all aspects of algorithms
employing stochastic components, including, but not limited to:
- Stochastic algorithms in combinatorial optimization
- Stochastic local search methods
- Design and analysis of randomized algorithms
- Fingerprinting and abundance of witnesses
- Random sampling and probabilistic methods
- Applications of Lovasz' local lemma
- Amplification
- Randomized rounding
- Stochastic algorithms in bioinformatics
- Machine learning methods
- Stochastic automata
- Evolvability and self-replication
- Average-case behavior and experimental analysis
- Real-world applications
- Pseudorandomness and derandomization
- Complexity of randomized computation, Las Vegas and Monte Carlo
- Quantum computation as a generalization of randomization
- Randomized communication
- Randomization in cryptology
- Algorithms in number theory
- Lower bounds on complexity and expected complexity
- Random combinatorial structures
- Random walks
- Property testing
- Smoothed analysis
- Probabilistic proof systems
Submissions:
Authors are invited to submit an extended abstract or full paper of at
most 12 pages. The paper should contain a succinct statement of the
issues and of their motivation, a summary of the main results, and a
brief explanation of their significance, accessible to non-specialist
readers. Proofs omitted due to space constraints must be put into an
appendix to be read by the program committee members at their
discretion.
Publication:
Proceedings will be published in the Springer Lecture Notes in
Computer Science. Instructions for authors can be found at
http://www.springer.de/comp/lncs/authors.html.
Important Dates:
Submission deadline April 9, 2007
Notification to authors May 28, 2007
Final version due June 18, 2007
Symposium September 13-15, 2007
Invited Speakers:
- Harry Buhrman (Centrum voor Wiskunde en Informatica, Netherlands)
- Martin Dietzfelbinger (Technische Universitat Ilmenau, Germany)
- Rusins Freivalds (University of Latvia, Latvia)
- Pavlos Spirakis (University of Patras, Greece)
- Arvind Srinivasan (University of Maryland, USA)
Program Committee:
- Farid Ablayev, Kazan
- Dimitris Achlioptas, Santa Cruz
- Andreas Albrecht, Hatfield
- Andris Ambainis, Waterloo
- Markus Blaser, Saarbrucken
- Eli Ben-Sasson, Haifa
- Harry Buhrman, Amsterdam
- Colin Cooper, London
- Josep Diaz, Barcelona
- Martin Dietzfelbinger, Ilmenau
- Juraj Hromkovic, Zurich (co-chair)
- Oktay M. Kasim-Zade, Moscow
- Chandrasekaran Pandu Rangan, Chennai
- Vijaya Ramachandran, Austin
- Jose Rolim, Geneva
- Vishal Sanwalani, New Mexico
- Martin Sauerhoff, Dortmund
- Christian Scheideler, Munich
- Georg Schnitger, Frankfurt am Main
- Jiri Sgall, Prague
- Angelika Steger, Zurich
- Kathleen Steinhofel, London
- Berthold Vocking, Aachen
- Osamu Watanabe, Tokyo
- Peter Widmayer, Zurich (co-chair)
Organizing Committee Chairs:
- Marc Nunkesser
- Peter Widmayer