From owner-theorynt@LISTSERV.NODAK.EDU Tue Jun 10 13:21:51 1997 Received: from CS.Stanford.EDU (CS.Stanford.EDU [171.64.64.64]) by robotics.Stanford.EDU (8.8.5/8.8.5) with ESMTP id NAA09457 for ; Tue, 10 Jun 1997 13:21:50 -0700 (PDT) Received: from listserv.nodak.edu (listserv.NoDak.edu [134.129.111.8]) by CS.Stanford.EDU (8.8.4/8.8.4) with ESMTP id NAA20643; Tue, 10 Jun 1997 13:11:16 -0700 (PDT) Received: from listserv (134.129.111.8) by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.E1C0D950@listserv.nodak.edu>; Tue, 10 Jun 1997 15:06:32 -0500 Received: from LISTSERV.NODAK.EDU by LISTSERV.NODAK.EDU (LISTSERV-TCP/IP release 1.8c) with spool id 703385 for THEORYNT@LISTSERV.NODAK.EDU; Tue, 10 Jun 1997 15:06:25 -0500 Received: from listserv (134.129.111.8) by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.DC5780E0@listserv.nodak.edu>; Tue, 10 Jun 1997 15:06:23 -0500 Received: from LISTSERV.NODAK.EDU by LISTSERV.NODAK.EDU (LISTSERV-TCP/IP release 1.8c) with spool id 703363 for THEORY-A@LISTSERV.NODAK.EDU; Tue, 10 Jun 1997 15:06:22 -0500 Received: from usc.edu by listserv.nodak.edu (LSMTP for Windows NT v1.1a) with SMTP id <0.DB4A2F90@listserv.nodak.edu>; Tue, 10 Jun 1997 15:06:21 -0500 Received: from pollux2.usc.edu (pollux2.usc.edu [128.125.253.192]) by usc.edu (8.8.4/8.7.2/usc) with ESMTP id NAA02383 for ; Tue, 10 Jun 1997 13:06:18 -0700 (PDT) Received: (from ierardi@localhost) by pollux2.usc.edu (8.8.4/8.8.4/usc) id NAA03706 for theory-a@listserv.nodak.edu; Tue, 10 Jun 1997 13:05:47 -0700 (PDT) Approved-By: Doug Ierardi Approved-By: Theory-A - TheoryNet World-Wide Events Message-ID: <199705302218.SAA18099@church.mcmaster.ca> Date: Tue, 10 Jun 1997 13:05:46 PDT Reply-To: Theory-A - TheoryNet World-Wide Events , Tao Jiang Sender: TheoryNet List From: Tao Jiang Subject: Cocoon97: preliminary program and registration Comments: To: THEORY-A@LISTSERV.NODAK.EDU To: THEORYNT@LISTSERV.NODAK.EDU X-Mozilla-Status: 0001 Content-Length: 18422 COCOON'97 Third Annual International Computing and Combinatorics Conference August 20-22, 1997, New Garden Hotel, Shanghai, China PRELIMINARY PROGRAM and ADVANCE REGISTRATION ######################## GENERAL INFORMATION ########################### COCOON'97 is the third in the series of Annual International Computing and Combinatorics Conference. It features 2 invited lectures and 53 contributed papers covering a wide scope of areas including algorithms, complexity, computability, logic, formal language, automata, rewriting, parallel and distrubuted computation, computational geometry, computational biology, computational finance, cryptography, mathematical programming, etc. The social program includes a reception, a dinner followed by an entertainment performance, a banquet, and various post-conference tours. This file contains the preliminary scientific program of the conference and registration forms for the conference, hotel and tours. For more complete information about the conference program, hotel, travel, local weather, tours, etc., please consult our homepage at http://www.dcss.mcmaster.ca/cocoon97 ##################### PRELIMINARY PROGRAM ############################ ****************************** * Tuesday, August 19, 1997 * ****************************** 7:00pm - 9:00pm: Reception and registration. ****************************** * Wednesday, August 20, 1997 * ****************************** Invited Lecture --------------- 8:30: t.b.a. --- Paul Vitanyi (Amsterdam, The Netherlands) Session 1: Parallel and Distributed Computating I ------------------------------------------------- 9:15 Conflict-Free Access to Templates of Trees and Hypercubes in Parallel Memory Systems --- Sajal K. Das, M. Cristina Pinotti 9:40 Many-to-One Packet Routing via Matchings --- Danny Krizanc, Louxin Zhang 10:05 A Multi-Tree Generating Routing Scheme --- Fred S. Annexstein, Ken Berman, Ram Swaminathan Coffee and Tea Break: 10:30 - 10:45 Session 2: Computational Geometry --------------------------------- 10:45 An algorithm for Heilbronn's problem --- Claudia Bertram-Kretzberg, Thomas Hofmeister, Hanno Lefmann 11:10 Optimal Multiresolution Polygonal Approximation --- K. W. Chan, Francis Y. L. Chin 11:35 Constructing A Strongly Convex Superhull of Points --- Wei Chen, Xiao Wen Deng, Koichi Wada, Kimio Kawaguchi 12:00 Fast Range Searching with Delaunay Triangulations --- Binhai Zhu Lunch Break: 12:25 - 1:30 Session 3: Complexity --------------------- 1:30 Resolution of Hartmanis' Conjecture for NL-hard Sparse Sets --- Jin-Yi Cai, D. Sivakumar 1:55 Can Large Fanin Circuits Perform Reliable Computations in the Presence of Noise? --- R\"udiger Reischuk 2:20 On Set Systems with Restricted Intersections Modulo a Composite --- Vince Grolmusz 2:45 Size and Variable Ordering of OBDDs Representing Threshold Functions --- Yasuhiko Takenaga, Mitsushi Nouzoe, Shuzo Yajima Coffee and Tea Break: 3:10 - 3:25 Session 4: Computational Biology I ---------------------------------- 3:25 The Performance of the Neighbor-Joining Method of Phylogeny Reconstruction --- Kevin Atteson 3:50 Inferring Evolutionary Trees with Strong Combinatorial Evidence --- Vincent Berry, Olivier Gascuel 4:15 Parsomony is Hard to Beat --- Kenneth Rice, Tandy Warnow 4:40 On the complexity of computing evolutionary trees --- Leszek Gasieniec, Jesper Jansson, Andrzej Lingas, Anna Ostlin Coffee and Tea Break: 5:05 - 5:20 Session 5: Computability ------------------------ 5:20 Computable Invariance --- Vasco Brattka 5:45 Subclasses of Computable Real Valued Functions --- Qing Zhou 6:10 Computability on Continuous, Lower Semi-Continuous and Upper Semi-Continuous Real Functions --- Klaus Weihrauch, Xizhong Zheng 7:00 - 10:00 Dinner and Entertainment Performance ****************************** * Thursday, August 21, 1997 * ****************************** Invited Lecture --------------- 8:30: t.b.a. --- Shanghua Teng (Minneapolis, USA) Session 6: Cryptography and Computational Finance ------------------------------------------------- 9:15 Contrast-Optimal k out of n Secret Sharing Schemes in Visual Cryptography --- Thomas Hofmeister, Matthias Krause, Hans U. Simon 9:40 A Rabin-Type Scheme Based on $y^2 \equiv x^3 + bx^2 \bmod{n}$ --- Seng Kiat Chua, San Ling 10:05 Optimal Bidding Algorithms Against Cheating in Multiple-Object Auctions --- Ming-Yang Kao, Junfeng Qi, Lei Tan Coffee and Tea Break: 10:30 - 10:45 Session 7: Graph Algorithms --------------------------- 10:45 Spring Algorithms and Symmetry --- Peter Eades, Xuemin Lin 11:10 Generalized Vertex-Rankings of Partial $k$-Trees --- Md. Abul Kashem, Xiao Zhou, Takao Nishizeki 11:35 A Selected Tour of the Theory of Identification Matrices --- Lin Chen 12:00 Efficient domination on permutation graphs and trapezoid graphs --- Y. Daniel Liang, C-L Lu, C-Y Tang Lunch Break: 12:25 - 1:30 Session 8: Computational Biology II ----------------------------------- 1:30 On Physical Mapping Algorithms - An error-tolerant test for the consecutive ones property --- Wen-Lian Hsu 1:55 Breakpoint Analysis in Comparative Genomics --- David Sankoff 2:20 Fast Algorithms for Aligning Sequences with Restricted Affine Gap Penalties --- Kun-Mao Chao 2:45 A Matrix Representation of Phylogenetic Trees --- Sanzheng Qiao, W.S-Y. Wang Coffee and Tea Break: 3:10 - 3:25 Session 9: Algorithms --------------------- 3:25 Edge and Node Searching Problems on Trees --- Sheng-Lung Peng, Chin-Wen Ho, Tsan-sheng Hsu, Ming-Tat Ko, Chuan-Yi Tang 3:50 Construction of Nearly Optimal Multiway Trees --- Peter Becker 4:15 Optimal Algorithm for Circle Partitioning --- Kuo-Hui Tsai, Da-Wei Wang 4:40 Hexagonal Routing of Multiterminal Nets --- Xuehou Tan, Xiaoyu Song Coffee and Tea Break: 5:05 - 5:20 Session 10: Rewriting and Logic ------------------------------- 5:20 Design and Analysis of Parallel Set-Term Unification --- Seung-Jin Lim, Yiu-Kai Ng 5:45 On Modularity of the Completeness in Order-Sorted Term Rewriting Systems --- Yoshinobu Kawabe, Naohiro Ishii 6:10 A Three-valued Quantificational Logic of Context --- Kaile Su, Decheng Ding, Huowang Chen 7:00 - 9:00 Banquet ****************************** * Friday, August 22, 1997 * ****************************** Session 11: Algoroithms and Applications ---------------------------------------- 8:30 A Compact Storage Scheme for Fast Wavelet-Based Subregion Retrieval --- A. Poulakidas, A. Srinivasan, O. Egecioglu, O. Ibarra, T. Yang 8:55 A Declustering Algorithm for Minimizing Spatial Join Cost --- Yanchun Zhang, Jitian Xiao, Xiaofang Zhou 9:20 Fixed topology Steiner trees and spanning forests with applications in network communications --- Lusheng Wang, Xiaohua Jia 9:45 A Branch-and-Bound Algorithm for Computing Node Weighted Steiner Minimum Trees --- Guoliang Xue Coffee and Tea Break: 10:10 - 10:30 Session 12: Automata, Languages and Complexity ---------------------------------------------- 10:30 A complete characterization of repetitive morphisms over the two-letter alphabet --- Yuji Kobayashi, Friedrich Otto, P. Seebold 10:55 An Algorithm for Indentifying Spliced Languages --- Sam M. Kim 11:20 The Shapes of Trees --- Ulrich Hertrampf 11:45 Tally Languages Accepted by alternating multitape finite automata --- Dainis Geidmanis, Janis Kaneps, Kalvis Apsitis, Daina Taimina, Elena Calude Lunch Break: 12:10 - 1:30 Session 13: Parallel and Distributed Computing II ------------------------------------------------- 1:30 Independent Spanning Trees of Chordal Rings --- Yukihiro Iwasaki, Yuka Kajiwara, Koji Obokata, Yoshihide Igarashi 1:55 Rearrangeable Graphs --- Qing Hu, Yixin Zhang, Xiaojun Shen 2:20 Projective Torus Networks --- T.Y. Sung, T.Y. Ho, L.H. Hsu Coffee and Tea Break: 2:45 - 3:00 Session 14: Mathematical Programming and Genetic Algorithms ----------------------------------------------------------- 3:00 On the 100% Rule of Sensitivity Analysis in Linear Programming --- Pu Cai, Jin-Yi Cai 3:25 Enumerating Triangulations for Products of Two Simplices and for Arbitrary Configurations of Points --- Fumihiko Takeuchi, Hiroshi Imai 3:50 Tree Structure Genetic Algorithms with a Nourishment Mechanism --- Zhangang Han and Ruqian Lu Coffee and Tea Break: 4:15 - 4:30 Session 15: Parallel and Distributed Computing III -------------------------------------------------- 4:30 An Approach to scalability of Parallel Matrix Multiplication --- Xingfu Wu, Wei Li 4:55 Limited Acceleration Mechanism for Cell Loss Free Flow Control in ATM Networks --- Hong Liu, Reza Sotudeh, Enmin Song 5:20 They Are Just Butterflies --- Yong-Hong Chen and Qiao Li ################### CONFERENCE REGISTRATION FORM ###################### First name ____________________________________________________ Last name ____________________________________________________ University/Company ____________________________________________ Title/Position ________________________________________________ Mailing Address _______________________________________________ _______________________________________________ _______________________________________________ _______________________________________________ How many companions? __________________________________________ Special dietary needs: ________________________________________ Registration fees: Before 6/15 After 6/15 Delegate US$350 ____ US$400 ____ Companion US$320 ____ US$370 ____ Extra Proceedings US$53 ____ US$63 ____ *** If your companion does not want to attend any activity of the conference, then you do not need to pay. Regular registration includes a copy of the Proceedings, the reception, three lunches, the banquet, an entertainment performance + dinner, refreshments during breaks, and a badge. Companion registration includes the reception, three lunches, the banquet, a performance show, a badget, and a three day tourist program during the conference. Please note that due to the difficulty of management, a badge is required to enter the conference room and the refreshment area during breaks. Refund Policy: Cancellation refunds cannot be made after July 15. The rate of refund will be 60% before July 15. Payment Calculation: Delegate US$____________________ Companion US$____________________ Total US$____________________ Methods of Payment and Return Address: For advance registration before June 15, please send this form, together with a money order or cheque drawn on a US or Canadian bank made out in US dollars and payable to COCOON, to Professor Tao Jiang Department of Computer Science McMaster University Hamilton, Ontario L8S 4K1 Canada Eurochecks, etc., are subject to collection charges of\$25 or more. For registration after June 15, please send this form, together with a cheque or money order made out in US dollars and payable to Mr. Cheng Lin, Institute of Applied Mathematics, to Mr. Cheng Lin COCOON'97 Secretary Institute of Applied Mathematics Chinese Academy of Sciences P.O.Box 2734 Beijing 100080, P.R. China Fax: 8610-6254-1689 E-mail: lcheng@amath2.amt.ac.cn The payment can also be made by bank transfer. If you choose payment through bank transfer, please send a copy of the remittance invoice or receipt with this form to Mr. Cheng Lin at the above address and please transfer your payment in US$ to the following account: Mr. Cheng Lin Account No. 4080000-2014-007069-6 Haidian Sub-Branch City Branch Beijing Bank of China Beijing 100080, China Passport and Visa: Upon receiving your Registration Form and fees before June 15 the conference secretariat will offer you an official invitation issued by the authority concerned. This invitation will facilitate the application for a Chinese entry visa. Please provide the following information in order to obtain the official invitation. Name __________________________________________ Nationality____________________________________ Date of birth _________________________________ Place of birth_________________________________ Institution ___________________________________ Title/Position ________________________________ Passport number _______________________________ If you have any companions, their Name __________________________________________ Passport number _______________________________ Name __________________________________________ Passport number _______________________________ Length of stay ________________________________ Where are you going to visit before and after the conference? Visit Type: 1. ___ Academic 2. ___ Post-conf. Tour If 1 is checked, please indicate the institutions that you plan to visit:_____________________________________________________ _____________________________________________________ Location of the Chinese Embassy (or Consulate-General) at which where you would like to apply for visa:_____________________________________ _____________________________________ _____________________________________ If a passport number is not yet available, please send this form first, then send the number before July 1. ###################### HOTEL RESERVATION FORM ###################### The conference has made a block room reservation at New Garden Hotel. Its address is 1900 Hongqiao Road Shanghai 200335, China Telephone: 86-21-62426688 FAX: 86-21-62423256 The discount price for a standard double room is US$52 per night. To reserve rooms, please provide the following information: Number of rooms___________________________ Number of nights__________________________ Arrival date______________________________ Departure date____________________________ No deposit is required for room reservation as long as the conference registration fee is paid. The conference holds a certain number of discount rooms, and the rooms will be provided in the order of conference registrations received. Thus, those who register too late may risk having to pay the regular price of $85 for a double room per night. ############# POST-CONFERENCE TOUR PROGRAMS AND RESERVATION ################ The following post-conference tours will be arranged by China Goodwill Travel Service. 1. One day tour - Suzhou Sightseeing, on Aug. 23 Departure: 8:30am (by air-conditioned bus) 10:00am arrive in Suzhou and visit Tiger Hill 11:30am Lunch 13:00pm visit Humble Administered Garden 14:30pm visit Hanshan Temple 15:30pm visit Suzhou Silk Factory 16:30pm return to Shanghai 18:00pm arrive in Shanghai Price: US$ 50 per person 2. Post-conference Tour Two itineraries will be arranged by the China Goodwill Travel Service Itinerary I: Shanghai-Hangzhou-Beijing (Aug. 24--Aug. 29; 6 days and 5 nights) Sightseeing: Hangzhou: West Lake, Linyin Temple, Temple of Yue Fei Beijing: the Forbiden City, Temple of Heven, Tian An Men Square, Beijing Opera (show), the Great Wall, Ming Tomb Price Table: Group Size Price (in US$) >10 Persons $567 6-9 Persons $647 2-5 Persons $747 (per person in Double Occupancy) Itinerary II: Shanghai--Xian--Guilin --Canton ( Aug.24--Aug. 29; 6 days and 5 nights) Sightseeing: Xian: the Big Wild Goose Pagoda, Qin Terra Cotta Worriers, Huaqing Hot Spring. Guilin: Li River, Reed Flute Cave, Elephant Hill, Pled Silk Hill Canton: Dr. Sun-Yet-Sen's Memorial Hall; Yue Xiu Park. Price Table: Group Size Price (in US$) >10 Persons $755 6-9 Persons $815 2-5 Persons $925 (per person in Double Occupancy) Notes: (1) To make a reservation, please fill in the following information, and return the form to: Mr. Cheng Lin COCOON'97 Secretary Institute of Applied Mathematics P.O.Box 2734 Beijing 100080 P.R.China Email: lcheng@amath2.amt.ac.cn Fax: 8610-62541689 Which tour? _____________________________ How many people in your group? ___________ How much deposit has been included? ______ (2) Please remit a deposit that is at least 50% of the price of the tour (in USD) to the COCOON'97 account in China at: Mr. Cheng Lin Account No. 4080000-2014-007069-6 Haidian Sub-Branch City Branch Beijing Bank of China (3) In order to avoid any confusion in money transfer, please send a copy of the remittance invoice or receipt to Mr. Cheng Lin at the above postal address. The fees can also be made by a cheque or money order in USD payable to Mr. Cheng Lin, Institute of Applied Mathematics, and sent to the above postal address. (4) If anyone has to cancel his/her reservation, please inform us by fax or in writing. The payment will be refunded according to the following table: Cancellation Received: Before {\bf July 15} 60% Refund After {\bf July 15} no refund