LATIN 2004


Chair
Program Committee
Organizing Committee
Invited Speakers
Proceeding
Papers
Sponsors
Location
Photos
Statistics


Chair
Martin Farach-Colton, Rutgers University, USA..

[Top] [Home] [All LATIN Chairs]

Program Committee
Michael Bender, SUNY Stony Brook, USA.
Gerth Brodal, Univ. of Aarhus, Denmark.
Fabian Chudak, ETH, Switzerland.
Mary Cryan, Univ. of Leeds, UK.
Pedro D'Argenio, UNC, Argentina.
Martin Farach-Colton (Chair), Rutgers Univ., USA.
David Fernández-Baca, Iowa State Univ., USA.
Paolo Ferragina, Universitá di Pisa, Italy.
Juan Garay, Bell Labs, USA.
Claudio Gutiérrez, Universidad de Chile.
John Iacono, Polytechnic Univ., USA.
Bruce Kapron, Univ. of Victoria, Canada.
Valerie King, Univ. of Victoria, Canada.
Marcos Kiwi, Universidad de Chile.
Sulamita Klein, Univ. Federal do Rio de Janeiro, Brazil.
Stefan Langerman, Université Libre de Bruxelles, Belgium.
Moshe Lewenstein, Bar Ilan Univ., Israel.
Alex López-Ortiz, Univ. of Waterloo, Canada.
Eduardo Sany Laber, PUC-Rio, Brazil.
Pablo E. Martínez López, UNLP, Argentina.
S. Muthukrishnan, Rutgers Univ. and AT&T Labs, USA.
Sergio Rajsbaum, Univ. Nacional Autónoma de México.
Andrea Richa, Arizona State Univ., USA.
Gadiel Seroussi, HP Labs, USA.
Alistair Sinclair, UC Berkeley, USA.
Danny Sleator, Carnegie Mellon Univ., USA.

[Top] [Home] [All LATIN PCs]

Organizing Committee
Eduardo Bonelli, Univ. de La Plata (UNLP), Argentina.
Carlos "Greg" Diuk, Univ. de Buenos Aires (UBA), Argentina.
Santiago Figueira, Univ. de Buenos Aires (UBA), Argentina.
Carlos López Pombo, Univ. de Buenos Aires (UBA), Argentina.
Matí Menni, Univ. de La Plata (UNLP), Argentina.
Pablo E. Martínez López (Chair), Univ. de La Plata (UNLP), Argentina.
Alejandro Russo, Univ. de Buenos Aires (UBA), Argentina.
Marcos Urbaneja Sánchez, Univ. de La Plata (UNLP), Argentina.
Hugo Zaccheo, Univ. de La Plata (UNLP), Argentina.

[Top] [Home] [All LATIN Org. Committees]

Invited Speakers
Cynthia Dwork, (Microsoft Research), Fighting Spam: The Science.
Mike Paterson, (U. of Warwick), Analysis of Scheduling Algorithms for Proportionate Fairness.
We consider a multiprocessor operating system in which each current job is guaranteed a given proportion over time of the total processor capacity. A scheduling algorithm allocates units of processor time to appropriate jobs at each time step. We measure the goodness of such a scheduler by the maximum amount by which the cumulative processor time for any job ever falls below the ``fair'' proportion guaranteed in the long term.

In particular we focus our attention on very simple schedulers which impose minimal computational overheads on the operating system. For several such schedulers we obtain upper and lower bounds on their deviations from fairness. The scheduling quality which is achieved depends quite considerably on the relative processor proportions required by each job.

We will outline the proofs of some of the upper and lower bounds, both for the unrestricted problem and for restricted versions where constraints are imposed on the processor proportions. Many problems remain to be investigated and we will give the results of some exploratory simulations.

This is joint research with Micah Adler, Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg and Paul Goldberg.

