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.