ISAAC 2003 Final Program

December 14 (Sun.)

18:00--21:00

Reception
(2F Atago)

December 15 (Mon.)

09:00--10:00	Invited Talk 1 (2F Atago)
	``Interactive Proofs for Quantum Computation'' Andrew Chi-Chih Yao (Princeton University, USA)
10:00--10:30	Break
10:30--12:10	Session 1A (2F Atago)	Session 1B (1F La Cigogne)
	Computational Geometry I	Graph and Combinatorial Algorithms I
12:10--13:30	Lunch (2F Kikyo)
13:30--15:10	Session 2A (2F Atago)	Session 2B (1F La Cigogne)
	Computational Complexity I	Graph and Combinatorial Algorithms II
15:10--15:40	Break
15:40--17:20	Session 3A (2F Atago)	Session 3B (1F La Cigogne)
	Quantum Computation	Graph and Combinatorial Algorithms III

December 16 (Tue.)

09:00--10:15	Session 4A (2F Atago)	Session 4B (1F La Cigogne)
	Computational Geometry II	Combinatorial Optimization I
10:15--10:45	Break
10:45--12:00	Session 5A (2F Atago)	Session 5B (1F La Cigogne)
	Scheduling	Computational Biology
12:00--13:30	Lunch (2F Kikyo)
13:30--15:10	Session 6A (2F Atago)	Session 6B (1F La Cigogne)
	Computational Geometry III	Graph and Combinatorial Algorithms IV
15:10--15:40	Break
15:40--16:55	Session 7A (2F Atago)	Session 7B (1F La Cigogne)
	Distributed and Parallel Algorithms	Graph and Combinatorial Algorithms V
16:55--18:00	Break
18:00--	Banquet (2F Kibune)

December 17 (Wed.)

09:00--10:00	Invited Talk 2 (2F Atago)
	``Drawing Plane Graphs'' Takao Nishizeki (Tohoku University, Japan)
10:00--10:30	Break
10:30--12:10	Session 8A (2F Atago)	Session 8B (1F La Cigogne)
	Data Structure	Graph and Combinatorial Algorithms VI
12:10--13:30	Lunch (2F Kikyo)
13:30--15:10	Session 9A (2F Atago)	Session 9B (1F La Cigogne)
	Combinatorial and Network Optimization	Computational Complexity and Cryptography
15:10--15:40	Break
15:40--17:20	Session 10A (2F Atago)	Session 10B (1F La Cigogne)
	Game Theory and Randomized Algorithm	Algebraic and Arithmetic Computation

Invited Talk 1

Interactive Proofs for Quantum Computation: Andrew Chi-Chih Yao (Princeton University)

Session 1A: Computational Geometry I

Linear Time Algorithm for Approximating a Curve by a Single-peaked Curve: Jinhee Chun (Tohoku University), Kunihiko Sadakane (Kyushu University) and Takeshi Tokuyama (Tohoku University)
A Dynamic Dictionary for Priced Information with Application: Anil Maheshwari and Michiel Smid (Carleton University)
Voronoi Diagram in the Flow Field: Tetsushi Nishida and Kokichi Sugihara (University of Tokyo)
Polygonal Path Approximation: a Query Based Approach: Ovidiu Daescu and Ningfang Mi (University of Texas at Dallas)

Session 1B: Graph and Combinatorial Algorithms I

A Vertex Incremental Approach for Dynamically Maintaining Chordal Graphs: Anne Berry (Université Clermont-Ferrand II), Pinar Heggernes and Yngve Villanger (University of Bergen)
Finding the Maximum Common Subgraph of a Partial k-Tree and a Graph with a Polynomially Bounded Number of Spanning Trees: Atsuko Yamaguchi and Hiroshi Mamitsuka (Kyoto University)
Hotlink Enhancement Algorithms for Web Directories: Ori Gerstel (IBM), Shay Kutten (The Technion), Rachel Matichin and David Peleg (The Weizmann Institute of Science)
Finding a Length-Constrained Maximum-Density Path in a Tree: Rung-Ren Lin, Wen-Hsiung Kuo and Kun-Mao Chao (National Taiwan University)

Session 2A: Computational Complexity I

