Posted to comp.theory March 18, 1996:
Advance Program
The Second International Computing and Combinatorics Conference
COCOON '96
Hong Kong, June 17--19 1996
In cooperation with the
Hong Kong Chapter of the ACM and the IEEE
Computer Chapter, Hong Kong Section.
Keynote Address
Chair: C. K. Wong 9:00 am -- 10:00 am
Algorithmic Aspects of Computer Aided Design of VLSI Circuits
Professor C. L. Liu
University of Illinois at Urbana-Champaign
Break: 10 am -- 10:20 am
Session 1 Chair: C. K. Wong 10:20 am -- 12:00 noon
10:20
Matthew Andrews, Michel X. Goemans, Lisa Zhang
Improved Bounds for On-line Load Balancing
10:45
Guo-Liang Xue, Ding-Zhu Du
An O(n log n)-average-time algorithm for
shortest networks under given topology
11:10
Tsan-Sheng Hsu, D. T. Lee, Kuo-Hui Tsai, Da-Wei Wang
Steiner problems on directed acyclic graphs
11:35
Efstratios Karaivazoglou, Paul Spirakis, Vassilis Triantafilou
Wormhole versus deflection routing: A case study on the mesh
Lunch: 12:00 noon -- 1:30 pm
Session 2 Chair: J.-Y. Cai 1:30 pm -- 3:10 pm
1:30
Hanno Lefmann, Pavel Pudlak, Petr Savicky
On Sparse Parity Check Matrices
1:55
Zhixiang Chen, Steven Homer, Carlos Cunha
Finding a Hidden Code by Asking Questions
2:20
H. K. Dai, K. E. Flannery
Improved Length Lower Bounds for Reflecting Sequences
2:45
Hiroshi Imai, Satoru Iwata, Kyoko Sekine, Kensyu Yoshida
Combinatorial and Geometric Approaches to Counting Problems on
Linear Matroids, Graphic Arrangements and Partial Orders
Break: 3:10 pm -- 3:30 pm
Session 3: Chair: D. T. Lee 3:30 pm -- 5:10 pm
3:30
Giuseppe Di Battista, Roberto Tamassia, Luca Vismara
Output-Sensitive Reporting of Disjoint Paths
3:55
Md. Saidur Rahman, Shin-ichi Nakano, Takao Nishizeki
Rectangular Grid Drawings of Plane Graphs
4:20
Chan-Su Shin, Sung Kwon Kim, Kyung-Yong Chwa
Area-Efficient Algorithms for Upward Straight-Line Tree Drawings
4:45
Oswin Aichholzer, Franz Aurenhammer
A Straight Skeleton for General Polygonal Figures in the Plane
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
Eric Allender
A note on uniform circuit lower bounds for the counting hierarchy
9:10
Thomas Hofmeister
A note on the simulation of exponential threshold weights
9:35
Vince Grolmusz
Harmonic analysis, real approximation, and the communication complexity
of Boolean functions
Break: 10 am -- 10:20 am
Session 5 Chair: T. Nishizeki 10:20 am -- 12:00 noon
10:20
Gruia Calinescu, Cristina G. Fernandes
Finding Large Planar Subgraphs and Large Subgraphs of a Given Genus
10:45
Farhad Shahrokhi, Weiping Shi
A Deterministic Algorithm for Embedding Bipartite Graphs on
O(sqrt(|E|)) Pages
11:10
Tsan-sheng Hsu, Ming-Yang Kao
Optimal Bi-Level Augmentation for selectivity enhancing graph connectivity
with applications
11:35
Carlos Domingo
Exact Learning of Subclasses of CDNF formulas with Membership queries
Lunch: 12:00 noon -- 1:30 pm
Session 6 Chair: H. Edelsbrunner 1:30 pm -- 3:10 pm
1:30
Shang-Hua Teng
Fast Separator-Decomposition for Finite-Element Meshes and Sparse
Symbolic-Factroization
1:55
Hans L. Bodlaender, Babette de Fluiter
Reduction Algorithms for Constructing Solutions in Graphs with
Small Treewidth
2:20
Zhi-Zhong Chen, Ryuhei Uehara, Xin He
Fast RNC and NC algorithms for finding a maximal set of paths with
an application
2:45
Juha Karkkainen, Esko Ukkonen
Sparse suffix trees
Break: 3:10 pm -- 3:30 pm
Session 7 Chair: C. Yap 3:30 pm -- 5:35 pm
3:30
Chi-Hsiang Yeh, Emmanouel A. Varvarigos
Depth-efficient threshold circuits for multiplication and
symmetric function computation
3:55
V. Arvind
On the self-witnessing property of computational problems
4:20
Dimitris Kavvadias, Martha Sideri
The Inverse Satifiability Problem
4:45
Lane A. Hemaspaandra, Zhigen Jiang, Joerg Rothe, Osamu Watanabe
The Join Can Lower Complexity
5:10
Xuerong Yong
On the distribution of eigenvalues of graphs
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
Mic Grigni, Christos Papadimitriou
On the difficulty of designing good classifiers
9:10
S. Ravi Kumar, Alexander Russell, Ravi Sundaram
Approximating Latin Square Extensions
9:35
Tatsuya Akutsu, Feng Bao
Approximating minimum keys and optimal substructure screens
Break: 10 am -- 10:20 am
Session 9 Chair: C. Papadimitriou 10:20 am -- 12:00 noon
10:20
Jay Belanger, Jie Wang
Reductions and covergence rates of average time
10:45
Akio Yanbe, Kouichi Sakurai
The Complexity of Computational Problems Associated with
Simple Stochastic Games
11:10
Oscar Ibarra, Pedro Diniz, Martin Rinard
On the complexity of commutativity analysis
11:35
A.E.F. Clementi, L. Trevisan
Improved Non-approximability Results for Vertex Cover Problems with
Density Constraints
Lunch: 12:00 noon -- 1:30 pm
Session 10 Chair: O. Ibarra 1:30 pm -- 3:10 pm
1:30
Ming Li, John Tromp, Louxin Zhang
Some notes on the Nearest Neighbour Interchange distance measure
1:55
Vasant Shanbhogue, Moti Yung
Distributed computing in asynchronous networks with byzantine edges
2:20
S. Cho, S. Sahni
Weighted biased leftist trees and modified skip lists
2:45
Hoong Chuin Lau
Probabilistic Analysis of Local Search on Random Instances of
Constraint Satisfaction
Break: 3:10 pm -- 3:30 pm
Session 11 Chair: M. Y. Kao 3:30 pm -- 5:35 pm
3:30
Naixun Pei, Sue Whitesides
On the reconfiguration of chains
3:55
Xuehou Tan, Binhai Zhu
Two-guarding a rectilinear polygon
4:20
R. Safavi-Naini
Three Systems for Shared Generation of Authenticators
4:45
Kwok-Yan Lam, San Ling, Lucas C-K Hui
Efficient Generation of Elliptic curve cryptosystems
5:10
Jixiang Meng
Superconnectivity for Minimal Multi-Loop Networks
---------------------------------------------------------------------
REGISTRATION FOR COCOON'96
The registration fees for COCOON'96 are listed below.
To qualify for the early registration fees, your registration
application must be received by May 4, 1996. The non-student
registration fee includes the reception, the banquet, coffee breaks
and lunches, and a copy of the proceedings. The student fee does
not include the reception, banquet or lunches.
Please fill out the form below and send it, along with a
money order or bank draft (in US or HK) made payable to
COCOON'96, to:
Dr. H.F. Ting
Department of Computer Science
The University of Hong Kong
Pokfulam Road, Hong Kong
Last Name:_______________________First Name:________________________
Affiliation:________________________________________________________
Address:____________________________________________________________
E-mail:_____________________________________________________________
Phone:___________________________Fax:_______________________________
Please circle one category below.
Category Fee Before May 4 After May 4
Regular $350US/$2730HK $420US/$3275HK
Student $250US/1950HK $300US/2340HK
---------------------------------------------------------------------
Hotel Reservations for COCOON'96
The conference will be held from June 17 to June 19, 1996
at the University of Hong Kong on Hong Kong Island.
While accomodations are not available on campus the hotels
listed below provide special conference rates.
For those of you not familiar with Hong Kong note that taxis
are very cheap and easy to catch at hotels. A taxi from
the Furama hotel to the conference site would cost approximately 3US
and take 15-20 minutes; from the Wharney or South Pacific, 4US and
20-25 minutes.
Tsimshatsui, the location of the New World Hotel is in the tourist
district across Victoria Harbour from Hong Kong Island. It therefore
requires much more travelling time to get from there to the conference;
first a 10 minute walk to the Star Ferry, then a ferry crossing
of the harbour and, finally, a taxi to the university. The ferry +
taxi should cost approximately 3US and take 30-35 minutes total.
To make your reservations,
fill out the form below and
send it, along with a deposit
for at least one night's stay, to:
Morning Star Travel Service Limited
(fax (+852) 2723 8033)
B19-23 Tsimshatsui Centre
66 Mody Road
Tsimshatsui East
Kowloon, Hong Kong
Reservations should be received by May 1, 1993.
Deposit should be made
in the form of a bank draft or money order (in US, or HK)
payable to the Morning Star Travel Service Limited.
Credit cards are not accepted.
Last Name:_________________________ First Name:______________________
Affiliation:_________________________________________________________
Address:_____________________________________________________________
Nationality/Citizenship:_______________________Passport:_____________
Phone:______________________________ Fax:____________________________
Arrival flight #:_____________________________________________________
Hotel rates shown below include
service charge and tax.
Single and double rooms have the same rates.
Please circle one of the following hotels:
Furama Hotel
1 Connaught Road, Central, Hong Kong
HK 1,420 (US 185) per night
Wharney Hotel
57-73 Lockhart Road, Wan Chai, Hong Kong
HK 1,010 (US 131) per night
South Pacific Hotel
23 Morrision Hill Road, Wan Chai, Hong Kong
HK 870 (US 113) per night
New World Hotel
22 Salisbury Road, New World Centre, Tsimshatsui, KOWLOON
HK 1,120 (US 146) per night
Please circle one of the following categories:
Single
Double: sharing room with___________________________________________
~Date: from _______ to _______ (No. of nights: )
If falling outside the conference date, reservation
will be accepted subject to space availability.
I enclose a check/money order of
US/HK (delete applicable entry)$_______________
payable to the Morning Star Travel Service Limited as deposit,
and understand that the balance will be settled after arrival with
the Morning Star Travel Service Limited at the conference site (instead of
the hotel) using cash, credit card, or traveler's check."