Yoshiharu Kohayakawa, (U. Sao Paolo), Advances in the Regularity Method.
Jean-Eric Pin, (CNRS/U. Paris VII), The consequences of Imre Simon's work in the theory of automata, languages and semigroups.
In this lecture, I will show how influential has been the work of Imre in the theory of automata, languages and semigroups. I will mainly focus on two celebrated problems, the restricted star-height problem (solved) and the decidability of the dot-depth hierarchy (still open). These two problems lead to surprising developments and are currently the topic of very active research.

I will present the prominent results of Imre on both topics, and demonstrate how these results have been the motor nerve of the research in this area for the last thirty years.

Dexter Kozen, (Cornell U.), Kleene Algebra with Tests and the Static Analysis of Programs.
I will propose a general framework for the static analysis of programs based on Kleene algebra with tests (KAT). I will show how KAT can be used to statically verify compliance with safety policies specified by security automata. The method is sound and complete over relational interpretations. I will illustrate the method on an example involving the correctness of a device driver.

[Top] [Home] [All LATIN Inv. Speakers]

Papers
Mike Paterson, Analysis of Scheduling Algorithms for Proportionate Fairness. [Bibtex]

Yoshiharu Kohayakawa, Advances in the Regularity Method. [Bibtex]

Cynthia Dwork, Fighting Spam: The Science. [Bibtex]

Jean-Eric Pin, The consequences of Imre Simon's work in the theory of automata, languages and semigroups. [Bibtex]

Eduardo Sany Laber, Renato Carmo and Yoshiharu Kohayakawa, Querying Priced Information in Databases: the Conjuntive Case. [Bibtex]

Funda Ergun, S. Muthukrishnan and Cenk Sahinalp, Sublinear Methods for Detecting Periodic Trends in Data Streams. [Bibtex]

Graham Cormode and S. Muthukrishnan, An Improved Data Stream Summary: The Count-Min Sketch and its Applications. [Bibtex]

Kimmo Fredriksson, Veli Mäkinen and Gonzalo Navarro, Rotation and Lighting Invariant Template Matching. [Bibtex]

Josep Díaz, Maria Serna and Nicholas Wormald, Computation of the bisection width for random d-regular graphs. [Bibtex]

Christian Borgs, Jennifer Chayes, Stephan Mertens and Boris Pittel, Constrained Integer Partitions. [Bibtex]

Abraham Flaxman, David Gamarnik and Gregory Sorkin, Embracing the Giant Component. [Bibtex]

Dimitris Achlioptas, Mike Molloy, Cristopher Moore and Frank Van Bussel, Sampling Grid Colourings with Fewer Colours. [Bibtex]

Lane Hemaspaandra, Mitsunori Ogihara, Mohammed Zaki and Marius Zimand, The Complexity of Finding Top-Toda-Equivalence-Class~Members. [Bibtex]

Tomás Feder, Pavol Hell, Sulamita Klein, Loana Tito Nogueira and Fábio Protti, List Partitions of Chordal Graphs. [Bibtex]

Erik D. Demaine, Fedor Fomin, Mohammad Taghi Hajiaghayi and Dimitrios M. Thilikos, Bidimensional Parameters and Local Treewidth. [Bibtex]

Frank Gurski and Egon Wanke, Vertex Disjoint Paths on Clique-Width Bounded Graphs. [Bibtex]

Frederic Gardi, On partitioning interval and circular-arc graphs into proper interval subgraphs with applications. [Bibtex]

Pierre Fraigniaud, Leszek Gasieniec, Dariusz R. Kowalski and Andrzej Pelc, Collective tree exploration. [Bibtex]

Alper Üngör, Off-centers: A new type of Steiner points for computing size-optimal quality-guaranteed Delaunay triangulations. [Bibtex]

Hervé Brönnimann and Timothy Chan, Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time. [Bibtex]

Claudio Gutierrez, Flavio Gutierrez and Maria-Cecilia Rivara, A Geometric Approach to the Bisection Method. [Bibtex]

Ho-Kwok Dai and X. W. Zhang, Improved Linear Expected-Time Algorithms for Computing Maxima. [Bibtex]

Jens S. Kohrt and Kirk Pruhs, Constant Approximation Algorithm for Sorting Buffers. [Bibtex]

