Second Annual International Computing and Combinatorics Conference

Hong Kong, June 17-19, 1996
In cooperation with the Hong Kong Chapter of ACM and IEEE Computer Chapter, Hong Kong Section.
  • Description
  • Program
  • Hotel and Registration Information
  • Transportation in Hong Kong
  • First session
  • Banquet
  • Weather
  • More about Hong Kong

  • Description

    See also the Call for Papers.

    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:

    The proceedings of the conference will be published by Springer-Verlag in the Lecture Notes in Computer Science series, and will be available for distribution at the conference. Selected papers will be published in special issues of the journal Algorithmica.

    Program Committee:

    Jin-Yi Cai, Co-Chair, C.K. Wong, Co-Chair, Richard Chang, JianEr Chen, Frank Dehne, Herbert Edelsbrunner, Andrew Goldberg, Juris Hartmanis, Ming-Deh Huang, Oscar Ibarra, Ming Y. Kao, D.T. Lee, Tom Leighton, Takao Nishizeki, Alan L. Selman, Jan van Leeuwen, Christos Papadimitriou, Prabhakar Raghavan, Seinosuke Toda, Frances Yao, Andrew Yao, Chee-Keng Yap, Yanjun Zhang.

    Conference Co-Chairs:

    Francis Chin (University of Hong Kong, and Jun Gu (Hong Kong University of Science and Technology,


    Day 1 (17 June 1996)
    Keynote Address Chair: C. K. Wong
    9:00 am - 10:00 am

    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).

    Hotel and Registration Information

    For Hotel and Registration information please send email to

    Transportation in Hong Kong

    Taxis are readily available from Hong Kong International Airport. A trip from the airport to Hong Kong Island costs about HK$100, including a HK$20 charge for the Cross-Harbour Tunnel.

    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 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.

    First session

    Please be reminded that the keynote address by Professor C. L. Liu will start at 9am Monday (June 17). On that day, breakfast will be provided starting from 8am.

    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 and we will email you the PostScript file.


    The conference banquet will be in Chinese style, and extra banquet tickets can be purchased at US$50 each. Vegetarians please inform us early so that we can prepare vegetarian food for you.


    The temperature in June is normally in the range 25-32C, and humidity varies from 60% up to 99%. It may be handy to bring an umbrella with you.

    More about Hong Kong

    See Hong Kong in Pictures for a taste or check out the Hong Kong Tourist Association
    Last updated by Mordecai Golin, June 6, 1996