Computing and Combinatorics

strongsupportandallprogramcommitteemembers,theirsupportsta?,and subrefereesfortheirexcellentworkwithindemandingtimeconstraints. Iwould alsoliketothankallauthorsforsubmittingtheirpaperstotheconference. I amgratefultoSteveTateforlettingmeusetheACMSIGACTelectronics- missionservice,MinghuiLiforhelpingmecreateconferencewebpages,and RichardCheekforprovidingsystemsupport. Finally,Iwouldliketoexpressmy gratitudetoDing-ZhuDu,XudongHu,andalllocalorganizersfortheirhard workinmakingthismeetingpossibleandenjoyable. August2001 JieWang ProgramCommitteeChairs: YuriGurevich,MicrosoftResearch,USA JieWang,UniversityofMassachusettsLowell,USA ProgramCommitteeMembers: EricAllender,RutgersUniversity,USA BernardChazelle,PrincetonUniversity,USA DannyZ. Chen,UniversityofNotreDame,USA JianerChen,TexasA&MUniversity,USA FrancisChin,UniversityofHongKong,China Kyung-YongChwa,KoreaAdvancedInstituteofScience&Technology,Korea RodDowney,VictoriaUniversityofWellington,NewZealand ErichGr¨adel,AachenUniversityofTechnology,Germany StevenHomer,BostonUniversity,USA ToshihideIbaraki,KyotoUniversity,Japan TaoJiang,UniversityofCaliforniaatRiverside,USA Ker-IKo,StateUniversityofNewYorkatStonyBrook,USA D. T. Lee,AcademyofScience,Taiwan XueminLin,UniversityofNewSouthWales,Australia MauriceNivat,UniversityofParis,France R. Ravi,CarnegieMellonUniversity,USA R¨udigerReischuk,UniversityofLub ¨eck,Germany SeinosukeToda,NihonUniversity,Japan LushengWang,CityUniversityofHongKong,China GuoliangXue,UniversityofVermont,USA MihalisYannakakis,BellLabs,USA Referees: DoritAharonov GuojunLi C. K. Poon KlausAmbos-Spies XueLi JohnShepherd DouglasBridges YanjunLi AmitabhSinha MarekChrobak YifanLi S. Skiena XiaotieDeng WeifaLiang MichaelTrick BjarniHalldorsson ShuangLuan KlausWagner PatrickHealy CatherineMcCartin C. A. Wang JohnHine AnilNerode WenpingWang YingpingHuang OjasParekh XiaodongWu XiaohuaJia Chong-DaePark BaogangXu Ming-YangKao Jung-HeumPark YuanshengYang JochenKonemann KunsooPark DongmoZhang TableofContents ComplexityTheory Complete Problems for Valiant's Class of qp-Computable Families of Polynomials. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Markus Bl¨ aser Log-Space Constructible Universal Traversal Sequences 4. 03 for Cycles of LengthO(n ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Michal Kouck´ y On Universally Polynomial Context-Free Languages. . . . . . . . . . . . . . . . . . . . 21 Nicholas Tran Separating Oblivious and Non-oblivious BPs. . . . . . . . . . . . . . . . . . . . . . . . . . 28 Kazuo Iwama, Yasuo Okabe, Toshiro Takase Program Schemes, Queues, the Recursive Spectrum and Zero-One Laws. . . 39 Iain A. Stewart Algebraic Properties for P-Selectivity. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 LaneA. Hemaspaandra,HaraldHempel,ArfstNickelsen Parallelizability of Some P-Complete Geometric Problems in the EREW-PRAM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 Carla Denise Castanho, Wei Chen, Koichi Wada, Akihiro Fujiwara ComputationalBiology Enhanced Sequence Reconstruction with DNA Microarray Application. . . . 64 Samuel A. Heath, Franco P. Preparata Non-approximability of Weighted Multiple Sequence Alignment. . . . . . . . . .