Kirk Pruhs and Gerhard Woeginger, Approximation schemes for a class of subset selection problems. [Bibtex]

Prabhakar Gubbala and Balaji Raghavachari, Finding k-connected subgraphs with minimum average weight. [Bibtex]

Ke Yang, On the (Im)possibility of Non-interactive Correlation Distillation. [Bibtex]

Volker Diekert and Paul Gastin, Pure future local temporal logics are expressively complete for Mazurkiewicz traces. [Bibtex]

Sylvain Lombardy and Jacques Sakarovitch, How expressions code for automata. [Bibtex]

Shigeki Akiyama, Frédérique Bassino and Christiane Frougny, Automata for arithmetic Meyer sets. [Bibtex]

Manuel Bodirsky, Tobias Gärtner, Timo von Oertzen and Jan Schwinghammer, Efficiently Computing the Density of Regular Languages. [Bibtex]

Maxime Crochemore, Costas Iliopoulos, Manal Mohamed and Marie-France Sagot, Longest Repeats with a Block of Don't Cares. [Bibtex]

John Rhodes and Benjamin Steinberg, Join Irreducible Pseudovarieties, Group Mapping and Kovacs-Newman Semigroups. [Bibtex]

Olivier Carton and Chloe Rispal, Complementation of rational sets on scattered linear orderings of finite rank. [Bibtex]

Marcos Kiwi, Martin Loebl and Jirí Matousek, Expected length of the longest common subsequence for large alphabets. [Bibtex]

Gadiel Seroussi, Universal types and simulation of individual sequences. [Bibtex]

Gérard Cohen and Hans Georg Schaathun, Separating Codes: Constructions and Upper Bounds. [Bibtex]

Sergei Bespamyatnikh, Encoding Homotopy of Paths in the Plane. [Bibtex]

Saverio Caminiti, Irene Finocchi and Rossella Petreschi, A unified approach to coding labeled trees. [Bibtex]

Hervé Brönnimann and Marc Glisse, Cost Optimal Trees for Ray Shooting. [Bibtex]

Flavio Keidi Miyazawa and Yoshiko Wakabayashi, Packing problems with orthogonal rotations. [Bibtex]

Alantha Newman and Matthias Ruhl, Combinatorial Problems on Strings with Applications to Protein Folding. [Bibtex]

Mark Cieliebak and Stephan Eidenbenz, Measurement Errors Make the Partial Digest Problem NP-hard. [Bibtex]

Jean Cardinal and Stefan Langerman, Designing Small Keyboards is Hard. [Bibtex]

James R. Lee, Manor Mendel and Assaf Naor, Metric structures in $L_1$: Dimension, snowflakes, and average distortion. [Bibtex]

Richard J. Lipton and Evangelos Markakis, Nash Equilibria via Polynomial Equations. [Bibtex]

Raja Jothi and Balaji Raghavachari, Minimum Latency Tours and the k-Traveling Repairmen Problem. [Bibtex]

Nikhil Bansal and Kirk Pruhs, Server Scheduling in the Weighted $l_p$ Norm. [Bibtex]

Martin Fürer, An Improved Communication-Randomness Tradeoff. [Bibtex]

Paul Gastin, Benjamin Lerman and Marc Zeitoun, Distributed games and distributed control for asynchronous systems. [Bibtex]

Mihai Badoiu and Erik D. Demaine, A Simplified and Dynamic Unified Structure. [Bibtex]

Ali Akhavi and Celine Moreira Dos Santos, Another view of the Gaussian algorithm. [Bibtex]

Endre Boros, Khaled Elbassioni, Vladimir Gurvich and Leonid Khachiyan, Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections. [Bibtex]

Jesper Jansson, Joseph H.-K. Ng, Kunihiko Sadakane and Wing-Kin Sung, Rooted Maximum Agreement Supertrees. [Bibtex]

Edith Hemaspaandra, Holger Spakowski and Mayur Thakur, Complexity of Cycle Length Modularity Problems in Graphs. [Bibtex]

