Program

Each talk is 25 minutes, including questions.

The tentative program can be downloaded. (word, pdf)

Monday, May 20

8:00 – 9:00

Registration is open outside the lecture room.

9:00 – 9:10

TAMC 2013 conference opening and welcome. (Prof. Francis Y.L. Chin)

 

9:10 – 10:25

Session 1

Chair:

Francis Chin

Online Scheduling on a CPU-GPU Cluster

Lin Chen, Deshi Ye and Guochuan Zhang

Throughput Maximization for Speed-Scaling with Agreeable Deadlines

Eric Angel, Evripidis Bampis, Vincent Chau and Dimitrios Letsios

Temperature Aware Online Algorithms for Minimizing Flow Time

Martin Birks and Stanley Fung 

10:25 – 10:45

Coffee Break

 

10:45 – 12:00

Session 2

Chair:

Siu Wing Cheng

Priority Queues and Sorting for Read-Only Data

Tetsuo Asano, Amr Elmasry and Jyrki Katajainen

(1+epsilon)-Distance Oracle for Vertex-Labeled Planar Graphs

Mingfei Li, Chu Chung Christopher Ma and Li Ning 

Group Nearest Neighbor Queries in the $L_1$ Plane

Hee-Kap Ahn, Sang Won Bae and Wanbin Son 

12:00 – 14:00

Lunch (Victoria Harbour Restaurant)

 

14:00 – 15:15

Session 3

Chair:

Angsheng Li

Modelling the Power Supply Network - Hardness and Approximation

Alexandru Popa 

Approximation Algorithms for a combined Facility Location Buy-at-Bulk Network Design

Andreas Bley, S. Mehdi Hashemi and Mohsen Rezapour 

k-means++ under Approximation Stability

Manu Agarwal, Ragesh Jaiswal and Arindam Pal 

15:15 – 15:35

Coffee Break

15:35 – 15:45

Group Photo

15:45 – 16:55

Chair:

Lap Chi Lau

Randomness and Pseudorandomness (Invited Talk) 
Avi Wigderson, Institute for Advanced Study 

 

17:00 – 18:15

Session 4

Chair:

Ke Yi

An Exact Algorithm for TSP in Degree-3 Graphs via Circuit Procedure and Amortization on Connectivity Structure 
Mingyu Xiao and Hiroshi Nagamochi 

Non-crossing Connectors in the Plane 
Jan Kratochvil and Torsten Ueckerdt 

Minimax Regret 1-Sink Location Problems in Dynamic Path Networks 
Yuya Higashikawa, Naoki Katoh, Siu-Wing Cheng, Guanqun Ni, Bing Su and Yinfeng Xu 

 

Tuesday, May 21

 

9:10 – 10:25 Session 5

Chair:

Barry Cooper

A Notion of a Computational Step for Partial Combinatory Algebras 
Nathanael L. Ackerman and Cameron E. Freer 

Selection by recursively enumerable sets 
Wolfgang Merkle, Frank Stephan, Jason Teutsch, Wei Wang and Yue Yang

On the Boundedness Property of Semilinear Sets 
Oscar Ibarra and Shinnosuke Seki 

10:25 – 10:45

Coffee Break

 

10:45 – 12:00 Session 6

Chair:

Hubert Chan

Turing machines can be efficiently simulated by the General Purpose Analog Computer 
Olivier Bournez, Daniel S. Graηa and Amaury Pouly 

Computing with and without arbitrary large numbers 
Michael Brand 

On the Sublinear Processor Gap for Parallel Architectures 
Alejandro Lopez-Ortiz and Alejandro Salinger 

12:00 – 14:00

Lunch (Traders Hotel)

 

14:00 – 15:15 Session 7

Chair:

Guochuan Zhang

On efficient constructions of short lists containing mostly Ramsey graphs 
Marius Zimand 

On Martin-Lof Convergence of Solomonoff's Mixture 
Tor Lattimore and Marcus Hutter 

Any monotone property of 3-uniform hypergraphs is weakly evasive 
Raghav Kulkarni, Youming Qiao and Xiaoming Sun 

15:15 – 15:35

Coffee Break

15:35 – 16:45

Chair:

Lap Chi Lau

Towards Provable Bounds for Machine Learning: Three Vignettes (Invited Talk) 
Sanjeev Arora, Princeton University 

16:45 – 18:00

Poster Session

18:30 pm

Banquet (Fulum Restaurant)

 

Wednesday, May 22

 

9:10 – 10:25 Session 8

Chair:

Xiaoming Sun

The Algorithm for the Two-sided Scaffold Filling Problem 
Nan Liu and Daming Zhu 

Energy-Efficient Threshold Circuits Detecting Global Pattern in 1-Dimensional Arrays 
Akira Suzuki, Kei Uchizawa and Xiao Zhou 

Resolving Rooted Triplet Inconsistency by Dissolving Multigraphs 
Andrew Chester, Riccardo Dondi and Anthony Wirth 

10:25 – 10:45

Coffee Break

 

10:45 – 12:00 Session 9

Chair:

Jianer Chen

Obnoxious Facility Game with a Bounded Service Range 
Yukun Cheng, Qiaomin Han, Wei Yu and Guochuan Zhang 

Efficient self-pairing on ordinary elliptic curves 
Hongfeng Wu and Rongquan Feng 

Grey-Box Public-Key Steganography 
Hirotoshi Takebe and Keisuke Tanaka 

12:00 – 14:00

Lunch (Delifrance)

 

 

14:00 – 15:40 Session 10

Chair:

Yijia Chen

Linear vertex kernels for several dense Ranking r-Constraint Satisfaction problems 
Anthony Perez 

On Parameterized and Kernelization Algorithms for the Hierarchical Clustering Problem 
Jianer Chen and Yixin Cao 

Vector Connectivity in Graphs 
Endre Boros, Pinar Heggernes, Pim Van 'T Hof and Martin Milanic 

Trees in Graphs With Conflit Edges or Forbidden Transitions 
Mamadou Moustapha Kante, Christian Laforest and Momege Benjamin 

18:00 – 19:00

 

William Mong Distinguished Lecture

 

Title:

The "P vs. NP" problem: efficient computation, Internet security, and the limits to human knowledge

 

Venue:

Theatre A, Chow Yei Ching Building, The University of Hong Kong

 

Speaker:

Professor Avi Wigderson

Institute for Advanced Study, Princeton