Scope

The 4th Symposium on Stochastic Algorithms, Foundations and Applications (SAGA'07) will be held September 13-14, 2007, in Zurich (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