Tentative Programme (updated: 2008-04-23)

The AAAC2008 Annual Meeting will be held in Lecture Theatre A, B and C, Chow Yei Ching Building, The University of Hong Kong, Pokfulam, Hong Kong.

Saturday April 26, 2008

08:15-08:50	Registration
08:50-09:00	Opening
09:00-10:00	Session 1: Invited talk 1
10:00-10:30	Break
10:30-12:30	Session 2:
12:30-14:00	Lunch (Union Restaurant, Composite Buildng, HKU)
14:00-16:00	Session 3-A Geometry	Session 3-B Security	Session 3-C Combinatorics 1
16:00-16:30	Break
16:30-18:10	Session 4-A Complexity	Session 4-B Distributed Algorithms	Session 4-C Game & Online
19:00-21:00	Banquet (KamBoat Chinese Cuisine, Room 243, 2/F, The Westwood, 8 Belcher’s Street)

Sunday April 27, 2008

09:00-10:00	Session 5: Invited talk 2
10:00-10:30	Break
10:30-12:30	Session 6:
12:30-14:00	Lunch (Union Restaurant, Composite Buildng, HKU)
14:00-16:20	Session 7-A Random	Session 7-B Graph	Session 7-C Combinatorics 2

April 26 (Sat)

08:15-08:50 Registration

08:50-09:00 Opening

09:00-10:00 Session 1: Invited talk 1

Chair: Francis Chin
Dynamic Random Geometric Graphs
/Josep Diaz (Universitat Politecnica de Catalunya)

10:30-12:30 Session 2:

Constant-Working Space Algorithm for Image Processing
/Tetsuo Asano.
Delaunay Edge Flips in Dense Surface Triangulations
/Siu-Wing Cheng and Tamal Dey.
Translation Algorithms for Overlaying Convex Polyhedra
/Hee-Kap Ahn, Siu-Wing Cheng and Iris Reinbacher.
Enumeration of Non-crossing Geometric Graphs
/Naoki Katoh and Shin-ichi Tanigawa.

14:00-16:00 Session 3-A Geometry

Digital Star Shapes and Their Applications
/Jinhee Chun, Matias Korman, Martin Nollenburg and Takeshi Tokuyama.
Approximate Voronoi Diagrams in Doubling Spaces
/Sunil Arya, David M. Mount, Antoine Vigneron and Jian Xia.
Farthest City Voronoi Diagram
/Sang Won Bae and Kyung-Yong Chwa.
Geometric routing in ad hoc networks via random local neighbors
/Hiroaki Onuma, Kazushige Sato and Takeshi Tokuyama.
Optimal insertion of a segment highway in a city metric
/Matias Korman and Takeshi Tokuyama.
Optimal Disjoint Two-box Covering of Points
/Sang Won Bae and Hee-Kap Ahn.

14:00-16:00 Session 3-B Security

A speed-up technique for the lattice based attack for the RSA cryptosystem
/Yoshinori Aono.
Universally Composable Oblivious Polynomial Evaluation
/Chunhua Su, Tadashi ARARAGI and Kouichi SAKURAI.
Analysis on Algorithms Used for Privacy-Preserving K-means Clustering Schemes
/Chunhua Su, Jianying Zhou, Bao Feng, Tsuyoshi Takagi and Kouichi SAKURAI.
A Compact Signature Scheme with Ideal Lattice (Extended Abstract)
/Keita Xagawa and Keisuke Tanaka.
An Almost Optimal Quantum String Sealing Protocol and Its Security Analysis
/Masaki Nakanishi, SEIICHIRO TANI and Shigeru Yamashita.
Encryption with Partial Information Deletion
/Takato Hirano, Koichiro Wada and Keisuke Tanaka.

14:00-16:00 Session 3-C Combinatorics 1

An Efficient Algorithm for L(2,1)-labeling of Trees
/Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono and Yushi Uno.
There are arbitrary large minimal 2-pinning configurations
/Xavier Goaoc, Hyo-Sil Kim and Jung-Gun Lim.
A Primal-Dual 6.55-Approximation Algorithm for the Connected Facility Location Problem
/Hyunwoo Jung, Mohammad Khairul Hasan and Kyung-Yong Chwa.
NP-Hardness of the Sorting Buffer Problem on the Unifrom Metric
/Yuichi Asahiro, Kenichi Kawahara and Eiji Miyano.
Restrained and Total Restrained Domination Problems
/Chih-Shan Liu, Sheng-Lung Peng and Chuan Yi Tang.
l-Motif Pair Finding Problem
/Francis Chin, SM Yiu, Henry C.M. Leung and M.H. Siu.

16:30-18:10 Session 4-A Complexity

Density Condensation of Boolean Formulas Based on Covering Codes
/Takashi HORIYAMA and Atsushi SATO.
Reversal versus Access: Complexity Classes and Random Combinatorial Structures
/Kenya Ueno.
Inapproximability of Stable Roommates Problem with Triple Rooms
/Kazuo Iwama, Shuichi Miyazaki and Kazuya Okamoto.
On noise-reduction effect of filters for Boolean functions
/Masashi Karasaki and Eiji Takimoto.
Estimating correlation between modulo function and polynomial by Gowers uniformity
/Hidetoki Tanaka and Akinori Kawachi.

