LATIN 2010


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


Chair
Alejandro López-Ortiz, University of Waterloo, Canada.

[Top] [Home] [All LATIN Chairs]

Program Committee
Amihood Amir, Bar-Ilan, Israel.
Diego Arroyuelo, Yahoo Research Latin America, Chile.
Ricardo Baeza-Yates, Yahoo Research, Spain.
Joan Boyar, U. Southern Denmark, Denmark.
Gerth Brodal, Aarhus, Denmark.
Edgar Chávez, U. Michoacan, Mexico.
José Correa, U. Adolfo Ibáñez , Chile.
Irit Dinur, Weizmann Institute, Israel.
Stephane Durocher, Manitoba, Canada.
Faith Ellen, Toronto, Canada.
Leah Epstein, Haifa, Israel.
Cristina G. Fernandes, U. de São Paulo, Brazil.
Paolo Ferragina, Pisa, Italy.
Martin Fürer, Penn State, USA.
Mike Langston, University of Tennessee, USA.
Kazuo Iwama, Kyoto, Japan.
Valerie King, Victoria, Canada.
Ravi Kumar, Yahoo Research, USA.
Moshe Lewenstein, Bar-Ilan, Israel.
Alejandro López-Ortiz (Chair), U. of Waterloo, Canada.
Jesús De Loera, UC Davis, USA.
Kazuhisa Makino, Tokyo, Japan.
Dániel Marx, Budapest, Hungary.
Kurt Mehlhorn, Max Planck Institute for Informatics, Germany.
Julián Mestre, Max Planck Institute for Informatics, Germany.
Michael Mitzenmacher, Harvard, USA.
Ian Munro, U. of Waterloo, Canada.
S. Muthukrishnan, Google and Rutgers U., USA.
Konstantinos Panagiotou, Max Planck Institute for Informatics, Germany.
Mike Paterson, Warwick, UK.
J. Ramírez Alfonsín, Pierre et Marie Curie, Paris 6, France.
Ivan Rapaport, U. Chile, Chile.
Günter Rote, Free U. Berlin, Germany.
Gelasio Salazar, San Luis Potosi, Mexico.
Hadas Shachnai, Technion, Israel.
Igor Shparlinski, Macquarie U., Australia.
Wojciech Szpankowski, Purdue, USA.
Subash Suri, UCSB, USA.
Alfredo Viola, U. Republica, Uruguay.
John Watrous, U. of Waterloo, Canada.
Renato Werneck, Microsoft Research, USA.
Gerhard Woeginger, T.U. Eindhoven, Netherlands.
Norbert Zeh, Dalhousie, Canada.

[Top] [Home] [All LATIN PCs]

Organizing Committee
Dante Arias Torres, UABJO, Oaxaca de Juárez, México.
Francisco Claude, University of Waterloo, Canada.
Jorge Cruz Pérez, UABJO, Oaxaca de Juárez, México.
Reza Dorrigiv (Webmaster), UABJO, Oaxaca de Juárez, México.
Robert Fraser (Publicity Chair), University of Waterloo, Canada.
Erick Israel Guerra Pérez, UABJO, Oaxaca de Juárez, México.
Jazmin Romero, University of Waterloo, Canada.
Lesvia Ruiz, University of Waterloo, Canada.
Alejandro Salinger, University of Waterloo, Canada.

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

Invited Speakers
Piotr Indyk, (Massachusetts Institute of Technology, USA), Sparse Recovery Using Sparse Random Matrices.
Cristopher Moore, (University of New Mexico and Santa Fe Institute, USA), Continuous and Discrete Methods in Computer Science.
Sergio Rajsbaum, (Universidad Nacional Autónoma de México, Mexico), Iterated Shared Memory Models.
Leslie Valiant, (Harvard University, USA), Some Observations on Holographic Algorithms.
Ricardo Baeza-Yates, John Brzozowski, Volker Diekert, and Jacques Sakarovitch, (Yahoo Research (Spain), University of Waterloo (Canada), Universität Stuttgart (Germany), and Ecole Nationale Supérieure des Télécommunications (France)), Vignettes on the work of Imre Simon.

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

Papers
Cristopher Moore, Continuous and Discrete Methods in Computer Science. [Bibtex]