The Intractability of Computing the Hamming Distance: Bodo Manthey and Rüdiger Reischuk (Universität zu Lübeck)
Infinitely-Often Autoreducible Sets: Richard Beigel (Temple University), Lance Fortnow (NEC Laboratories America) and Frank Stephan (University of Heidelberg)
Limiting Negations in Bounded-Depth Circuits: An Extension of Markov's Theorem: Shao Chin Sung (Japan Advanced Institute of Science and Technology) and Keisuke Tanaka (Tokyo Institute of Technology)
Computational Complexity Measures of Multipartite Quantum Entanglement: Tomoyuki Yamakami (University of Ottawa)

Session 2B: Graph and Combinatorial Algorithms II

A New Simple Algorithm for the Maximum-Weight Independent Set Problem on Circle Graphs: Gabriel Valiente (Technical University of Catalonia)
Polynomial Time 2-Approximation Algorithms for the Minmax Subtree Cover Problem: Hiroshi Nagamochi (Toyohashi University of Technology) and Kohei Okada (Matsushita Electric Industrial Co., Ltd.)
Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-hard Problems: Jianer Chen (Texas A&M University), Iyad Kanj (DePaul University) and Ge Xia (Texas A&M University)
A New Translation from Semi-Extended Regular Expressions into NFAs and Its Application to an Approximate Matching Problem: Hiroaki Yamamoto (Shinshu University)

Session 3A: Quantum Computation

The Quantum Query Complexity of 0-1 Knapsack and Associated Claw Problems: Vikraman Arvind (Institute of Mathematical Sciences, Chennai) and Rainer Schuler (University of Ulm)
Non-Interactive Quantum Perfect and Statistical Zero-Knowledge: Hirotada Kobayashi (Japan Science and Technology Corporation)
Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?: Hirotada Kobayashi (Japan Science and Technology Corporation), Keiji Matsumoto (National Institute of Informatics) and Tomoyuki Yamakami (University of Ottawa)
A Faster Lattice Reduction Method Using Quantum Search: Christoph Ludwig (Technische Universität Darmstad)

Session 3B: Graph and Combinatorial Algorithms III

Three Sorting Algorithms Using Priority Queues: Amr Elmasry (Alexandria University)
Lower Bounds on Correction Networks: Grzegorz Stachowiak (University of Wroclaw)
Approximate Regular Expression Searching with Arbitrary Integer Weights: Gonzalo Navarro (Univ. of Chile)
Constructing Compressed Suffix Arrays with Large Alphabets: Wing-Kai Hon, Tak-Wah Lam (The University of Hong Kong), Kunihiko Sadakane (Kyushu University) and Wing-Kin Sung (National University of Singapore)

Session 4A: Computational Geometry II

On the Geometric Dilation of Finite Point Sets: Annette Ebbers-Baumann, Ansgar Grüne and Rolf Klein (University of Bonn)
On Computing All Immobilizing Grasps of a Simple Polygon with Few Contacts: Jae-Sook Cheong, Herman Haverkort and Frank van der Stappen (Utrecht University)
Optimal Point Set Projections onto Regular Grids: José Miguel Díaz-Báñez (Universidad de Sevilla), Ferran Hurtado (Universitat Politècnica de Catalunya), Mario Alberto López (University of Denver) and J. Antoni Sellarès (Universitat de Girona)

Session 4B: Combinatorial Optimization I

An Approximation Algorithm for Dissecting a Rectangle into Rectangles with Specified Areas: Hiroshi Nagamochi (Toyohashi University of Technology) and Yuusuke Abe (NEC Software Tohoku, Ltd.)
A Faster Algorithm for Two-variable Integer Programming: Friedrich Eisenbrand and Sören Laue (Max Planck Institute for Computer Science)
Efficient Algorithms for Generation of Combinatorial Covering Suites: Adrian Dumitrescu (University of Wisconsin-Milwaukee)

Session 5A: Scheduling

