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


  Chair


David Fernández-Baca, Iowa State University, USA.

[Top] [Home] [All LATIN Chairs]

  Program Committee


Ricardo Baeza-Yates, Yahoo Research, Spain.
Nikhil Bansal, IBM, USA.
Jérémy Barbay, U. Chile, Chile.
Michael Bender, Stony Brook U., USA.
José Correa, U. Chile, Chile.
Pilu Crescenzi, U. Firenze, Italy.
Martín Farach-Colton, Rutgers U., USA.
Cristina G. Fernandes, U. de São Paulo, Brazil.
David Fernández-Baca (Chair), Iowa State U., USA.
Guilherme Fonseca, Unirio, Brazil.
Joachim von zur Gathen, U. Bonn, Germany.
Johannes Koebler, Humboldt U., Germany.
Yoshiharu Kohayakawa, U. de São Paulo, Brazil.
S. Rao Kosaraju, Johns Hopkins U., USA.
Ravi Kumar, Yahoo Research, USA.
Giovanni Manzini, U. Piemonte Orientale, Italy.
Alberto Marchetti-Spaccamela, U. Roma, Italy.
Conrado Martínez, UPC Barcelona, Spain.
Elvira Mayordomo, U. Zaragoza, Spain.
Lucia Moura, U. Ottawa, Canada.
J. Ian Munro, U. Waterloo, Canada.
Arlindo Oliveira, U. Técnica Lisboa, Portugal.
Luis Rademacher, Ohio State U., USA.
Ivan Rapaport, U. Chile, Chile.
Andrea Richa, Arizona State U., USA.
Jacques Sakarovitch, ENST, France.
Gelasio Salazar, U. San Luis Potosí, Mexico.
Nicholas Schabanel, LIAFA U. Paris, France.
R. I. Silveira, UPC Barcelona, Spain.
Mona Singh, Princeton U., USA.
Martin Strauss, U. Michigan, USA.
Wojciech Szpankowski, Purdue U., USA.
Jorge Urrutia, UNAM, Mexico.
E. Vigoda, Georgia Tech, USA.
Alfredo Viola, U. de la República, Uruguay.

[Top] [Home] [All LATIN PCs]

  Organizing Committee


A. Cuadros-Vargas, Universidad Católica San Pablo, Peru.
E. Cuadros-Vargas (Chair), Universidad Católica San Pablo, Peru.
M. P. Rondón R., Universidad Católica San Pablo, Peru.
R. Ticona H., Universidad Católica San Pablo, Peru.
Y. Túpac V., Universidad Católica San Pablo, Peru.

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

  Invited Speakers


Martin Davis, (Courant Institute, NYU, USA), Universality is Ubiquitous.
Scott Aaronson, (Massachusetts Institute of Technology, USA), Turing Year Lecture.
Kirk Pruhs, (University of Pittsburgh, USA), Green Computing Algorithmics: Managing Power Heterogeneity.
Marcos Kiwi, (Universidad de Chile, Chile), Combinatorial and Algorithmic Problems Involving (Semi-)Random Sequences.

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

  Papers


Hee-Kap Ahn, Sang Won Bae, Otfried Cheong, Joachim Gudmundsson, Takeshi Tokuyama and Antoine Vigneron, A Generalization of the Convex Kakeya Problem. [Bibtex]

Eric Angel, Evripidis Bampis and Vincent Chau, Low Complexity Scheduling Algorithm Minimizing the Energy for Tasks with Agreeable Deadlines. [Bibtex]

Esther M. Arkin, José Miguel Díaz-Báñez, Ferran Hurtado, Piyush Kumar, Joseph S. B. Mitchell, Belén Palop, Pablo Pérez-Lantero, Maria Saumell and Rodrigo I. Silveira, Bichromatic 2-Center of Pairs of Points. [Bibtex]

Vikraman Arvind, Partha Mukhopadhyay and Prajakta Nimbhorkar, Erd\H{o}s-Rényi Sequences and Deterministic Construction of Expanding Cayley Graphs. [Bibtex]

Rafael da Ponte Barbosa and Yoshiko Wakabayashi, A Better Approximation Ratio and an IP Formulation for a Sensor Cover Problem. [Bibtex]

Hans-Joachim Böckenhauer, Dennis Komm, Richard Královic and Peter Rossmanith, On the Advice Complexity of the Knapsack Problem. [Bibtex]

Nicolas Boria, Jérôme Monnot and Vangelis Th. Paschos, Reoptimization of Some Maximum Weight Induced Hereditary Subgraph Problems. [Bibtex]