Greg Aloupis, Jean Cardinal, Sébastien Collette, Shinji Imahori, Matias Korman, Stefan Langerman, Oded Schwartz, Shakhar Smorodinsky and Perouz Taslakian, Colorful Strips. [Bibtex]

Jonathan Backer and J. Mark Keil, The Mono- and Bichromatic Empty Rectangle and Square Problems in All Dimensions. [Bibtex]

Qianping Gu and Navid Imani, Connectivity Is Not a Limit for Kernelization: Planar Connected Dominating Set. [Bibtex]

Eric Angel, Evripidis Bampis and Nicolas Thibault, Randomized Truthful Algorithms for Scheduling Selfish Tasks on Parallel Machines. [Bibtex]

Martin Fürer, Almost Linear Time Computation of the Chromatic Polynomial of a Graph of Bounded Tree-Width. [Bibtex]

Nadja Betzler, Jiong Guo, Christian Komusiewicz and Rolf Niedermeier, Average Parameterization and Partial Kernelization for Computing Medians. [Bibtex]

Fedor V. Fomin, Daniel Lokshtanov, Fabrizio Grandoni and Saket Saurabh, Sharp Separation and Applications to Exact and Parameterized Algorithms. [Bibtex]

Tsunehiko Kameda, Ichiro Suzuki and John Z. Zhang, Finding the Minimum-Distance Schedule for a Boundary Searcher with a Flashlight. [Bibtex]

Salvatore La Torre, Parthasarathy Madhusudan and Gennaro Parlato, The Language Theory of Bounded Context-Switching. [Bibtex]

Diego Recalde, Cyriel Rutten, Petra Schuurman and Tjark Vredeveld, Local Search Performance Guarantees for Restricted Related Parallel Machine Scheduling. [Bibtex]

Britta Peis, Martin Skutella and Andreas Wiese, Packet Routing on the Grid. [Bibtex]

Michael D. Coury, Pavol Hell, Jan Kratochvíl and Tomás Vyskocil, Faithful Representations of Graphs by Islands in the Extended Grid. [Bibtex]

Gero Greiner and Riko Jacob, The I/O Complexity of Sparse Matrix Dense Matrix Multiplication. [Bibtex]

Piotr Indyk, Sparse Recovery Using Sparse Random Matrices. [Bibtex]

Johannes Fischer, Optimal Succinctness for Range Minimum Queries. [Bibtex]

Jérémy Barbay, Francisco Claude and Gonzalo Navarro, Compact Rich-Functional Binary Relation Representations. [Bibtex]

Sylvain Lombardy and Jacques Sakarovitch, Radix Cross-Sections for Length Morphisms. [Bibtex]

Viliam Geffert and Giovanni Pighizzini, Pairs of Complementary Unary Languages with "Balanced" Nondeterministic Automata. [Bibtex]

Janusz A. Brzozowski, Galina Jirásková and Baiyu Li, Quotient Complexity of Ideal Languages. [Bibtex]

Frédérique Bassino, Laura Giambruno and Cyril Nicaud, Complexity of Operations on Cofinite Languages. [Bibtex]

Hagai Cohen and Ely Porat, Fast Set Intersection and Two-Patterns Matching. [Bibtex]

Joachim von zur Gathen, Alfredo Viola and Konstantin Ziegler, Counting Reducible, Powerful, and Relatively Irreducible Multivariate Polynomials over Finite Fields. [Bibtex]

Beate Bollig, A Larger Lower Bound on the OBDD Complexity of the Most Significant Bit of Multiplication. [Bibtex]

Manfred G. Madritsch and Brigitte Vallée, Modelling the LLL Algorithm by Sandpiles. [Bibtex]

Prosenjit Bose, Paz Carmi, Michiel H. M. Smid and Daming Xu, Communication-Efficient Construction of the Plane Localized Delaunay Graph. [Bibtex]

Dominik Gall, Riko Jacob, Andréa W. Richa, Christian Scheideler, Stefan Schmid and Hanjo Täubig, Time Complexity of Distributed Topological Self-stabilization: The Case of Graph Linearization. [Bibtex]

Petra Berenbrink, Robert Elsässer and Thomas Sauerwald, Randomised Broadcasting: Memory vs. Randomness. [Bibtex]

Vonjy Rasendrahasina and Vlady Ravelomanana, Limit Theorems for Random MAX-2-XORSAT. [Bibtex]

Per Austrin, Siavosh Benabbas and Avner Magen, On Quadratic Threshold CSPs. [Bibtex]