Dusan Guller, Procedural Semantics for Fuzzy Disjunctive Programs on Residuated Lattices. [Bibtex]

Olga Tveretina and Hans Zantema, A Proof System and a Decision Procedure for Equality Logic. [Bibtex]

Argimiro Arratia and Carlos Ortiz, Approximating the expressive power of logics in finite models. [Bibtex]

Joachim von zur Gathen, Arithmetic circuits for discrete logarithms. [Bibtex]

Jeff Edmonds, On the Competitiveness of AIMD-TCP within a General Network. [Bibtex]

Mark Cieliebak, Gathering Non-Oblivious Mobile Robots. [Bibtex]

Bernard Mans and Igor Shparlinski, Bisecting and Gossiping in Circulant Graphs. [Bibtex]

Paola Flocchini, Evangelos Kranakis, Danny Krizanc, Nicola Santoro and Cindy Sawchuk, Mobile Agent Rendezvous in a Ring. [Bibtex]

Jeremy Elson, Richard Karp, Christos Papadimitriou and Scott Shenker, Global Synchronization in Sensornets. [Bibtex]



[Top] [Home] [All LATIN Papers]

Sponsors
HP
Sociedad Argentida de Informática e Investigación Operativa (SADIO)
El Ojo del Huracán
Microsoft

[Top] [Home] [All LATIN Sponsors]

Location
Loct'2004

Conference Site

The conference was held at the Elevage Hotel in the heart of Buenos Aires.

Buenos Aires is the capital of Argentina and one of the world's great cities. Its atractions are those of a major cosmipolitan center: architecture, night-life, restaurants, theater, music, and flaneurism.


[Top] [Home] [All LATIN Locations]

Photos

[Top] [Home] [All LATIN Photos]

Statistics
General:
No. of submissions 178
No. of accepted papers 59
% of accepted papers 33.1%
Total No. of authors 146
Avg. No. of authors per paper 2.47
No. of countries represented 22
 
No. of papers according to how many authors work in Latin-America
    At least one 7(11.9%)
    All 3(5.1%)


Statistics by Country of Author's Affiliation

Authors*Papers**

60.0(41.1%)25.32(42.9%)USA
17.5(12.0%)7.79(13.2%)France
12.0(8.2%)4.08(6.9%)Canada
9.5(6.5%)3.96(6.7%)Germany
8.0(5.5%)2.60(4.4%)Brazil
5.0(3.4%)1.67(2.8%)Chile
4.5(3.1%)1.12(1.9%)UK
3.5(2.4%)1.17(2.0%)Spain
3.0(2.1%)1.00(1.7%)Italy
3.0(2.1%)1.50(2.5%)Netherlands
3.0(2.1%)0.75(1.3%)Singapore
2.0(1.4%)1.00(1.7%)Australia
2.0(1.4%)1.00(1.7%)Belgium
2.0(1.4%)1.50(2.5%)Switzerland
2.0(1.4%)0.75(1.3%)Norway
2.0(1.4%)0.58(1.0%)Japan
2.0(1.4%)0.67(1.1%)Finland
2.0(1.4%)0.67(1.1%)Czech Republic
1.0(0.7%)1.00(1.7%)Slovakia
1.0(0.7%)0.50(0.8%)Denmark
0.5(0.3%)0.25(0.4%)Venezuela
0.5(0.3%)0.12(0.2%)Poland

Authors with n affiliations contributes 1/n to each affiliation.
** Papers with n authors contribute 1/n to each affiliation.


Statistics by Region of Author's Affiliation

Authors*Papers**

72.0(49.3%)29.4(49.8%)USA & Canada
53.5(36.6%)22.8(38.6%)Europe
13.5(9.2%)4.5(7.7%)Latin-America
7.0(4.8%)2.3(4.0%)Australia & Asia

Authors with n affiliations contributes 1/n to each affiliation.
** Papers with n authors contribute 1/n to each affiliation.


Africa

Australia & Asia

Australia Mans, Bernard; Shparlinski, Igor;
Japan Akiyama, Shigeki; Sadakane, Kunihiko;
Singapore Jansson, Jesper; Ng, Joseph H.-K.; Sung, Wing-Kin;

