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
|
|
|
[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%) |
* Authors with n affiliations contributes 1/n to each affiliation.
** Papers with n authors contribute 1/n to each affiliation.
* Authors with n affiliations contributes 1/n to each affiliation.
** Papers with n authors contribute 1/n to each affiliation.
Africa
Australia & Asia
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]
|
|