16:30-18:10 Session 4-B Distributed Algorithms

Searching a Circular Corridor by Two Boundary 1-Searchers
/Tsunehiko Kameda, John Z. Zhang and Masafumi Yamashita.
Strong Stabilization: Bounding Times Affected by Byzantine Processes in Stabilization
/Toshimitsu Masuzawa and Sebastien Tixeuil.
Asynchronous Byzantine Request-set Agreement Algorithm for Replication
/Junya Nakamura, Tadashi ARARAGI and Shigeru Masuyama.
Convergence of Mobile Robots with Uniformly-Inaccurate Sensors
/Kenta Yamamoto, Taisuke Izumi, Yoshiaki Katayama, Nobuhiro Inuzuka and Koichi Wada.
On A Self-Stabilizing Algorithm for Minimal Clique Partition Problem
/Hiroshi NISHIMURA, Taisuke Izumi, Yoshiaki Katayama and Koichi Wada.

16:30-18:10 Session 4-C Game & Online

Submodularity of Minimum-Cost Spanning Tree Games
/Masayuki Kobayashi and Yoshio Okamoto.
On a Strategic Issue in Gale-Shapley Algorithm
/Hirotatsu Kobayashi and Tomomi Matsui.
Selfish Wavelength Assignment in Multifiber Optical Networks
/Evangelos Bampas, Aris Pagourtzis, George Pierrakos and Katerina Potika.
On-Line Scheduling of Parallel Jobs with Virtualization
/Deshi Ye and Guochuan Zhang.
An Optimal Online Algorithm for the Graph Exploration Problem on Cycles
/Naoyuki Morimoto, Shuichi Miyazaki and Yasuo Okabe.

April 27 (Sun)

09:00-10:00 Session 5: Invited talk 2

Chair: Osamu Watanabe
Computational Awareness
/Lance Fortnow (Northwestern University)

10:30-12:30 Session 6:

A Faster 2-Approximation Algorithm for the Minimum Manhattan Network Problem
/Zeyu Guo, He Sun and Hong Zhu.
Dynamic Rank/Select Functions for Texts over a Large Alphabet
/Sunho Lee and Kunsoo Park.
Energy Complexity of Threshold Circuits
/Kei Uchizawa and Eiji Takimoto.
A new circular-ones test based on matrix decomposition
/Ei-Wen Yang and WenLian Hsu.

14:00-16:20 Session 7-A Random

Belief Propagation and Spectral Methods
/Masaki Yamamoto and Osamu Watanabe.
Random Deployment of Wireless Networks: Power of Second Chance
/Yajun Wang, Wangsen Feng, Mo Li, Xiang-Yang Li and Yunhao Liu.
Optimal Tracking of Distributed Heavy Hitters and Quantiles
/Ke Yi and Qin Zhang.
Scale Free Interval Graphs
/Takeya Shigezumi, Naoto Miyoshi, Ryuhei Uehara and Osamu Watanabe.
On the Distribution of the Longest Path Length in a Directed Acyclic Graph with Exponentially Distributed Edge Weights
/Ei Ando, Hirotaka Ono, Kunihiko Sadakane and Masafumi Yamashita.
On necessary Conditions of Linear Cover Time Random Walks
/Yoshiaki Nonaka, Hirotaka Ono, Kunihiko Sadakane and Masafumi Yamashita.
An O(n log n) -Cover Time Random Walk on a Biconnected Graph
/Yusuke Hosaka, Yoshiaki Nonaka, Hirotaka Ono, Kunihiko Sadakane and Masafumi Yamashita.

14:00-16:20 Session 7-B Graph

The Induced Disjoint Paths Problem
/Ken-ichi Kawarabayashi and Yusuke KOBAYASHI.
On Packing and Covering with In-trees in Directe Graphs
/Naoyuki Kamiyama, Naoki Katoh and Atsushi Takizawa.
On k-Connectivity Testing in Degree-Bounded Graphs
/Yuichi Yoshida and Hiro Ito.
On Orthogonal Ray Graphs
/Yohei Kobayashi, Anish Shrestha, Satoshi Tayu and Shuichi Ueno.
Minimum Vertex Ranking Spanning Tree Problem on Some Classes of Graphs
/Ruei-Yuan Chang, Guanling Lee and Sheng-Lung Peng.
Linear Algorithms for edge-disjoint k-partition with One-base on Planar Graphs
/Shingo Omura, Koichi Wada and Wei Chen.

14:00-16:20 Session 7-C Combinatorics 2

Approximation On Max/Min Mean Path
/Hong Zhu, DaKan Wang and Jie Zhou.
Inverting Linkages with Stretch
/Youichi Fujimoto, Mitsuo Motoki and Ryuhei Uehara.
Meta-knowledge to explore hypotheses in inductive learning algorithms
/Nobuhiro Inuzuka, Hiroyuki Ishida and Tomofumi Nakano.
A Weighted K_{t,t}-Free t-Factor Algorithm for Bipartite Graphs
/Kenjiro Takazawa.
Shannon Coding for the Discrete Noiseless Channel and Related Problems
/Man Du, Mordecai J. Golin and Qin Zhang.
The Complexity of the Hajos Calculus for Planar Graphs
/Kazuo Iwama and Suguru Tamaki.