9:00am-8:00pm: Registration 7:00pm-10:00pm: Reception

8:20-8:45: Complete Problems for Valiant's Class of qp-Computable Families of PolynomialsMarkus Blaeser8:45-9:10: Log-space Constructible Universal Traversal Sequences for Cycles of Length $O(n^{4.03})$Michal Koucky9:10-9:35: On Universally Polynomial Context-Free LanguagesNicholas Tran

8:20-8:45: Enhanced Sequence Reconstruction with DNA Microarray ApplicationSamuel A. Heath, Franco P. Preparata8:45-9:10: Non-Approximability of Weighted Multiple Sequence AlignmentBodo Siebert9:10-9:35: A Greedy Algorithm for Optimal RecombinationShiquan Wu, Xun Gu

10:05-10:30: The Euclidean Bottleneck Steiner Tree and Steiner Tree with Minimum Number of Steiner PointsDing-Zhu Du, Lusheng Wang, Baogang Xu10:30-10:55: An FPTAS for Weight-Constrained Steiner Trees in Series-Parallel GraphsGuangting Chen, Guoliang Xue

10:05-10:30: Irene Finocchi Layered Drawings of Graphs with Crossing Constraints 10:30-10:55: Irene Finocchi, Rossella Petreschi On the Validity of Hierarchical Decompositions

11:00-12:00: The Digital Envelope--A Crash Course in Modern CryptographyAvi Wigderson, IAS, Princeton & Hebrew University, JerusalemAbstract:The talk is planned for a general audience, and no particular background is assumed. While Cryptography has existed for millenia, the basic theory which underlies all security on the internet and electronic commerce today has been developed within Theoretical Computer Science in a dazzling brief time span starting in the late 70's. In this talk I will try to describe the fundamental assumptions of this (complexity-based cryptography) theory, the exciting developement of ideas and notions (like one-way functions and zero-knowledge proofs), and how they enable basic tasks (like secure communication), as well as arbitrarily complex tasks (like playing a game of Poker over the telephone).

1:30-1:55: A Space Saving Trick for Directed Dynamic Transitive Closure and Shortest Path AlgorithmsValerie King, Mikkel Thorup1:55-2:20: Finding the Most Vital Node of a Shortest PathEnrico Nardelli, Guido Proietti, Peter Widmayer2:20-2:45: Algorithm for the Cost Edge-Coloring of TreesXiao Zhou, Takao Nishizeki2:45-3:10: Counting $H$-Colorings of Partial $k$-TreesJosep Diaz, Maria Serna, Dimitrios M. Thilikos

1:30-1:55: Improved On-line Stream Merging: from a Restricted to a General SettingWun-Tat Chan, Tak-Wah Lam, Hing-Fung Ting, Wai-Ha Wong1:55-2:20: On-line Deadline Scheduling on Multiple ResourcesJae-Hoon Kim, Kyung-Yong Chwa2:20-2:45: Competitive Online Scheduling with Level of ServiceEe-Chien Chang, Chee Yap2:45-3:10: On-line Variable Sized CoveringLeah Epstein

3:40-4:05: On the Planar Two-Watchtower ProblemSergei Bespamyatnikh, Zhixiang Chen, Kanliang Wang, Binhai Zhu4:05-4:30: Efficient Generation of Triconnected Plane TriangulationsShin-ichi Nakano4:30-4:55: Packing Two Disks into a Polygonal EnvironmentProsenjit Bose, Pat Morin, Antoine Vigneron4:55-5:20: How Good Is Sink Insertion?Xiang-Yang Li, Yu Wang

3:40-4:05: Cluttered Orderings for the Complete GraphMyra Cohen, Charles Colbourn, Dalibor Froncek4:05-4:30: On the Domination Numbers of Generalized de Bruijn Digraphs and Generalized Kautz DigraphsYosuke Kikuchi, Yukio Shibata4:30-4:55: A Notion of Cross-Perfect Bipartite GraphsMilind Dawande4:55-5:20: Some Results on Orthogonal FactorizationsHaodi Feng

8:20-8:45: Generating Well-Shaped d-Dimensional Delaunay MeshesXiang-Yang Li8:45-9:10: Towards Compatible TriangulationsOswin Aichholzer, Franz Aurenhammer, Hannes Krasser, Ferran Hurtado9:10-9:35: An Improved Upper Bound on the Size of Planar Convex-HullsAbdullah N. Arslan, Ömer Egecioglu

8:20-8:45: PC-Trees vs. PQ-TreesWen-Lian Hsu8:45-9:10: Stacks versus DequesHolger Petersen9:10-9:35: Optimizing a Computational Method for Length Lower Bounds for Reflecting SequencesH. K. Dai

