Algorithmics, Social choice, Market Design, and Other Topics

The Knuth Prize 2008 has been announced. It goes to Volker Strassen . The citation is as following: The ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) will present its 2008 Knuth Prize to Volker Strassen of the University of Konstanz in Germany, for his contributions to the theory and practice of algorithm design. Strassen’s innovations enabled fast and efficient computer algorithms, the sequence of instructions that tells a computer how to solve a particular problem. His discoveries resulted in some of the most important algorithms used today on millions if not billions of computers around the world, and fundamentally altered the field of cryptography, which uses secret codes to protect data from theft or alteration.

Bill Howard has an interesting piece on social networks in the latest issue Communication of the ACM. Howard writes that Social network analysis explains why some sites succeed and others fail, how physical and online social networks differ and are alike, and attempts to predict how they will evolve. Howard notes that analysis of social networks predates online social networks. This is an interesting topic where computer science and sociology find some intersection. Enjoy!

The website for the Center for Computational Intractability is up . There is a nicely written overview of the importance of computational complexity in the summary of the project: The term Computational Intractability refers to the phenomenon that many problems seem inherently impossible to solve on current computational models. This phenomenon permeates science, mathematics, and engineering, and it limits our ability to understand nature or to design systems ... It seeks to bridge fundamental gaps in our understanding about the power and limits of efficient algorithms, which has the potential to revolutionize our understanding of algorithmic processes in a host of disciplines, and cast new light on fields such as quantum computing, secure cryptography, and pseudorandomness.

Kenneth Arrow has written a comment piece on the recent credit crunch. He points out the " growing difficulty of understanding the underlying risks imposed by growing complexity ".

Peter Key has a post on Ryan O Donnell winning the Okawa Award. Ryan O Donnel is doing exciting research in fourier analysis, boolean functions and computational learning. Lee writes: Ryan has made several seminal contributions, particularly in the area of hardness of approximation. He showed in a recent series of papers that the current best 0.878… approximation factor known for the classic Max-Cut problem is in fact the best factor achievable by any polynomial-time algorithm, under a well-known conjecture in complexity theory. Ryan’s publications are many and have been making a big impact, and this year he was invited to give a special tutorial at the STOC conference — quite an honor and the only theory tutorial on the program this year.

DIMAP Warwick Algorithms Day will take place at DIMAP, University of Warwick, on October 24, 2008. The goal is to bring together the UK community of researchers and graduate students interested in the study of Algorithms, Data Structures, and Complexity. The event will provide exciting invited lectures presenting recent advances in the field and also will provide lots of opportunity for discussions. (Quoted from here ) The program is available here .

Complexity Science focuses on systems of many interdependent components, showing Emergent behaviour at the system level, Self-organisation and/or Evolution. (Quoted from here ) There is a useful reading list for Complexity Science at the Warwick Complexity Complex website .