Mini-workshop on the Theory of Computing

August 9-11, 2010
Room 121, 1/F., Ho Sin Hang Engineering Building
The Chinese University of Hong Kong

About the workshop

The methods of the theory of computing are relevant in various areas in computer science: algorithm design, cryptography and security, quantum computation, and many others. Interactions between these diverse domains have always been vital for progress in the field.

The goal of this workshop is to bring together young researchers from Hong Kong, mainland China, and abroad who specialize various areas in the theory of computing. There will be talks about challenges and recent advances in the theory of computing as well as opportunities for informal discussions.

The workshop is open to the public.



Monday 9 August in room SHB 121
10.00 Akinori Kawachi
Pseudorandomness of the Legendre sequences and robust quantum state decoding
11.00 Periklis Papakonstantinou
On the limits of Decisional Diffie Hellman and trapdoor permutations
12.00 lunch
14.00 S. M. Yiu
High throughput short read alignment via Bi-directional BWT
15.00 Ke Yi
Optimal sampling from distributed streams

Tuesday 10 August in room SHB 121
10.00 Homin K. Lee
On the learnability of monotone functions
11.00 Kevin Matulef
Property testing of boolean functions, and connections to learning theory
12.00 lunch
14.00 Andrej Bogdanov
A better tester for bipartiteness?
15.00 Arnab Bhattacharyya
A Unified Framework for Testing Linear-Invariant Properties

Wednesday 11 August in room SHB 121
10.00 John Steinberger
A new proof of the 4-color theorem
11.00 Leo Cheung
Simple algebraic algorithms for linear matroid parity and applications
12.00 lunch
14.00 Alon Rosen
Sequential Rationality in Cryptographic Protocols

Douglas Pun To Yung


Using simple linear rules to explain complex cellular processes

Information for participants

Organizing Committee