Carles Padró and Leonor Vázquez, Finding Lower Bounds on the Complexity of Secret Sharing Schemes by Linear Programming. [Bibtex]

Elizabeth Maltais and Lucia Moura, Finding the Best CAFE Is NP-Hard. [Bibtex]

Anna Gál and Jing-Tang Jang, The Size and Depth of Layered Boolean Circuits. [Bibtex]

Pankaj K. Agarwal, Jeff M. Phillips and Bardia Sadri, Lipschitz Unimodal and Isotonic Regression on Paths and Trees. [Bibtex]

Daniel Panario, Brett Stevens and Qiang Wang, Ambiguity and Deficiency in Costas Arrays and APN Permutations. [Bibtex]

Sergio Rajsbaum, Iterated Shared Memory Models. [Bibtex]

Emden R. Gansner, Yifan Hu, Michael Kaufmann and Stephen G. Kobourov, Optimal Polygonal Representation of Planar Graphs. [Bibtex]

Adrian Dumitrescu and Minghui Jiang, Minimum-Perimeter Intersecting Polygons. [Bibtex]

Qi Cheng and Yu-Hsin Li, Finding the Smallest Gap between Sums of Square Roots. [Bibtex]

Greg Aloupis, Jean Cardinal, Sébastien Collette, Erik D. Demaine, Martin L. Demaine, Muriel Dulieu, Ruy Fabila Monroy, Vi Hart, Ferran Hurtado, Stefan Langerman, Maria Saumell, Carlos Seara and Perouz Taslakian, Matching Points with Things. [Bibtex]

Bettina Speckmann and Kevin Verbeek, Homotopic Rectilinear Routing with Few Links and Thick Edges. [Bibtex]

Alexis Ballier, Bruno Durand and Emmanuel Jeandel, Tilings Robust to Errors. [Bibtex]

Steven Bitner, Yam Ki Cheung, Atlas F. Cook, Ovidiu Daescu, Anastasia Kurdia and Carola Wenk, Visiting a Sequence of Points with a Bevel-Tip Needle. [Bibtex]

MohammadHossein Bateni and MohammadTaghi Hajiaghayi, Euclidean Prize-Collecting Steiner Forest. [Bibtex]

MohammadTaghi Hajiaghayi and Arefeh A. Nasri, Prize-Collecting Steiner Networks via Iterative Rounding. [Bibtex]

René van Bevern, Hannes Moser and Rolf Niedermeier, Kernelization through Tidying. [Bibtex]

Mark van Hoeij and Andrew Novocin, Gradual Sub-lattice Reduction and a New Complexity for Factoring Polynomials. [Bibtex]

Christine Chung, Katrina Ligett, Kirk Pruhs and Aaron Roth, The Power of Fair Pricing Mechanisms. [Bibtex]

Vahab S. Mirrokni, S. Muthukrishnan and Uri Nadav, Quasi-Proportional Mechanisms: Prior-Free Revenue Maximization. [Bibtex]

Leslie G. Valiant, Some Observations on Holographic Algorithms. [Bibtex]

Jaroslaw Byrka, Andreas Karrenbauer and Laura Sanità, The Interval Constrained 3-Coloring Problem. [Bibtex]

Paul S. Bonsma and Felix Breuer, Counting Hexagonal Patches and Independent Sets in Circle Graphs. [Bibtex]

Yuichi Asahiro, Eiji Miyano and Kazuaki Samizo, Approximating Maximum Diameter-Bounded Subgraphs. [Bibtex]

Kunal Dutta and C. R. Subramanian, Largest Induced Acyclic Tournament in Random Digraphs: A 2-Point Concentration. [Bibtex]

Qi Ge and Daniel Stefankovic, The Complexity of Counting Eulerian Tours in 4-Regular Graphs. [Bibtex]

Andreas Brandstädt, Christian Hundt and Ragnar Nevries, Efficient Edge Domination on Hole-Free Graphs in Polynomial Time. [Bibtex]

Marek Karpinski, Andrzej Rucinski and Edyta Szymanska, Computational Complexity of the Hamiltonian Cycle Problem in Dense Hypergraphs. [Bibtex]

Amalia Duch, Rosa M. Jiménez and Conrado Martínez, Rank Selection in Multidimensional Data. [Bibtex]

