Lecture Notes in Computer Science 2976 EditedbyG.Goos,J.Hartmanis,andJ.vanLeeuwen 3 Berlin Heidelberg NewYork HongKong London Milan Paris Tokyo Martin Farach-Colton (Ed.) LATIN 2004: Theoretical Informatics 6th Latin American Symposium Buenos Aires, Argentina, April 5-8, 2004 Proceedings 1 3 SeriesEditors GerhardGoos,KarlsruheUniversity,Germany JurisHartmanis,CornellUniversity,NY,USA JanvanLeeuwen,UtrechtUniversity,TheNetherlands VolumeEditor MartinFarach-Colton RutgersUniversity DepartmentofComputerScience,Piscataway,NJ08855,USA E-mail:[email protected] Cataloging-in-PublicationDataappliedfor AcatalogrecordforthisbookisavailablefromtheLibraryofCongress. BibliographicinformationpublishedbyDieDeutscheBibliothek DieDeutscheBibliothekliststhispublicationintheDeutscheNationalbibliografie; detailedbibliographicdataisavailableintheInternetat<http://dnb.ddb.de>. CRSubjectClassification(1998):F.2,F.1,E.1,E.3,G.2,G.1,I.3.5,F.3,F.4 ISSN0302-9743 ISBN3-540-21258-2Springer-VerlagBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer-Verlag.Violationsare liableforprosecutionundertheGermanCopyrightLaw. Springer-VerlagisapartofSpringerScience+BusinessMedia springeronline.com (cid:2)c Springer-VerlagBerlinHeidelberg2004 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyPTP-Berlin,Protago-TeX-ProductionGmbH Printedonacid-freepaper SPIN:10989654 06/3142 543210 Preface This volume contains the proceedings of the Latin American Theoretical Infor- matics(LATIN)conferencethatwasheldinBuenosAires,Argentina,April5–8, 2004. The LATIN series of symposia was launched in 1992 to foster interactions between the Latin American community and computer scientists around the world. This was the sixth event in the series, following Sa˜o Paulo, Brazil (1992), Valparaiso, Chile (1995), Campinas, Brazil (1998), Punta del Este, Uruguay (2000), and Cancun, Mexico (2002). The proceedings of these conferences were also published by Springer-Verlag in the Lecture Notes in Computer Science series: Volumes 583, 911, 1380, 1776, and 2286, respectively. Also, as before, we published a selection of the papers in a special issue of a prestigious journal. Wereceived178submissions.Eachpaperwasassignedtofourprogramcom- mittee members, and 59 papers were selected. This was 80% more than the previous record for the number of submissions. We feel lucky to have been able tobuildonthesolidfoundationprovidedbytheincreasinglysuccessfulprevious LATINs.AndweareverygratefulforthetirelessworkofPabloMart´ınezL´opez, theLocalArrangementsChair.Finally,wethankSpringer-Verlagforpublishing these proceedings in its LNCS series. December 2003 Martin Farach-Colton VI Preface Invited Presentations Cynthia Dwork, Microsoft Research, USA Mike Paterson, University of Warwick, UK Yoshiharu Kohayakawa, Universidade de Sa˜o Paulo, Brazil Jean-Eric Pin, CNRS/Universit´e Paris VII, France Dexter Kozen, Cornell University, NY, USA Organization Program Chair Martin Farach-Colton, Rutgers University, USA Local Arrangments Chair Pablo Mart´ınez L´opez, Univ. Nacional de La Plata, Argentina Steering Committee Ricardo Baeza Yates, Univ. de Chile, Chile Gaston Gonnet, ETH Zurich, Switzerland Claudio Lucchesi, Univ. de Campinas, Brazil Imre Simon, Univ. de Sa˜o Paulo, Brazil Program Committee Michael Bender, SUNY Stony Brook, USA Gerth Brodal, University of Aarhus, Denmark Fabian Chudak, ETH, Switzerland Mary Cryan, University of Leeds, UK Pedro D’Argenio, UNC, Argentina Martin Farach-Colton (Chair), Rutgers University, USA David Fern´andez-Baca, Iowa State University, USA Paolo Ferragina, Universita` di Pisa, Italy Juan Garay, Bell Labs, USA Claudio Guti´errez, Universidad de Chile, Chile John Iacono, Polytechnic University, USA Bruce Kapron, University of Victoria, Canada Valerie King, University of Victoria, Canada Marcos Kiwi, Universidad de Chile, Chile Sulamita Klein, Univ. Federal do Rio de Janeiro, Brazil Stefan Langerman, Universit´e Libre de Bruxelles, Belgium Moshe Lewenstein, Bar Ilan University, Israel Alex L´opez-Ortiz, University of Waterloo, Canada Eduardo Sany Laber, PUC-Rio, Brazil Pablo E. Mart´ınez L´opez, UNLP, Argentina S. Muthukrishnan, Rutgers Univ. and AT&T Labs, USA Sergio Rajsbaum, Univ. Nacional Auto´noma de M´exico, Mexico Andrea Richa, Arizona State University, USA Gadiel Seroussi, HP Labs, USA Alistair Sinclair, UC Berkeley, USA Danny Sleator, Carnegie Mellon University, USA VIII Organization Local Arrangements Committee Eduardo Bonelli, Universidad Nacional de La Plata Carlos “Greg” Diuk, Universidad de Buenos Aires Santiago Figueira, Universidad de Buenos Aires Carlos Lo´pez Pombo, Universidad de Buenos Aires Mat´ıas Menni, Universidad Nacional de La Plata Pablo E. Mart´ınez L´opez (Chair), Univ. de La Plata Alejandro Russo, Universidad de Buenos Aires Marcos Urbaneja S´anchez, Universidad Nacional de La Plata Hugo Zaccheo, Universidad Nacional de La Plata Referees Dimitris Achlioptas Moses Charikar Gudmund S. Frandsen Ali Akhavi Chandra Chekuri Antonio Frangioni David Aldous Koen Claessen Ari Freund Jorge Almeida Don Coppersmith Daniel Fridlender Greg Aloupis Massimo Coppola Alan Frieze Andris Ambainis Ricardo Corin Fabio Gadducci Eric Bach Peter Csorba Naveen Garg Pablo Barcelo Ricardo Dahab Leszek Gasieniec Alexander Barg Ivan Damgaard Vincenzo Gervasi Elad Barkan Gianna Del Corso Jovan Golic Paulo Barreto Erik Demaine Roberto Grossi Tomas Barros Vinay Deolalikar Antonio Gulli Cecilia Bastarrica Vania Maria F. Dias Hermann Haeusler Gabriel Baum Irit Dinur Petr Hajek Amir Ben-Amram Shlomi Dolev Angele Hamel Julien Bernet Dan Dougherty Darrel Hankerson Javier Blanco Vida Dujmovic Carmit Harel Paulo Blauth Dannie Durand Amir Herzberg Hans Bodlaender Jerome Durand-Lose Alejandro Hevia Philip Bohannon Nadav Efraty Steve Homer Eduardo Bonelli John Ellis Carlos Hurtado Prosenjit Bose Hazel Everett Ferran Hurtado Herv´e Br¨onnimann Luerbio Faria Lucian Ilie Veronique Bruyere Sa´ndor P. Fekete Neil Immerman John Brzozowski Claudson Ferreira Andre Inacio Reis Ayelet Butman Bornstein Gabriel Infante Lopez Ying Cai Santiago Figueira Achim Jung Carlile Campos Lavor Celina M. H. Charanjit Jutla H´ector Cancela de Figueiredo Mehmet Hakan Karaata Jean Cardinal Philippe Flajolet Hakan Karaata Olivier Carton Paola Flocchini Makino Kazuhisa Organization IX Carmel Kent Fatma Mili Alexander Russell Claire Kenyon Ruy Milidiu Andrei Sabelfeld Tien Kieu Peter Bro Miltersen Kai Salomaa Tomi Klein Manuela Montangero Louis Salvail Jon Kleinberg Pat Morin Luigi Santocanale Lars R. Knudsen R´emi Morin Eric Schost Cetin Koc Sergio Mun˜oz Matthias Schro¨der Ulrich Kohlenbach Seffi Naor Marinella Sciortino Goran Konjevod Gonzalo Navarro Michael Segal Peter Kornerup Alantha Newman Arun Sen Margarita Korovina Stefan Nickel Rahul Shah Guy Kortsarz Peter Niebert Jeff Shallit Natalio Krasnogor Rolf Niedermeier Scott Shenker Danny Krizanc Soohyun Oh David Shmoys Marcos Kurban Alfredo Olivero Amin Shokrollahi Alair Lago Nicolas Ollinger Igor Shparlinski Leema Lallmamode Melih Onus Riccardo Silvestri Orlando Lee Erik Ordentlich Guillermo Simari Noa Lewenstein Friedrich Otto Imre Simon Yehuda Lindell Daniel Panario Bjarke Skjernaa Ricardo Linden Alessandro Panconesi Dan Spielman Claudia Linhares Luis Pardo Jessica Staddon Marina Lipshtein Rodrigo Paredes Mike Steele Errol Lloyd Ojas Parekh William Steiger Martin Loebl Michal Parnas Bernd Sturmfels John Longley Mike Paterson Subhash Suri Fabrizio Luccio Boaz Patt-Shamir Maxim Sviridenko Alejandro Maass David Peleg Wojciech Szpankowski Guido Macchi Marco Pellegrini Shang-Hua Teng Phil MacKenzie David Pelta Siegbert Tiga Nelson Maculan Daniel Penazzi Loana Tito Nogueira Francesco Maffioli Pino Persiano Yaroslav Usenko Greg Malewicz Rau´l Piaggio Santosh Vempala Arnaldo Mandel Benny Pinkas Newton Vieira Giovanni Manzini Nadia Pisanti Narayan Vikas Alvaro Mart´ın Ely Porat Jorge Villavicencio Demetrio Martin Vilela Daniele Pretolani Alfredo Viola Carlos Alberto Corrado Priami Elisa Viso Martinhon Cristophe Prieur Marcelo Weinberger Brian Mayoh Kirk Pruhs Nicolas Wolovick Robert W. McGrail Geppino Pucci David Wood Candido F.X. Claude-Guy Quimper Jinyun Yuan de Mendonca Rajmohan Rajaraman Michal Ziv-Ukelson Mat´ıas Menni Desh Ranjan Andrea Mennucci Matt Robshaw Peter Merz Ricardo Rodr´ıguez