==== 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.