Prosenjit Bose, Karim Douïeb, Vida Dujmovic and John Howat, Layered Working-Set Trees. [Bibtex]

Paolo Ferragina, Travis Gagie and Giovanni Manzini, Lightweight Data Indexing and Compression in External Memory. [Bibtex]



[Top] [Home] [All LATIN Papers]

Sponsors
Yahoo! Research
Microsoft Research
Honorable Ayuntamiento Oaxaca de Juárez, Mexico
Universidad Autónoma "Benito Juárez" de Oaxaca
University of Waterloo

[Top] [Home] [All LATIN Sponsors]

Location

Conference Site

LATIN 2010 took place in Oaxaca, Mexico. Oaxaca is a city located in a valley surrounded by mountains, 500 km south of Mexico City. Not far lay the beautiful beaches of Huatulco and the southern Mexican tropical rain forest. The surrounding mountainous terrain gave raise to a variety of indigenous cultures with their own language and tradition, with the Mixtec and Zapotec culture being the better known. It has a very pleasant climate, characteristic of high altitude tropical sites. The historical center of Oaxaca has been declared by UNESCO to be a "World Heritage Site" because of its colonial architecture. In the surrounding area there are a large number of archaeological sites.

A few blocks north of the zócalo is the magnificent 16th-century monastery and church of Santo Domingo. It is without a doubt one of Mexico's most ornately decorated churches. The austerity of the fa├žade contrasts with the exuberant Baroque of its interior.

There are numerous attractions in the surrounding areas. No trip to Oaxaca is complete without a visit to Monte Albán, one of Mexico's great treasures. Built on a hilltop flattened by the Zapotec Indians over 2,500 years ago, Monte Alban was once a holy city of more than 25,000 inhabitants. The expansive ruins consist of a great central plaza surrounded by buildings, temples, an observatory, ball court and burial tombs. Magnificent stone carvings on vertical stone slabs date to 700b.c. The view from Monte Alban of Oaxaca Valley is spectacular, and the site is appealing to non-archaeological buffs as well.


[Top] [Home] [All LATIN Locations]

Photos

[Top] [Home] [All LATIN Photos]

Statistics
General:
No. of submissions 155
No. of accepted papers 56
% of accepted papers 36.1%
Total No. of authors 172
Avg. No. of authors per paper 3.07
No. of countries represented 20
 
No. of papers according to how many authors work in Latin-America
    At least one 5(8.9%)
    All 0(0.0%)


Statistics by Country of Author's Affiliation

Authors*Papers**

40.5(23.5%)13.56(24.2%)USA
29.0(16.9%)10.19(18.2%)Germany
27.0(15.7%)9.25(16.5%)Canada
16.0(9.3%)6.50(11.6%)France
10.0(5.8%)0.94(1.7%)Belgium
8.0(4.7%)2.23(4.0%)Spain
6.5(3.8%)2.25(4.0%)Italy
5.0(2.9%)1.75(3.1%)Netherlands
5.0(2.9%)1.22(2.2%)Japan
5.0(2.9%)1.69(3.0%)Israel
3.0(1.7%)1.00(1.8%)Switzerland
3.0(1.7%)1.00(1.8%)Chile
3.0(1.7%)1.25(2.2%)India
2.0(1.2%)0.50(0.9%)Norway
2.0(1.2%)0.83(1.5%)Slovakia
2.0(1.2%)0.67(1.2%)Poland
2.0(1.2%)0.50(0.9%)Czech Republic
1.0(0.6%)0.33(0.6%)Uruguay
1.0(0.6%)0.08(0.1%)Mexico
1.0(0.6%)0.25(0.4%)Ecuador

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**

85.5(49.7%)27.4(48.9%)Europe
67.5(39.2%)22.8(40.7%)USA & Canada
8.0(4.7%)2.5(4.4%)Australia & Asia
6.0(3.5%)1.7(3.0%)Latin-America
5.0(2.9%)1.7(3.0%)Middle East

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


Africa

Australia & Asia

Japan Asahiro, Yuichi; Imahori, Shinji; Korman, Matias; Miyano, Eiji; Samizo, Kazuaki;
India Dutta, Kunal; Saurabh, Saket; Subramanian, C. R.;

China

Europe