Prosenjit Bose, Rolf Fagerberg, André van Renssen and Sander Verdonschot, On Plane Constrained Bounded-Degree Spanners. [Bibtex]

Joshua Brody, Hongyu Liang and Xiaoming Sun, Space-Efficient Approximation Scheme for Circular Earth Mover Distance. [Bibtex]

Ana Busic, Nazim Fatès, Jean Mairesse and Irene Marcovici, Density Classification on Infinite Lattices and Trees. [Bibtex]

Jean Cardinal and Matias Korman, Coloring Planar Homothets and Three-Dimensional Hypergraphs. [Bibtex]

Armando Castañeda, Maurice Herlihy and Sergio Rajsbaum, An Equivariance Theorem with Applications to Renaming. [Bibtex]

Armando Castañeda, Damien Imbs, Sergio Rajsbaum and Michel Raynal, Renaming Is Weaker Than Set Agreement But for Perfect Renaming: A Map of Sub-consensus Tasks. [Bibtex]

Eda Cesaratto and Brigitte Vallée, Pseudorandomness of a Random Kronecker Sequence. [Bibtex]

Richard Cole and Vijaya Ramachandran, Revisiting the Cache Miss Analysis of Multithreaded Algorithms. [Bibtex]

Robert Crowston, Gregory Gutin, Mark Jones, Venkatesh Raman and Saket Saurabh, Parameterized Complexity of MaxSat above Average. [Bibtex]

Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk and Jakub Onufry Wojtaszczyk, Solving the 2-Disjoint Connected Subgraphs Problem Faster Than $2^n$. [Bibtex]

Daniel Dadush, A $O(1/\epsilon^2)^n$-Time Sieving Algorithm for Approximate Integer Programming. [Bibtex]

Pooya Davoodi, Michiel H. M. Smid and Freek van Walderveen, Two-Dimensional Range Diameter Queries. [Bibtex]

Domingos Dellamonica Jr., Yoshiharu Kohayakawa, Vojtech Rödl and Andrzej Rucinski, An Improved Upper Bound on the Density of Universal Random Graphs. [Bibtex]

Volker Diekert, Jonathan Kausch and Markus Lohrey, Logspace Computations in Graph Groups and Coxeter Groups. [Bibtex]

Stefan Dobrev, Evangelos Kranakis, Danny Krizanc, Oscar Morales Ponce and Ladislav Stacho, Approximating the Edge Length of 2-Edge Connected Planar Geometric Graphs on a Set of Points. [Bibtex]

Mitre Costa Dourado, Dieter Rautenbach, Vinícius Fernandes dos Santos, Philipp Matthias Schäfer, Jayme Luiz Szwarcfiter and Alexandre Toma, On the Radon Number for $P_3$-Convexity. [Bibtex]

Tinaz Ekim, Aysel Erey, Pinar Heggernes, Pim van 't Hof and Daniel Meister, Computing Minimum Geodetic Sets of Proper Interval Graphs. [Bibtex]

Zoltán Ésik and Szabolcs Iván, Hausdorff Rank of Scattered Context-Free Linear Orders. [Bibtex]

Martin Farach-Colton, Antonio Fernández Anta, Alessia Milani, Miguel A. Mosteiro and Shmuel Zaks, . [Bibtex]

MohammadAmin Fazli, Mohammad Ghodsi, Jafar Habibi, Pooya Jalaly Khalilabadi, Vahab S. Mirrokni and Sina Sadeghian Sadeghabad, On the Non-progressive Spread of Influence through Social Networks. [Bibtex]

Johannes Fischer, Travis Gagie, Tsvi Kopelowitz, Moshe Lewenstein, Veli Mäkinen, Leena Salmela and Niko Välimäki, Forbidden Patterns. [Bibtex]

Krzysztof Fleszar, Christian Glaßer, Fabian Lipp, Christian Reitwießner and Maximilian Witek, Structural Complexity of Multiobjective NP Search Problems. [Bibtex]

Fedor V. Fomin, Serge Gaspers, Petr A. Golovach, Karol Suchan, Stefan Szeider, Erik Jan van Leeuwen, Martin Vatshelle and Yngve Villanger, $k$-Gap Interval Graphs. [Bibtex]

Pierre Fraigniaud and Andrzej Pelc, Decidability Classes for Mobile Agents Computing. [Bibtex]

Bin Fu, NE Is Not NP Turing Reducible to Nonexponentially Dense NP Sets. [Bibtex]