A Better Approximation for the Two-Machine Flowshop Scheduling Problem with Time Lags: Yoshiyuki Karuno (Kyoto Institute of Technology) and Hiroshi Nagamochi (Toyohashi University of Technology)
On Minimizing Average Weighted Completion Time: A PTAS for the Job Shop Problem with Release Dates: Alexey Fishkin, Klaus Jansen (Christian-Albrechts-Universität zu Kiel) and Monaldo Mastrolilli (IDSIA)
On-line Scheduling of Parallel Jobs with Dependencies on 2-Dimensional Meshes: Deshi Ye (Zhejiang University) and Guochuan Zhang (Christian-Albrechts-Universität zu Kiel)

Session 5B: Computational Biology

Efficient Algorithms for Descendent Subtrees Comparison of Phylogenetic Trees with Applications to Co-evolutionary Classifications in Bacterial Genome: Yaw-Ling Lin (Providence University) and Tsan-Sheng Hsu (Academia Sinica)
Settling the Intractability of Multiple Alignment: Isaac Elias (Royal Institute of Technology, Stockholm)
Efficient Algorithms for Optimizing Whole Genome Alignment with Noise: TW Lam, N Lu, HF Ting, Prudence WH Wong and SM Yiu (University of Hong Kong)

Session 6A: Computational Geometry III

Segmenting Doughnut-shaped Objects in Medical Images: Xiaodong Wu (The University of Texas - Pan American)
On the Locality Properties of Space-Filling Curves: H. K. Dai and H. C. Su (Oklahoma State University)
Geometric Restrictions on Producible Polygonal Protein Chains: Erik D. Demaine (Massachusetts Institute of Technology), Stefan Langerman (Université Libre de Bruxelles) and Joseph O'Rourke (Smith College)
Symmetric Layout of Disconnected Graphs: Seok-Hee Hong and Peter Eades (University of Sydney)

Session 6B: Graph and Combinatorial Algorithms IV

Approximation Hardness of Minimum Edge Dominating Set and Minimum Maximal Matching: Miroslav Chlebík (Max Planck Institute for Mathematics in the Sciences, Leipzig) and Janka Chlebíková (Christian-Albrechts-Universität zu Kiel)
Enumerating Global Roundings of an Outerplanar Graph: Nadia Takki-Chebihi and Takeshi Tokuyama (Tohoku University)
Augmenting Forests to Meet Odd Diameter Requirements: Toshimasa Ishii (Toyohashi University of Technology), Shigeyuki Yamamoto (I FOR COM Co.,Ltd.) and Hiroshi Nagamochi (Toyohashi University of Technology)
On the Existence and Determination of Satisfactory Partitions in a Graph: Cristina Bazgan (Université Paris-Dauphine), Zsolt Tuza (Hungarian Academy of Sciences) and Daniel Vanderpooten (Université Paris-Dauphine)

Session 7A: Distributed and Parallel Algorithms

A Turn Function Scheme Realized in the Asynchronous Single-Writer/Multi-Reader Shared Memory Model: Tom Altman (University of Colorado at Denver), Yoshihide Igarashi (Gunma University) and Michiko Omori (NEC Corp.)
An Optimal Parallel Algorithm for c-Vertex-Ranking of Trees: Md. Abul Kashem and M. Ziaur Rahman (Bangladesh University of Engineering and Technology)

Session 7B: Graph and Combinatorial Algorithms V

The Student-Project Allocation Problem: David Abraham, Robert Irving and David Manlove (University of Glasgow)
Algorithms for Enumerating Circuits in Matroids: Endre Boros, Khaled Elbassioni, Vladimir Gurvich and Leonid Khachiyan (Rutgers University)
A Generalized Gale-Shapley Algorithm for a Discrete-Concave Stable-Marriage Model: Akinobu Eguchi (Panasonic Mobile Communications Co., Ltd.), Satoru Fujishige and Akihisa Tamura (Kyoto University)

Invited Talk 2

Drawing Plane Graphs: Takao Nishizeki (Tohoku University)

Session 8A: Data Structure

Succinct Data Structures for Searchable Partial Sums: Wing-Kai Hon (The University of Hong Kong), Kunihiko Sadakane (Kyushu University) and Wing-Kin Sung (National University of Singapore)
Range Mode and Range Median Queries on Lists and Trees: Danny Krizanc (Wesleyan University), Pat Morin and Michiel Smid (Carleton University)
Quasi-Perfect Minimally Adaptive q-ary Searchwith Unreliable Test: Ferdinando Cicalese (Università di Salerno ) and Christian Deppe (Universität Bielefeld)
New Ways to Construct Binary Search Trees: Travis Gagie (University of Toronto)

