Current Trends in Algorithms, Complexity Theory, and Cryptography 2009

March 22~March 27

Room 1-315, FIT Building, Tsinghua University

PROGRAM

March 23 (Monday)

Session 1 (Session Chair: Prof. Andrej Bogdanov)               09:20-10:00

Title: Some Recent Results and Some Open Problems Concerning Solving Infinite Duration Games

Peter Bro Miltersen, University of Aarhus, Denmark

Session 2 (Session Chair: Dr. Christophe Tartary)               10:40-12:00

Title: Quasi-Cryptography

Andrej Bogdanov, Chinese University of Hong Kong

Title: Trends in Information Theoretically Secure Cryptography

Ivan Damgård, University of Aarhus, Denmark

Session 3 (Session Chair:Prof. Lars Arge)                        14:00-15:20

Title: Graph Colorings and Secure Computation over Non-Abelian Groups

Christophe Tartary, Tsinghua University, China

Title: Solving Linear Programs Using Multiparty Computation

Thomas Toft, University of Aarhus, Denmark

Session 4 (Session Chair: Dr. Jayalal Sarma M.N.)                15:50-17:10

Title: Rank Aggregation: Together We're Strong

Frans Schalekamp, Tsinghua University, China

Title: Privacy-Enhancing First-Price Auctions Using Rational Cryptography

Jesper Buus Nielsen, University of Aarhus, Denmark

March 25 (Wednesday)

Session 5 (Session Chair: Prof. Ivan Damgård)                   08:50-10:10

Title: Composition Theorems in Communication Complexity

Shengyu Zhang, The Chinese University of Hong Kong

Title: On the Quantum Query Complexity of Local Search

Xiaoming Sun, Tsinghua University, China

Session 6 (Session Chair: Dr. Anke van Zuylen)                  10:40-12:00

Title: Fundamentals of Range Searching

Peyman Afshani, University of Aarhus, Denmark

Title: Dynamic Normal Forms and Dynamic Characteristic Polynomial

Gudmund Skovbjerg Frandsen, University of Aarhus, Denmark

Session 7 (Session Chair: Dr. Frans Schalekamp)                14:00-15:20

Title: MASSIVE Data Algorithmics

Lars Arge, University of Aarhus, Denmark

Title: Cache-Oblivious Algorithms - A Unified Approach to Hierarchical Memory Algorithms

Gerth Stølting Brodal, University of Aarhus, Denmark

Session 8 (Session Chair: Prof. Jesper Buus Nielsen)             15:50-17:10

Title: The Proof of The Ranndom Energy Model(REM) Conjecture in The Number Partitioning Problem

Chandra Nair, The Chinese University of Hong Kong

Title: Computing Frobenius Numbers Using Test Sets

Bjarke Hammersholt Roune, University of Aarhus, Denmark

March26 (Thursday)

Session 9 (Session Chair: Prof. Gerth Stølting Brodal)           08:50-10:10

Title: On Class Separations Around Logspace

Anastasios Viglas, University of Sydney

Title: Derandomization of Space-Bounded Computational Classes

Elad Verbin, Tsinghua University, China

Session 10 (Session Chair: Dr. Elad Verbin)                      10:40-12:00

Title: Deterministic Sampling Algorithms for Network Design

Anke van Zuylen, Tsinghua University, China

Title: Network Interdiction

Daniel Andersson, University of Aarhus, Denmark

Session 11 (Session Chair: Prof. Peter Bro Miltersen)             14:00-15:20

Title: Complexity of Matroid Isomorphism Problem

Jayalal Sarma M.N., Tsinghua University, China

Title: Hilbert's Thirteenth Problem and Circuit Complexity

Kristoffer Arnsfelt Hansen, University of Aarhus, Denmark