10:05-10:30: A New Measure of Edit Distance Between Labeled TreesChin Lung Lu, Zheng-Yao Su, Chuan Yi Tang10:30-10:55: A Linear Time Algorithm for Enumerating All the Minimum and Minimal Separators of A Chordal GraphL. Sunil Chandran

10:05-10:30: Decidable Approximations on Generalized and Parameterized Discrete Timed AutomataZhe Dang, Oscar H. Ibarra, Richard A. Kemmerer10:30-10:55: Multiplicative Adaptive Algorithms for User Preference RetrievalZhixiang Chen

11:00-12:00 A Few Fundamental Open Questions in Computational GeometryBernard Chazelle, Princeton University, USA

1:30-1:55: Separating Oblivious and Non-Oblivious BPsKazuo Iwama, Yasuo Okabe, Toshiro Takase1:55-2:20: Program Schemes, Queues, the Recursive Spectrum and Zero-One LawsIain A. Stewart2:20-2:45: Algebraic Properties for P-SelectivityLane Hemaspaandra, Harald Hempel, Arfst Nickelsen2:45-3:10: Parallelizability of Some P-Complete Geometric Problems in the EREW-PRAMCarla Denise Castanho, Wei Chen, Koichi Wada, Akihiro Fujiwara

1:30-1:55: On Testing for Zero Polynomials by a Set of Points with Bounded PrecisionJin-Yi Cai, Eric Bach1:55-2:20: A Randomized Algorithm for Gossiping in Radio NetworksMarek Chrobak, Leszek Gasieniec, Wojciech Rytter2:20-2:45: Deterministic Application of Grover's Quantum Search AlgorithmKyoichi Okamoto, Osamu Watanabe2:45-3:10: Random Instance Generation for MAX 3SATMitsuo Motoki

3:40-4:05: Maximum Red/Blue Interval Matching with ApplicationsDanny Z. Chen, Xiaobo (Sharon) Hu, Xiaodong Wu4:05-4:30: Computing Farthest Neighbors on a Convex PolytopeOtfried Cheong, Chan-Su Shin, Antoine Vigneron4:30-4:55: Polynomial Time Algorithms for Three-Label Point LabelingRob Duncan, Jianbo Qian, Binhai Zhu4:55-5:20: Finding An Optimal Bridge Between Two PolygonsXuehou Tan

3:40-4:05: Lower Bounds on the Minus Domination and $k$-Subdomination NumbersLiying Kang, Hong Qiao, Erfang Shan, Ding-Zhu Du4:05-4:30: Edge Connectivity vs Vertex Connectivity in Chordal GraphsL. Sunil Chandran4:30-4:55: Changing the Diameter of Graph ProductsTing-Yi Sung, Jeng-Jung Wang4:55-5:20: Plane Graphs with Acyclic ComplexBaogang Xu

8:20-8:45: Competitive Facility Location along a HighwayHee-Kap Ahn, Siu-Wing Cheng, Otfried Cheong, Mordecai Golin, Rene van Oostrum8:45-9:10: Membership for Core of LP Games and Other GamesQizhi Fang, Shanfeng Zhu, Maocheng Cai, Xiaotie Deng9:10-9:35: Strong Solutions to the Identification ProblemPino Caballero-Gil, Candelaria Hernandez-Goya9:35-10:00: Area Efficient Exponentiation Using Modular Multiplier/Squarer in GF$(2^n)$Hyun-Sung Kim, Kee-Young Yoo

8:20-8:45: Graph Separators: A Parameterized ViewJochen Alber, Henning Fernau, Rolf Niedermeier8:45-9:10: On Assigning Prefix Free Codes to the Vertices of A GraphN.S. Narayanaswamy, C.E. Veni Madhavan9:10-9:35: A Highly Efficient Algorithm to Determine Bicritical GraphsDingjun Lou, Ning Zhong9:35-10:00: Approximation Algorithms for the Watchman Route and Zookeeper's ProblemsXuehou Tan

10:30-10:55: Prefix-Free Languages and Initial Segments of Computably Enumerable DegreesGuohua Wu10:55-11:20: Weakly Computable Real Numbers and Total Computable Real FunctionsRobert Rettinger, Xizhong Zheng, Romain Gengler, Burchard von Braunmuhl11:20-11:45: Turing Computability of a Nonlinear Schrödinger PropagatorKlaus Weihrauch, Ning Zhong

10:30-10:55: Parametric Scheduling for Network ConstraintsK. Subramani10:55-11:20: A Logical Framework for Knowledge Sharing in Multi-Agent Systems}Kaile Su, Xudong Luo, Huaiqing Wang, Shichao Zhang, Qingfeng Chen11:20-11:45: A Lockout Avoidance Algorithm without Using Time-Stamps for the $k$-Exclusion ProblemKumiko Obokata, Michiko Omori, Kazuhiro Motegi, Yoshihide Igarashi