ICALP2002: accepted papers and preliminary program

Thu, 21 Mar 2002 19:19:43 +0100

This is a multi-part message in MIME format.
--------------9F1656E3A2720904ECEA2E70
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit

Dear Sir/Madam,

 I'm sending you the following information:

-the list of accepted papers for ICALP'2002 (an HTML table
 with two columns; authors and title)

-the preliminary program of ICALP'2002 is available on

http://sirius.lcc.uma.es/ICALP2002/PreliminarySchedule.html

(and on the "news" of ICALP2002 pages: http://www.lcc.uma.es/ICALP2002)

-the preliminary program of the satellite event "Global Computing"
 (in the same link).

I consider that this conference can be of your interest.
The registration will be open in a few days.
Best regards,
Rafael Morales

--------------9F1656E3A2720904ECEA2E70
Content-Type: text/html; charset=us-ascii;
 name="tableAceptICALP2002.htm"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="tableAceptICALP2002.htm"

<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=windows-1252">
<META NAME="Generator" CONTENT="Microsoft Word 97">
<TITLE>Track A</TITLE>
</HEAD>
<BODY>

<TABLE BORDER CELLSPACING=1 CELLPADDING=4 WIDTH=571>
<TR><TD WIDTH="34%" VALIGN="TOP">
Track A
</TD>
<TD WIDTH="66%" VALIGN="TOP">&nbsp;</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Peter Hertling;</TD>
<TD WIDTH="66%" VALIGN="TOP">
A Banach-Mazur Computable but not Markov Computable Function on the Computable Real Numbers</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Seth Pettie;</TD>
<TD WIDTH="66%" VALIGN="TOP">
A Faster All-pairs Shortest Path Algorithm for Real-weighted Sparse Graphs</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Juhani Karhum&auml;ki; Leonid P. Lisovik;</TD>
<TD WIDTH="66%" VALIGN="TOP">
A surprising undecidability result: The equivalence problem for finite substitutions on $ab^*c$</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Doerr Benjamin;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Antirandomizing the Wrong Game</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Piotr Berman; Marek Karpinski; Yakov Nekrich;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Approximating Huffman Codes in Parallel</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Marek Karpinski; Piotr Berman;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Nathan Segerlind;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Bounded Depth Frege with Counting Principles Polynomially Simulates Nullstellensatz Refutations</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Rolf Fagerberg; Gerth St&oslash;lting Brodal;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Cache Oblivious Distribution Sweeping</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Udo Adamy;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Call Control in Rings</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Jurdzinski Tomasz;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Church-Rosser Languages vs. UCFL</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Vincenzo Liberatore;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Circular Arrangements</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Victor Dalmau;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Constraint Satisfaction Problems in Non-Deterministic Logarithmic Space</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Joseph (Seffi) Naor;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Control Message Aggregation in Group Communication Protocols</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 John Hitchcock;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Correspondence Principles for Effective Dimensions</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Aggelos Kiayias; Moti Yung;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Cryptographic Hardness based on the Decoding of Reed-Solomon Codes</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Colin Stirling;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Deciding DPDA equivalence is primitive recursive</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Yoshiharu Kohayakawa; Brendan Nagle; Vojtech Rodl;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Efficient testing of hypergraphs</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Peter Sanders; Rene Beier; Naveen Sivadasan; Edgar Ramos;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Energy Optimal Routing in Radio Networks Using Geometric Data Structures</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Dima Grigoriev; Edward A. Hirsch; Dmitrii V. Pasechnik;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Exponential Lower Bound for Static Semi-Algebraic Proofs</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Rajeev Raman;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Exponential structures for cache-oblivious algorithms</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Karhan Akcoglu;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Fast Universalization of Investment Strategies with Provably Good Relative Returns</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Moses Charikar; Kevin Chen; Martin Farach-Colton;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Finding Frequent Items in Data Streams</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Thore Husfeldt;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Finding a Path of Superlogarithmic Length</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Xiaotie Deng; Guojun Li; Zimao Li; Bin ma; Lusheng Wang;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Genetic Design of Drug without Side-effect</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Leszek Gasieniec; Andrzej Lingas;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Gossiping with bounded size messages in unknown ad-hoc radio networks</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Elias Koutsoupias; Christos Papadimitriou; Alex Fabrikant;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Heuristically Optimized Trade-offs: A New Paradigm for Power Laws in the Internet</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Martin Strauss; Sudipto Guha; Piotr Indyk; Muthu Muthukrishnan;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Histogramming Data Streams with Fast Per-Item Processing</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Papazian Christophe;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Hyperbolic Recognition by Cellular Automata</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Camil Demetrescu; Giuseppe F. Italiano;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Improved Bounds and New Trade-Offs for Dynamic All Pairs Shortest Paths</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Jonas Holmerin;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Improved Inapproximability Results for Vertex Cover on k-regular Hyper-graphs</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 V.S. Anil Kumar Kumar;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Improved Results for Stackelberg Scheduling Strategies</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Tomasz Radzik;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Improving time bounds on maximum generalised flow computation</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Lars Engebretsen; Jonas Holmerin; Alexander Russell;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Inapproximability Results for Equations Over Finite Groups</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Sebastian Bala;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Intersection of Regular Language and Star Hierarchy</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Ryuhei Uehara;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Linear Time Algorithms on Chordal Bipartite and Strongly Chordal Graphs</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Moses Charikar; Piotr Indyk; Rina Panigrahy;</TD>
<TD WIDTH="66%" VALIGN="TOP">
New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching and Related Problems</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Steve Seiden; Leah Epstein; Rob van Stee;</TD>
<TD WIDTH="66%" VALIGN="TOP">
New Bounds for Variable-Sized and Resource Augmented Online Bin Packing</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Nicola Galesi; Juan Luis Esteban; Jochen Messner;</TD>
<TD WIDTH="66%" VALIGN="TOP">
On the Complexity of Resolution with Bounded Conjunctions</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Conrado Martinez; Amalia Duch;</TD>
<TD WIDTH="66%" VALIGN="TOP">
On the average performance of orthogonal range search in multidimensional data structures</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Sylvain Lombardy;</TD>
<TD WIDTH="66%" VALIGN="TOP">
On the construction of reversible automata for reversible languages</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Rasmus Pagh; Anna &Ouml;stlin;</TD>
<TD WIDTH="66%" VALIGN="TOP">
One-Probe Search</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Xiaodong Wu; Danny Chen;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Optimal Net Surface Problems with Applications</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Andreas Jakoby; Maciej Liskiewicz;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Paths Problems in Symmetric Logarithmic Space</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Eyal Kushilevitz; Yuval Ishai;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Perfect Constant-Round Secure Computation via Perfect Randomizing Polynomials</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Andrzej Lingas; Artur Czumaj; Hairong Zhao;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Polynomial-Time Approximation Schemes for the Euclidean Survivable Network Design Problem</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Marek Chrobak; Leah Epstein; John Noga; Jiri Sgall; Rob van Stee; Tomas Tichy; Nodari Vakhania;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Preemptive Scheduling in Overloaded Systems</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Amr Elmasry;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Priority queues, pairing and adaptive sorting</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Chris Pollett; Farid Ablayev; Cris Moore;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Quantum and Stochastic Branching Programs of Bounded Width</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Philippe Flajolet;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Random Sampling from Boltzmann Principles</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Vasco Brattka;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Random numbers and an incomplete immune recursive set</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Harald R&auml;cke; Micah Adler; Naveen Sivadasan; Christian Sohler; Berthold V&ouml;cking;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Randomized Pursuit-Evasion in Graphs</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Kazuo Iwama;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Removable On-Line Knapsack Problems</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Peter Damaschke;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Scheduling search procedures</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Carlo Fantozzi; Andrea Pietracaprina; Geppino Pucci;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Seamless Integration of Parallelism and Memory Hierarchy</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Gerth St&oslash;lting Brodal; Rune Bang Lyngs&oslash;; Anna &Ouml;stlin; Christian N. S. Pedersen;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Solving the String Statistics Problem in Time $O(n\log n)$</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Ugo Vaccaro; Pavol Hell; Ladislav Stacho; Luisa Gargano;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Spanning trees with bounded number of branch vertices</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Wolfgang Merkle;</TD>
<TD WIDTH="66%" VALIGN="TOP">
The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Robert A. Hearn; Erik D. Demaine;</TD>
<TD WIDTH="66%" VALIGN="TOP">
The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Ollinger Nicolas;</TD>
<TD WIDTH="66%" VALIGN="TOP">
The Quest for Small Universal Cellular Automata</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Dimitrios Fotakis; Spyros Kontogiannis; Elias Koutsoupias; Marios Mavronicolas; Paul Spirakis;</TD>
<TD WIDTH="66%" VALIGN="TOP">
The Structure and Complexity of Nash Equilibria for a Selfish Routing Game</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Noam Nisan;</TD>
<TD WIDTH="66%" VALIGN="TOP">
The communication complexity of approximate set packing and covering</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Mikolaj Bojanczyk;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Two-Way Alternating Automata and Finite Models</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Mohamed Mosbah; Nicolas Bonichon; Bertrand Le Saec;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Wagner's theorem on Realizers</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 John Hitchcock; Jack Lutz;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Why Computational Complexity Requires Stricter Martingales</TD>
</TR>
</TABLE>

&nbsp;
&nbsp;
&nbsp;
&nbsp;
<TABLE BORDER CELLSPACING=1 CELLPADDING=4 WIDTH=571>
<TR><TD WIDTH="34%" VALIGN="TOP">
Track B</TD>
<TD WIDTH="66%" VALIGN="TOP">&nbsp;</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Philippa Gardner;</TD>
<TD WIDTH="66%" VALIGN="TOP">
A Spatial Logic for Querying Graphs</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Rosu Grigore;</TD>
<TD WIDTH="66%" VALIGN="TOP">
A Total Approach to Partial Algebraic Specification</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Paul Gastin;</TD>
<TD WIDTH="66%" VALIGN="TOP">
An Elementary Expressively Complete Temporal Logic for Mazurkiewicz Traces</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Lohrey Markus;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Axiomatising Divergence</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Marco Kick;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Bialgebraic Modelling of Timed Processes</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Alex Simpson;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Comparing functional paradigms for exact real-number computation</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Bharat Adsul; Milind Sohoni;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Expressively Complete Tractable Linear Time Temporal Logics over Traces</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Luke Ong;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Games Characterizing Levy-Longo Trees</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Zeitoun Marc; muscholl anca; genest blaise; seidl helmut;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Infinite-state High-Level MSCs: Model-Checking and Realizability</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 James Worrell; Keye Martin; Mike Mislove;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Measuring the Probabilistic Powerdomain</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Michal Bielecki; Hidders Jan; Jan Paredaens; Jerzy Tyszkiewicz; Jan Van den Bussche;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Navigating with a Browser</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Colcombet Thomas;</TD>
<TD WIDTH="66%" VALIGN="TOP">
On Families of Graphs Having a Decidable First Order Theory with Reachability</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Dietrich Kuske; Markus Lohrey;</TD>
<TD WIDTH="66%" VALIGN="TOP">
On the theory of one-step rewriting in trace monoids</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Jiri Srba;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Strong Bisimilarity and Regularity of Basic Process Algebra is PSPACE-Hard</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Thierry Cachat;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Symbolic Strategy Synthesis for Games on Pushdown Graphs</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Franck van Breugel;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Testing Labelled Markov Processes</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 J. B. Wells Wells;</TD>
<TD WIDTH="66%" VALIGN="TOP">
The Essence of Principal Typings</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Freddy Mang; Thomas A. Henzinger; Orna Kupferman; Sriram Krishnan;</TD>
<TD WIDTH="66%" VALIGN="TOP">
The Synthesis of Uninitialized Systems</TD>
</TR>
<TR><TD WIDTH="34%" VALIGN="TOP">
 Klaus Wich;</TD>
<TD WIDTH="66%" VALIGN="TOP">
Universal Inherence of cycle-free context-free Ambiguity Functions</TD>
</TR>
</TABLE>

<FONT SIZE=2></FONT></BODY>
</HTML>

--------------9F1656E3A2720904ECEA2E70--