Europe

UK Crochemore, Maxime; Gasieniec, Leszek; Iliopoulos, Costas; Mohamed, Manal; Schwinghammer, Jan;
Italy Caminiti, Saverio; Finocchi, Irene; Petreschi, Rossella;
Germany Bodirsky, Manuel; Diekert, Volker; Gärtner, Tobias; Gurski, Frank; Kowalski, Dariusz R.; Mertens, Stephan; Spakowski, Holger; Wanke, Egon; von Oertzen, Timo; von zur Gathen, Joachim;
Switzerland Cieliebak, Mark;
Belgium Cardinal, Jean; Langerman, Stefan;
Norway Fomin, Fedor; Schaathun, Hans Georg;
Netherlands Tveretina, Olga; Woeginger, Gerhard; Zantema, Hans;
France Akhavi, Ali; Bassino, Frédérique; Carton, Olivier; Cohen, Gérard; Crochemore, Maxime; Dos Santos, Celine Moreira; Fraigniaud, Pierre; Frougny, Christiane; Gardi, Frederic; Gastin, Paul; Glisse, Marc; Lerman, Benjamin; Lombardy, Sylvain; Rispal, Chloe; Sagot, Marie-France; Sakarovitch, Jacques; Zeitoun, Marc;
Slovakia Guller, Dusan;
Poland Kowalski, Dariusz R.;
Finland Fredriksson, Kimmo; Mäkinen, Veli;
Denmark Kohrt, Jens S.;
Spain Arratia, Argimiro; Díaz, Josep; Serna, Maria; Thilikos, Dimitrios M.;
Czech Republic Loebl, Martin; Matousek, Jirí;

Latin-America

Chile Gutierrez, Flavio; Kiwi, Marcos; Navarro, Gonzalo; Rivara, Maria-Cecilia;
Brazil Carmo, Renato; Klein, Sulamita; Kohayakawa, Yoshiharu; Laber, Eduardo Sany; Miyazawa, Flavio Keidi; Nogueira, Loana Tito; Protti, Fábio; Wakabayashi, Yoshiko;
Venezuela Arratia, Argimiro;

Middle East

USA & Canada

Canada Chan, Timothy; Edmonds, Jeff; Flocchini, Paola; Hell, Pavol; Kranakis, Evangelos; Molloy, Mike; Pelc, Andrzej; Santoro, Nicola; Sawchuk, Cindy; Steinberg, Benjamin; Van Bussel, Frank; Wormald, Nicholas;
USA Üngör, Alper; Achlioptas, Dimitris; Badoiu, Mihai; Bansal, Nikhil; Bespamyatnikh, Sergei; Borgs, Christian; Boros, Endre; Brönnimann, Hervé; Chayes, Jennifer; Cormode, Graham; Dai, Ho-Kwok; Demaine, Erik D.; Eidenbenz, Stephan; Elbassioni, Khaled; Elson, Jeremy; Ergun, Funda; Fürer, Martin; Feder, Tomás; Flaxman, Abraham; Gamarnik, David; Gubbala, Prabhakar; Gurvich, Vladimir; Hajiaghayi, Mohammad Taghi; Hemaspaandra, Lane; Jothi, Raja; Karp, Richard; Khachiyan, Leonid; Krizanc, Danny; Lee, James R.; Lipton, Richard J.; Markakis, Evangelos; Mendel, Manor; Moore, Cristopher; Muthukrishnan, S.; Naor, Assaf; Newman, Alantha; Ogihara, Mitsunori; Ortiz, Carlos; Papadimitriou, Christos; Pittel, Boris; Pruhs, Kirk; Raghavachari, Balaji; Rhodes, John; Ruhl, Matthias; Sahinalp, Cenk; Seroussi, Gadiel; Shenker, Scott; Sorkin, Gregory; Thakur, Mayur; Yang, Ke; Zaki, Mohammed; Zhang, X. W.; Zimand, Marius;


[Top] [Home] [All LATIN Statistics]