_____
 ____  __
  ______     _______
    ____________________
           _______________
          _________________
          ________________
           ______________
            ____________
            __________
            ________
            _______
            _____
            _____
            ___
            ___
            ___


  Chair


Martín 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. São Paulo), 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 S. 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 \(\ell_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


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%)0.75(1.3%)Singapore
3.0(2.1%)1.00(1.7%)Italy
3.0(2.1%)1.50(2.5%)Netherlands
2.0(1.4%)0.58(1.0%)Japan
2.0(1.4%)0.67(1.1%)Finland
2.0(1.4%)0.75(1.3%)Norway
2.0(1.4%)1.00(1.7%)Australia
2.0(1.4%)1.50(2.5%)Switzerland
2.0(1.4%)0.67(1.1%)Czech Republic
2.0(1.4%)1.00(1.7%)Belgium
1.0(0.7%)0.50(0.8%)Denmark
1.0(0.7%)1.00(1.7%)Slovakia
0.5(0.3%)0.12(0.2%)Poland
0.5(0.3%)0.25(0.4%)Venezuela

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.40(49.8%)USA & Canada
53.5(36.6%)22.75(38.6%)Europe
13.5(9.2%)4.52(7.7%)Latin-America
7.0(4.8%)2.33(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;
Singapore Jansson, Jesper; Ng, Joseph H.-K.; Sung, Wing-Kin;
Japan Akiyama, Shigeki; Sadakane, Kunihiko;

Europe

Italy Caminiti, Saverio; Finocchi, Irene; Petreschi, Rossella;
UK Crochemore, Maxime; Gasieniec, Leszek; Iliopoulos, Costas S.; Mohamed, Manal; Schwinghammer, Jan;
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;
Switzerland Cieliebak, Mark;
Slovakia Guller, Dusan;
Germany Bodirsky, Manuel; Diekert, Volker; Gärtner, Tobias; Gurski, Frank; Kowalski, Dariusz R.; Mertens, Stephan; Spakowski, Holger; von Oertzen, Timo; von zur Gathen, Joachim; Wanke, Egon;
Belgium Cardinal, Jean; Langerman, Stefan;
Poland Kowalski, Dariusz R.;
Czech Republic Loebl, Martin; Matousek, Jirí;
Denmark Kohrt, Jens S.;
Netherlands Tveretina, Olga; Woeginger, Gerhard; Zantema, Hans;
Norway Fomin, Fedor; Schaathun, Hans Georg;
Finland Fredriksson, Kimmo; Mäkinen, Veli;
Spain Arratia, Argimiro; Díaz, Josep; Serna, Maria; Thilikos, Dimitrios M.;

Latin-America

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

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 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; Feder, Tomás; Flaxman, Abraham; Fürer, Martin; Gamarnik, David; Gubbala, Prabhakar; Gurvich, Vladimir; Hajiaghayi, Mohammad Taghi; Hemaspaandra, Edith; 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; Üngör, Alper; Yang, Ke; Zaki, Mohammed; Zhang, X. W.; Zimand, Marius;

[Top] [Home] [All LATIN Statistics]