Session 8B: Graph and Combinatorial Algorithms VI

Approximation Algorithms for Optimization Problems in Graphs with Superlogarithmic Treewidth: Artur Czumaj (New Jersey Institute of Technology), Andrzej Lingas and Johan Nilsson (Lund University)
Biconnectivity on Symbolically Represented Graphs: a Linear Solution: Raffaella Gentilini and Alberto Policriti (Università di Udine)
A Dynamic Data Structure for Maintaining Disjoint Paths Information in Digraphs: Torsten Tholey (J. W. Goethe Universität Frankfurt)
Deterministic Algorithm for the t-Threshold Set Problem: Jeremy Barbay (University of British Columbia) and Claire Kenyon (École Polytechnique de Paris)

Session 9A: Combinatorial and Network Optimization

Energy-Efficient Wireless Network Design: Ioannis Caragiannis, Christos Kaklamanis and Panagiotis Kanellopoulos (Computer Technology Institute and University of Patras)
Wavelength Conversion in Shortest-Path All-Optical Networks: Thomas Erlebach and Stamatis Stefanakos (ETH Zürich)
A Heuristic for the Stacker Crane Problem on Trees which is Almost Surely Exact: Amin Coja-Oghlan (Humboldt-Universität zu Berlin), Sven O. Krumke (Konrad-Zuse-Zentrum für Informationstechnik) and Till Nierhoff (International Computer Science Institute)
Flexible Train Rostering: Stephan Eidenbenz (Los Alamos National Laboratory), Aris Pagourtzis (National Technical University of Athens) and Peter Widmayer (ETH Zürich)

Session 9B: Computational Complexity and Cryptography

Counting Complexity Classes over the Reals. I: The Additive Case: Peter Bürgisser (Paderborn University) and Felipe Cucker (City University of Hong Kong)
Some Properties of One-Pebble Turing Machines with Sublogarithmic Space: Atsuyuki Inoue, Akira Ito, Katsushi Inoue (Yamaguchi Univ.) and Tokio Okazaki (Josai International Univ.)
Hypergraph Decomposition and Secret Sharing: Giovanni Di Crescenzo (Telcordia Technologies) and Clemente Galdi (Research Academic Computer Technology Institute & Univ. of Patras)
A Promising Key Agreement Protocol: Eun-Kyung Ryu, Kee-Won Kim and Kee-Young Yoo (Kyungpook National University)

Session 10A: Game Theory and Randomized Algorithm

Rapid Mixing of Several Markov Chains for a Hard-Core Model: Ravi Kannan, Michael Mahoney (Yale University) and Ravi Montenegro (Georgia Institute of Technology)
Polynomial Time Approximate Sampler for Discretized Dirichlet Distribution: Tomomi Matsui (University of Tokyo), Mitsuo Motoki (Japan Advanced Institute of Science and Technology) and Naoyuki Kamatani (Tokyo Women's Medical University)
Fair Cost Allocations under Conflicts --- a Game-theoretic Point of View ---: Yoshio Okamoto (ETH Zürich)
Equilibria for Networks with Malicious Users: George Karakostas (McMaster University) and Anastasios Viglas (University of Toronto)

Session 10B: Algebraic and Arithmetic Computation

Quasi-Optimal Arithmetic for Quaternion Polynomials: Martin Ziegler (University of Paderborn)
Upper bounds on the Complexity of some Galois Theory Problems: Vikraman Arvind and Piyush Kurur (Institute of Mathematical Sciences, Chennai)
Unfolded Modular Multiplication: Wieland Fischer and Jean-Pierre Seifert (Infineon technologies AG)
Gauss Period, Sparse Polynomial, Redundant Basis, and Efficient Exponentiation for a Class of Finite Fields with Small Characteristic: Soonhak Kwon (Sungkyunkwan University), Chang Hoon Kim and Chun Pyo Hong (Daegu University)

[Top Page]