Italy Ferragina, Paolo; Giambruno, Laura; Grandoni, Fabrizio; La Torre, Salvatore; Manzini, Giovanni; Parlato, Gennaro; Pighizzini, Giovanni;
Germany Betzler, Nadja; Bollig, Beate; Bonsma, Paul S.; Brandstädt, Andreas; Breuer, Felix; Elsässer, Robert; Fischer, Johannes; Gall, Dominik; Greiner, Gero; Guo, Jiong; Hundt, Christian; Jacob, Riko; Karpinski, Marek; Kaufmann, Michael; Komusiewicz, Christian; Moser, Hannes; Nevries, Ragnar; Niedermeier, Rolf; Peis, Britta; Scheideler, Christian; Schmid, Stefan; Schwartz, Oded; Skutella, Martin; Täubig, Hanjo; Wiese, Andreas; van Bevern, René; von zur Gathen, Joachim;
Belgium Aloupis, Greg; Cardinal, Jean; Collette, Sébastien; Langerman, Stefan; Taslakian, Perouz;
Switzerland Byrka, Jaroslaw; Karrenbauer, Andreas; Sanità, Laura;
Norway Fomin, Fedor V.; Lokshtanov, Daniel;
Netherlands Rutten, Cyriel; Schuurman, Petra; Speckmann, Bettina; Verbeek, Kevin; Vredeveld, Tjark;
France Angel, Eric; Ballier, Alexis; Bampis, Evripidis; Bassino, Frédérique; Durand, Bruno; Jeandel, Emmanuel; Lombardy, Sylvain; Madritsch, Manfred G.; Nicaud, Cyril; Novocin, Andrew; Rasendrahasina, Vonjy; Ravelomanana, Vlady; Sakarovitch, Jacques; Thibault, Nicolas; Vallée, Brigitte; Ziegler, Konstantin;
Slovakia Geffert, Viliam; Jirásková, Galina;
Poland Rucinski, Andrzej; Szymanska, Edyta;
Spain Duch, Amalia; Hurtado, Ferran; Jiménez, Rosa M.; Martínez, Conrado; Padró, Carles; Saumell, Maria; Seara, Carlos; Vázquez, Leonor;
Czech Republic Kratochvíl, Jan; Vyskocil, Tomás;

Latin-America

Uruguay Viola, Alfredo;
Mexico Fabila Monroy, Ruy;
Chile Barbay, Jérémy; Gagie, Travis; Navarro, Gonzalo;
Ecuador Recalde, Diego;

Middle East

Israel Carmi, Paz; Cohen, Hagai; Nadav, Uri; Porat, Ely; Smorodinsky, Shakhar;

USA & Canada

Canada Backer, Jonathan; Benabbas, Siavosh; Berenbrink, Petra; Bose, Prosenjit; Brzozowski, Janusz A.; Claude, Francisco; Coury, Michael D.; Douïeb, Karim; Dujmovic, Vida; Gu, Qianping; Hell, Pavol; Howat, John; Imani, Navid; Kameda, Tsunehiko; Li, Baiyu; Magen, Avner; Maltais, Elizabeth; Mark Keil, J.; Moura, Lucia; Panario, Daniel; Sadri, Bardia; Smid, Michiel H. M.; Stevens, Brett; Wang, Qiang; Xu, Daming; Zhang, John Z.;
USA Agarwal, Pankaj K.; Austrin, Per; Bateni, MohammadHossein; Bitner, Steven; Cheng, Qi; Cheung, Yam Ki; Chung, Christine; Cook, Atlas F.; Daescu, Ovidiu; Demaine, Martin L.; Dulieu, Muriel; Dumitrescu, Adrian; Fürer, Martin; Gál, Anna; Gansner, Emden R.; Ge, Qi; Hajiaghayi, MohammadTaghi; Hart, Vi; Hu, Yifan; Jang, Jing-Tang; Jiang, Minghui; Kobourov, Stephen G.; Kurdia, Anastasia; Li, Yu-Hsin; Ligett, Katrina; Madhusudan, Parthasarathy; Mirrokni, Vahab S.; Muthukrishnan, S.; Nasri, Arefeh A.; Parlato, Gennaro; Phillips, Jeff M.; Pruhs, Kirk; Richa, Andréa W.; Roth, Aaron; Sauerwald, Thomas; Stefankovic, Daniel; Suzuki, Ichiro; Wenk, Carola; van Hoeij, Mark;


[Top] [Home] [All LATIN Statistics]