Martin Fürer, Efficient Arbitrary and Resolution Proofs of Unsatisfiability for Restricted Tree-Width. [Bibtex]

Travis Gagie, Kalle Karhu, Juha Kärkkäinen, Veli Mäkinen, Leena Salmela and Jorma Tarhio, Indexed Multi-pattern Matching. [Bibtex]

Archontia C. Giannopoulou, Sudeshna Kolay and Saket Saurabh, New Lower Bound on Max Cut of Hypergraphs with an Application to $r$-Set Splitting. [Bibtex]

Ragavendran Gopalakrishnan, Dimitrios Kanoulas, Naga Naresh Karuturi, C. Pandu Rangan, Rajmohan Rajaraman and Ravi Sundaram, Cache Me If You Can: Capacitated Selfish Replication Games. [Bibtex]

Gero Greiner and Riko Jacob, The Efficiency of MapReduce in Parallel External Memory. [Bibtex]

Michel Habib, Antoine Mamcarz and Fabien de Montgolfier, Algorithms for Some $H$-Join Decompositions. [Bibtex]

Daniel Heldt, Kolja B. Knauer and Torsten Ueckerdt, On the Bend-Number of Planar and Outerplanar Graphs. [Bibtex]

Ahmed Helmi, Conrado Martínez and Alois Panholzer, Hiring above the $m$-th Best Candidate: A Generalization of Records in Permutations. [Bibtex]

Wiebke Höhn and Tobias Jacobs, On the Performance of Smith's Rule in Single-Machine Scheduling with Nonlinear Cost. [Bibtex]

Rohit Khandekar, Guy Kortsarz and Vahab S. Mirrokni, Advantage of Overlapping Clusters for Minimizing Conductance. [Bibtex]

Toryn Qwyllyn Klassen and Philipp Woelfel, Independence of Tabulation-Based Hash Classes. [Bibtex]

Martin Kutrib, Andreas Malcher and Giovanni Pighizzini, Oblivious Two-Way Finite Automata: Decidability and Complexity. [Bibtex]

Hélio B. Macêdo Filho, Raphael C. S. Machado and Celina M. Herrera de Figueiredo, Clique-Colouring and Biclique-Colouring Unichord-Free Graphs. [Bibtex]

Bernard Mans and Igor Shparlinski, Random Walks and Bisections in Random Circulant Graphs. [Bibtex]

Monaldo Mastrolilli, The Feedback Arc Set Problem with Triangle Inequality Is a Vertex Cover Problem. [Bibtex]

Basile Morcrette, Fully Analyzing an Algebraic Pólya Urn Model. [Bibtex]

Zeev Nutov, Degree-Constrained Node-Connectivity. [Bibtex]

Zeev Nutov, Survivable Network Activation Problems. [Bibtex]

Jiawei Qian, Frans Schalekamp, David P. Williamson and Anke van Zuylen, On the Integrality Gap of the Subtour LP for the 1,2-TSP. [Bibtex]

Hadas Shachnai, Gal Tamir and Tami Tamir, A Theory and Algorithms for Combinatorial Reoptimization. [Bibtex]

Amir Shpilka, Capacity Achieving Two-Write WOM Codes. [Bibtex]

Xiaoming Sun, Chengu Wang and Wei Yu, The Relationship between Inner Product and Counting Cycles. [Bibtex]

Linqing Tang and Peng Zhang, Approximating Minimum Label $s$-$t$ Cut via Linear Programming. [Bibtex]



[Top] [Home] [All LATIN Papers]

  Sponsors


Yahoo! Labs
Microsoft Research

[Top] [Home] [All LATIN Sponsors]

  Location


LATIN 2012 took place in Arequipa, Peru. Arequipa, founded in 1540, is Peru's second largest urban area, with a population of over 1.1 million. The city is located 1,000 kilometers southeast of Peru's capital, Lima, at 2,235 meters above sea level, and is next to three volcanoes: the still-active Misti and the extinct Chachani and Pichu Pichu. The weather is sunny year-round, warm during the day and cool at night. The average temperature from January to May is approximately 15 degrees Celsius, with a high around 20 degrees Celsius.

Arequipa is an important center of Peruvian arts and culture. Its downtown area, with buildings made of white volcanic rock (sillar) blending native and Spanish styles, is a UNESCO World Heritage site. Arequipa's Main Square (Plaza de Armas) is among Peru's most beautiful, with an impressive cathedral and colonial arcaded buildings full of restaurants and cafés.

