Stochastic Algorithms: Foundations and Applications
The 4th Symposium on Stochastic Algorithms, Foundations and Applications (SAGA 2007) took place on September 13–14, 2007, in Zur ¨ ich (Switzerland). It o?ered the opportunity to present original research on the design and an- ysis 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 the SAGA symposia series is on investigating the power of randomization in al- rithmics, and on the theory of stochastic processes especially within realistic scenarios and applications. Thus, the scope of the symposium ranges from the study of theoretical fundamentals of randomized computation to experimental algorithmics related to stochastic approaches. Previous SAGA symposia took place in Berlin (2001), Hat?eld (2003), and Moscow (2005). This year 31 submissions were received, and the program c- mittee selected 9 submissions for presentation. All papers were evaluated by at least four members of the program committee, partly with the assistance of subreferees. We thank the members of the program committee as well as all subreferees for their thorough and careful work. A special thanks goes to Harry Buhrman, Martin Dietzfelbinger, Rusi ¯ n? ¸s Freivalds, Paul G. Spirakis, and - avind Srinivasan, who accepted our invitation to give invited talks at SAGA 2007 and so to share their insights on new developments in researchareas of key interest.