==== Symposium on the Centenary of Alan Turing’s Birth ==== It will be the centenary of Alan Turing’s birth on 23 June 2012. On 20 June 2012, we will have an informal symposium to commemorate the illustrious founder of our field. The symposium will have 4 short talks (of 30 minutes each) on cryptanalysis, computational biology, logic, and complexity, which are some of the topics that Turing worked on. The talk title/abstracts can be found below. All are welcome. Registration is not required. But for catering purpose, please inform Ms Tan Poh Suan (tanps@comp.nus.edu.sg) by Sunday 17 June 2012 if you would like to join the post-symposium lunch. Venue: Executive Classroom, Level 4, COM2. Time: 10am - 12nn, 20 June 2012. Talk #1: Alan Turing and Cryptanalysis of Enigma Speaker: A/P Chang Ee Chien Abstract: During WWII, Alan Turing helped to break the Enigma machines, using technologies available at his time. In this talk, we will discuss Turing's pragmatic approach in cryptanalysis and his influences in modern cryptography. Talk #2: Genome Sequencing and Data Compression Speaker: A/P Sung Wing Kin Abstract: Due to the introduction of next generation sequencing, the number of DNA bases increases exponentially. Nowadays, storing and managing the DNA data becomes one of the major costs. In this talk, we will discuss some of the current development in DNA data compression. Talk #3: The Dichotomous Intensional Expressive Power of the Nested Relational Calculus with Powerset Speaker: Prof Wong Limsoon Abstract: Most existing studies on the expressive power of query languages have focused on what queries can be expressed and what queries cannot be expressed in a query language. They do not tell us much about whether a query can be implemented efficiently in a query language. Yet, paradoxically, efficiency is of primary concern in computer science. In this paper, the efficiency of queries in NRC(Powerset), a nested relational calculus with a powerset operation, is discussed. A dichotomy in the efficiency of these queries on a large general class of structures---which include long chains, deep trees, etc.---is discovered. In particular, it is shown that these queries are either already expressible in the usual nested relational calculus or require at least exponential space. This Dichotomy Theorem, when coupled with the Bounded Degree Property of the usual nested relational calculus proved earlier by Libkin and Wong, becomes a powerful general tool in studying the intensional expressive power of query languages. The Bounded Degree Property makes it easy to prove that a query is inexpressible in the usual nested relational calculus. Then, if the query is expressible in NRC(Powerset), subject to the conditions of the Dichotomy Theorem, the query must take at least exponential space. Talk #4: The Cost of Fault Tolerance in Multi-Party Communication Complexity Speaker: A/P Yu Haifeng Abstract: Multi-party communication complexity involves distributed computation of a function over inputs held by multiple distributed players. A key focus of distributed computing research, since the very beginning, has been to tolerate crash failures. It is thus natural to ask "If we want to compute a certain function in a fault-tolerant way, what will the communication complexity be?" Whether fault-tolerant communication complexity is interesting to study largely depends on how big a difference failures make. This talk will show an exponential gap between the non-fault-tolerant and fault-tolerant communication complexity of the SUM aggregation function. This result attests that fault-tolerant communication complexity needs to be studied separately, and thus gives rise to a novel topic rife with interesting open questions.