A notable attraction near the square is the 400-year old Santa Catalina Monastery, which is like a city within the city. The Monastery will be the location of the LATIN 2012 banquet. Not too far from the bustling downtown area, there are quiet neighborhoods where you can take a pleasant stroll. One of these is Yanahuara, with a charming square and excellent view of the city, the mountains, and the surrounding countryside. Another is San Lazaro, with pedestrian streets and winding alleys. San Lazaro is the location of San Pablo Catholic University (UCSP) where LATIN 2012 will be held. The UCSP campus lies along the Chili River and has a clear view of the Misti volcano. All over the city there are excellent restaurants, where you can sample Arequipa's cuisine, which occupies a special place in Peru's world-renowned gastronomy.


[Top] [Home] [All LATIN Locations]

  Photos



[Top] [Home] [All LATIN Photos]

  Statistics


General:
No. of submissions 153
No. of accepted papers 55
% of accepted papers 35.9%
Total No. of authors 185
Avg. No. of authors per paper 3.36
No. of countries represented 31
 
No. of papers according to how many authors work in Latin-America
    At least one 9(16.4%)
    All 2(3.6%)


Statistics by Country of Author's Affiliation

Authors*Papers**

24.5(13.2%)8.25(15.0%)USA
21.0(11.4%)7.28(13.2%)France
20.0(10.8%)5.51(10.0%)Germany
10.5(5.7%)3.04(5.5%)Brazil
10.0(5.4%)3.18(5.8%)Canada
10.0(5.4%)1.57(2.9%)Finland
9.0(4.9%)4.49(8.2%)Israel
9.0(4.9%)2.40(4.4%)India
7.5(4.1%)1.41(2.6%)Spain
7.0(3.8%)1.15(2.1%)Norway
6.0(3.2%)2.75(5.0%)Switzerland
6.0(3.2%)2.33(4.2%)China
5.0(2.7%)0.83(1.5%)Iran
5.0(2.7%)1.58(2.9%)Denmark
4.0(2.2%)0.73(1.3%)UK
4.0(2.2%)0.94(1.7%)Poland
3.0(1.6%)1.17(2.1%)Australia
3.0(1.6%)0.50(0.9%)South Korea
3.0(1.6%)0.58(1.1%)Austria
2.0(1.1%)0.40(0.7%)Turkey
2.0(1.1%)1.00(1.8%)Hungary
2.0(1.1%)1.00(1.8%)Belgium
2.0(1.1%)0.58(1.1%)Mexico
2.0(1.1%)0.44(0.8%)Czech Republic
1.5(0.8%)0.17(0.3%)Chile
1.0(0.5%)0.33(0.6%)Italy
1.0(0.5%)0.17(0.3%)Japan
1.0(0.5%)0.20(0.4%)Slovakia
1.0(0.5%)0.17(0.3%)Saudi Arabia
1.0(0.5%)0.50(0.9%)Argentina
1.0(0.5%)0.33(0.6%)Greece

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

96.5(52.2%)26.82(48.8%)Europe
34.5(18.6%)11.43(20.8%)USA & Canada
22.0(11.9%)6.57(11.9%)Australia & Asia
17.0(9.2%)5.89(10.7%)Middle East
15.0(8.1%)4.30(7.8%)Latin-America

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


Africa

Australia & Asia

Australia Gudmundsson, Joachim; Mans, Bernard; Shparlinski, Igor;
China Liang, Hongyu; Sun, Xiaoming; Tang, Linqing; Wang, Chengu; Zhang, Peng;
Japan Tokuyama, Takeshi;
South Korea Ahn, Hee-Kap; Bae, Sang Won; Cheong, Otfried;
India Arvind, Vikraman; Karuturi, Naga Naresh; Kolay, Sudeshna; Mukhopadhyay, Partha; Nimbhorkar, Prajakta; Raman, Venkatesh; Rangan, C. Pandu; Saurabh, Saket;

Europe

