(Message inbox:24) Return-Path: Received: from CS.CMU.EDU by MISSING.LINK.CS.CMU.EDU id aa07360; 1 May 96 4:35 EDT Received: from hearn.nic.surfnet.nl by CS.CMU.EDU id aa11008; 1 May 96 4:35:05 EDT Received: from HEARN.NIC.SURFNET.NL by HEARN.nic.SURFnet.nl (IBM VM SMTP V2R2) with BSMTP id 5100; Wed, 01 May 96 10:28:36 +0200 Received: from NIC.SURFNET.NL (NJE origin LISTSERV@HEARN) by HEARN.NIC.SURFNET.NL (LMail V1.2a/1.8a) with BSMTP id 6918; Wed, 1 May 1996 10:28:22 +0200 Received: from NIC.SURFNET.NL by NIC.SURFNET.NL (LISTSERV release 1.8b) with NJE id 3969 for DMA-LIST@NIC.SURFNET.NL; Wed, 1 May 1996 09:28:09 +0100 Received: from HEARN (NJE origin SMTP@HEARN) by HEARN.NIC.SURFNET.NL (LMail V1.2a/1.8a) with BSMTP id 6910; Wed, 1 May 1996 10:28:08 +0200 Received: from utmfu0.math.utwente.nl by HEARN.nic.SURFnet.nl (IBM VM SMTP V2R2) with TCP; Wed, 01 May 96 10:28:04 +0200 Received: by utmfu0.math.utwente.nl ($Revision: 1.36.108.11 $/16.2) id AA224149277; Wed, 1 May 1996 10:27:57 +0200 Full-Name: DMANET Mailer: Elm [revision: 66.36.1.1] Approved-By: DMANET Message-ID: <199605010827.AA224149277@utmfu0.math.utwente.nl> Date: Wed, 1 May 1996 10:27:53 METDST Reply-To: golin@cs.ust.hk Sender: DMANET From: DMANET Subject: COCOON96 program To: Multiple recipients of list DMA-LIST ******** EARLY REGISTRATION ENDS MAY 4, 1996 ************ 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. Conference Venue Chow Yei Ching Building University of Hong Kong Pokfulam Road, Hong Kong The first talk on the first day, the keynote address, will take place in Lecture Theatre A, located on the ground floor of the Chow Yei Ching Building, University of Hong Kong. All other talks will take place in Lecture Theatres B and C on Lower Ground 1 (LG1). 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 a 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, Carlos Cunha, Steven Homer 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 Straight Skeletons 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 Efficient Deterministic Algorithms for Embedding Graphs on Book 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 1:55 Hans L. Bodlaender, Babette de Fluiter Reduction Algorithms for Constructing Solutions in Graphs with Small Treewidth 2:20 Ryuhei Uehara, Zhi-Zhong Chen, 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 Satisfiability 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, Vincent Mirelli, 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 On 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 and NP-Completeness Result for Constraint Satisfaction Break: 3:10 pm -- 3:30 pm Session 11 Chair: M. Y. Kao 3:30 pm -- 5:35 pm 3:30 Sue Whitesides, Naixun Pei 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 There will also be on-site registration in the Chow Yei Ching Building, University of Hong Kong. On 17 June, 1996, registration will be in the ground floor lobby. On 18 and 19 June 1996, registration will be on Lower Ground 1. --------------------------------------------------------------------- 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 accommodations 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, 1996. 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." -- ****************************************************** Contributions to be spread via DMANET are submitted to DMANET@math.utwente.nl Replies to a message carried on DMANET should NOT be addressed to DMANET but to the original sender. The original sender, however, is invited to prepare an update of the replies received and to communicate it via DMANET. DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)