Hong Kong, June 17-19, 1996In cooperation with the Hong Kong Chapter of ACM and IEEE Computer Chapter, Hong Kong Section.
This conference is intended to provide a forum for researchers in theoretical computer science, combinatorics related to computing, and experimental analysis of algorithms. Typical, but not exclusive, topics of interest include:
Day 1 (17 June 1996)Keynote Address Chair: C. K. Wong
Algorithmic Aspects of Computer Aided Design of VLSI Circuits
Prof. C.L.Liu (University of Illinois, Urbana-Champaign)
Break: 10 am - 10:20 am
Session 1 Chair: C. K. Wong
10:20 am - 12:00 noon
10:20 Improved Bounds for On-line Load Balancing
Matthew Andrews, Michel X. Goemans, Lisa Zhang
10:45 O(n logn)-average-time algorithm for
shortest networks under a given topology
Guo-Liang Xue, Ding-Zhu Du
11:10 Steiner problems on directed acyclic graphs
Tsan-Sheng Hsu, D. T. Lee, Kuo-Hui Tsai, Da-Wei Wang
11:35 Wormhole versus deflection routing: A case study on the mesh
Efstratios Karaivazoglou, Paul Spirakis, Vassilis Triantafilou
Lunch: 12:00 noon - 1:30 pm
Session 2 Chair: J.-Y. Cai
1:30 pm - 3:10 pm
1:30 On Sparse Parity Check Matrices
Hanno Lefmann, Pavel Pudlak, Petr Savicky
1:55 Finding a Hidden Code by Asking Questions
Zhixiang Chen, Steven Homer, Carlos Cunha
2:20 Improved Length Lower Bounds for Reflecting Sequences
H. K. Dai, K. E. Flannery
2:45 Combinatorial and Geometric Approaches to Counting Problems on
Linear Matroids, Graphic Arrangements and Partial Orders
Hiroshi Imai, Satoru Iwata, Kyoko Sekine, Kensyu Yoshida
Break: 3:10 pm - 3:30 pm
Session 3: Chair: D. T. Lee
3:30 pm - 5:10 pm
3:30 Output-Sensitive Reporting of Disjoint Paths
Giuseppe Di Battista, Roberto Tamassia, Luca Vismara
3:55 Rectangular Grid Drawings of Plane Graphs
Md. Saidur Rahman, Shin-ichi Nakano, Takao Nishizeki
4:20 Area-Efficient Algorithms for Upward Straight-Line Tree Drawings
Chan-Su Shin, Sung Kwon Kim, Kyung-Yong Chwa
4:45 Straight Skeletons for General Polygonal Figures in the Plane
Oswin Aichholzer, Franz Aurenhammer
Reception: 5:30 pm - 6:30 pm
Day 2 (18 June 1996)
Session 4 Chair: S. Toda
8:45 am - 10:00 am
8:45 A note on uniform circuit lower bounds for the counting hierarchy
Eric Allender
9:10 A note on the simulation of exponential threshold weights
Thomas Hofmeister
9:35 Harmonic analysis, real approximation, and the communication complexity
of Boolean functions
Vince Grolmusz
Break: 10 am - 10:20 am
Session 5 Chair: T. Nishizeki
10:20 am - 12:00 noon
10:20 Finding Large Planar Subgraphs and Large Subgraphs of a Given Genus
Gruia Calinescu, Cristina G. Fernandes
10:45 Efficient Deterministic Algorithms for Embedding
Graphs on Books
Farhad Shahrokhi, Weiping Shi
11:10 Optimal Bi-Level Augmentation for selectivity enhancing graph connectivity
with applications
Tsan-sheng Hsu, Ming-Yang Kao
11:35 Exact Learning of Subclasses of CDNF formulas with Membership queries
Carlos Domingo
Lunch: 12:00 noon - 1:30 pm
Session 6 Chair: H. Edelsbrunner
1:30 pm - 3:10 pm
1:30 Fast Separator-Decomposition for Finite-Element Meshes
Shang-Hua Teng
1:55 Reduction Algorithms for Constructing Solutions in Graphs with
Small Treewidth
Hans L. Bodlaender, Babette de Fluiter
2:20 Fast RNC and NC algorithms for finding a maximal set of paths with
an application
Zhi-Zhong Chen, Ryuhei Uehara, Xin He
2:45 Sparse suffix trees
Juha Kärkkäinen, Esko Ukkonen
Break: 3:10 pm - 3:30 pm
Session 7 Chair: C. Yap
3:30 pm - 5:35 pm
3:30 Depth-efficient threshold circuits for multiplication and
symmetric function computation
Chi-Hsiang Yeh, Emmanouel A. Varvarigos
3:55 On the self-witnessing property of computational problems
V. Arvind
4:20 The Inverse Satisfiability Problem
Dimitris Kavvadias, Martha Sideri
4:45 The Join Can Lower Complexity
Lane A. Hemaspaandra, Zhigen Jiang, Joerg Rothe, Osamu Watanabe
5:10 On the distribution of eigenvalues of graphs
Xuerong Yong
Banquet: 7:00 pm - 10:00 pm
Day 3 (19 June 1996)
Session 8 Chair: A. Goldberg
8:45 am - 10:00 am
8:45 On the difficulty of designing good classifiers
Mic Grigni, Vincent Mirelli, Christos Papadimitriou
9:10 Approximating Latin Square Extensions
S. Ravi Kumar, Alexander Russell, Ravi Sundaram
9:35 Approximating minimum keys and optimal substructure screens
Tatsuya Akutsu, Feng Bao
Break: 10 am - 10:20 am
Session 9 Chair: C. Papadimitriou
10:20 am - 12:00 noon
10:20 Reductions and covergence rates of average time
Jay Belanger, Jie Wang
10:45 The Complexity of Computational Problems Associated with
Simple Stochastic Games
Akio Yanbe, Kouichi Sakurai
11:10 On the complexity of commutativity analysis
Oscar Ibarra, Pedro Diniz, Martin Rinard
11:35 Improved Non-approximability Results for Vertex Cover Problems with
Density Constraints
A.E.F. Clementi, L. Trevisan
Lunch: 12:00 noon - 1:30 pm
Session 10 Chair: O. Ibarra
1:30 pm - 3:10 pm
1:30 Some notes on the Nearest Neighbour Interchange distance measure
Ming Li, John Tromp, Louxin Zhang
1:55 Distributed computing in asynchronous networks with byzantine edges
Vasant Shanbhogue, Moti Yung
2:20 Weighted biased leftist trees and modified skip lists
S. Cho, S. Sahni
2:45 Probabilistic Analysis of Local Search and NP-Completeness
Result for Constraint Satisfaction
Hoong Chuin Lau
Break: 3:10 pm - 3:30 pm
Session 11 Chair: M. Y. Kao
3:30 pm - 5:35 pm
3:30 On the reconfiguration of chains
Naixun Pei, Sue Whitesides
3:55 Two-guarding a rectilinear polygon
Xuehou Tan, Binhai Zhu
4:20 Three Systems for Shared Generation of Authenticators
R. Safavi-Naini
4:45 Efficient Generation of Elliptic curve cryptosystems
Kwok-Yan Lam, San Ling, Lucas C-K Hui
5:10 Superconnectivity for Minimal Multi-Loop Networks
Jixiang Meng
Conference Venue
Chow Yei Ching Building
University of Hong Kong
Pokfulam Road, Hong Kong
The keynote address will take place in Lecture Theatre A, located on the ground floor of the Chow Yei Ching Building. All other talks will take place in Lecture Theatres B and C on Lower Ground 1 (LG1).
The air-conditioned Airbus service is another convenient and inexpensive way of travelling to and from Hong Kong International Airport. Coaches operate on a fixed 15-20-minute frequency daily from about 7am to midnight, and stop at, or near, major hotels on both sides of the harbour. It costs HK$17 for a trip to various locations in Hong Kong Island. To catch an Airbus, turn left after you get out of the airport lobby.
For your convenience, we provide a sketch map to indicate the locations and chinese characters for the conference hotels and venue, the University of Hong Kong. Note that many taxi drivers in Hong Kong do not understand English so, if you do not speak Cantonese, you might want to carry the map with you in order to show them.
If you have any trouble accessing the map please send email to cocoon96@cs.ust.hk and we will email you the PostScript file.
A free tourist information kit, which includes a tourist map, can be picked up at the airport in the luggage claim area.
The easiest way to the conference site (University of Hong Kong) is to take a taxi. It costs HK$30-50 and takes 15-30 minutes. See the map of the university, for directions to the Chow Yei Ching Building where the conference will be held.
If you have any trouble accessing the map please send email to cocoon96@cs.ust.hk and we will email you the PostScript file.