UK Crowston, Robert; Golovach, Petr A.; Gutin, Gregory; Jones, Mark;
Italy Pighizzini, Giovanni;
Germany Diekert, Volker; Fischer, Johannes; Fleszar, Krzysztof; Gla{\ss}er, Christian; Höhn, Wiebke; Heldt, Daniel; Jacobs, Tobias; Kausch, Jonathan; Knauer, Kolja B.; Kutrib, Martin; Lipp, Fabian; Lohrey, Markus; Malcher, Andreas; Meister, Daniel; Rautenbach, Dieter; Reitwie{\ss}ner, Christian; Rossmanith, Peter; Schäfer, Philipp Matthias; Witek, Maximilian; van Zuylen, Anke;
Hungary Ésik, Zoltán; Iván, Szabolcs;
Belgium Cardinal, Jean; Korman, Matias;
Switzerland Böckenhauer, Hans-Joachim; Greiner, Gero; Jacob, Riko; Komm, Dennis; Královic, Richard; Mastrolilli, Monaldo;
Norway Fomin, Fedor V.; Heggernes, Pinar; Pilipczuk, Michal; Vatshelle, Martin; Villanger, Yngve; van 't Hof, Pim; van Leeuwen, Erik Jan;
France Angel, Eric; Bampis, Evripidis; Boria, Nicolas; Busic, Ana; Castañeda, Armando; Chau, Vincent; Fatès, Nazim; Fraigniaud, Pierre; Habib, Michel; Imbs, Damien; Mairesse, Jean; Mamcarz, Antoine; Marcovici, Irene; Milani, Alessia; Monnot, Jér\^ome; Montgolfier, Fabien de; Morcrette, Basile; Paschos, Vangelis Th.; Raynal, Michel; Vallée, Brigitte;
Slovakia Dobrev, Stefan;
Poland Cygan, Marek; Pilipczuk, Marcin; Rucinski, Andrzej; Suchan, Karol; Wojtaszczyk, Jakub Onufry;
Finland Gagie, Travis; Kärkkäinen, Juha; Karhu, Kalle; Mäkinen, Veli; Salmela, Leena; Tarhio, Jorma; Välimäki, Niko;
Austria Gaspers, Serge; Panholzer, Alois; Szeider, Stefan;
Denmark Brody, Joshua; Davoodi, Pooya; Fagerberg, Rolf; Yu, Wei; van Walderveen, Freek;
Spain Díaz-Báñez, José Miguel; Fernández Anta, Antonio; Helmi, Ahmed; Hurtado, Ferran; Martínez, Conrado; Mosteiro, Miguel A.; Palop, Belén; Silveira, Rodrigo I.;
Greece Giannopoulou, Archontia C.;
Czech Republic Saumell, Maria; Ueckerdt, Torsten;

Latin-America

Mexico Rajsbaum, Sergio;
Chile Pérez-Lantero, Pablo; Suchan, Karol;
Brazil Barbosa, Rafael da Ponte; Dellamonica Jr., Domingos; Dourado, Mitre Costa; Kohayakawa, Yoshiharu; Mac\^edo Filho, Hélio B.; Machado, Raphael C. S.; Szwarcfiter, Jayme Luiz; Toma, Alexandre; Wakabayashi, Yoshiko; de Figueiredo, Celina M. Herrera; dos Santos, Vinícius Fernandes;
Argentina Cesaratto, Eda;

Middle East

Turkey Ekim, Tinaz; Erey, Aysel;
Iran Fazli, MohammadAmin; Ghodsi, Mohammad; Habibi, Jafar; Khalilabadi, Pooya Jalaly; Sadeghabad, Sina Sadeghian;
Saudi Arabia Vigneron, Antoine;
Israel Kopelowitz, Tsvi; Lewenstein, Moshe; Nutov, Zeev; Shachnai, Hadas; Shpilka, Amir; Tamir, Tami; Zaks, Shmuel;

USA & Canada

Canada Bose, Prosenjit; Klassen, Toryn Qwyllyn; Kranakis, Evangelos; Pelc, Andrzej; Ponce, Oscar Morales; Smid, Michiel H. M.; Stacho, Ladislav; Verdonschot, Sander; Woelfel, Philipp; van Renssen, André;
USA Arkin, Esther M.; Cole, Richard; Dadush, Daniel; Fürer, Martin; Farach-Colton, Martin; Fu, Bin; Gopalakrishnan, Ragavendran; Herlihy, Maurice; Kanoulas, Dimitrios; Khandekar, Rohit; Kohayakawa, Yoshiharu; Kortsarz, Guy; Krizanc, Danny; Kumar, Piyush; Mirrokni, Vahab S.; Mitchell, Joseph S. B.; Mosteiro, Miguel A.; Qian, Jiawei; Rödl, Vojtech; Rajaraman, Rajmohan; Ramachandran, Vijaya; Rucinski, Andrzej; Schalekamp, Frans; Sundaram, Ravi; Williamson, David P.;

[Top] [Home] [All LATIN Statistics]