LATIN 2012 Conference Program



Sunday April 15, 2012

18:00-21:00 Reception at the Hotel Libertador

Monday April 16, 2012

8:40-9:00 Opening Ceremony
9:00-10:00 Turing Year Lecture Martin Davis
10:00-10:20 A Theory and Algorithms for Combinatorial Reoptimization H. Shachnai, G. Tamir and T. Tamir
10:20-10:40 Reoptimization of some Maximum Weight Induced Hereditary Subgraph Problems N. Boria, J. Monnot and V. Paschos
10:40-11:00 Structural Complexity of Multiobjective NP Search Problems

K. Fleszar, C. Glasser, F. Lipp,
C. Reitwießner and M. Witek

11:00-11:20 Break
11:20-11:40 The Feedback Arc Set Problem with Triangle Inequality is a Vertex Cover Problem M. Mastrolilli
11:40-12:00 Approximating Minimum Label s-t Cut via Linear Programming L.Tang and P. Zhang
12:00-12:40 Survivable Network Activation Problems Z. Nutov
12:20-12:40 Degree-Constrained Node-Connectivity Z. Nutov
12:40-15:00 Lunch
15:00-16:00 Turing Year Lecture Scott Aaronson
16:00-16:20 The Relationship between Inner Product and Counting Cycles X. Sun, C. Wang and W. Yu
16:20-16:40 NE is not NP Turing Reducible to Nonexpoentially Dense NP Sets B. Fu
16:40-17:00 Capacity achieving two-write WOM codes A. Shpilka
17:00-17:20 Break
17:20-17:40 Indexed Multi-Pattern Matching T. Gagie, K. Karhu, J. Kärkkäinen,
V. Mäkinen, L. Salmela and J. Tarhio
17:40-18:00 Forbidden Patterns J. Fischer, T. Gagie, T. Kopelowitz,
M. Lewenstein,V. Mäkinen, L. Salmela, and Niko Välimäki

Tuesday April 17, 2012

9:00-10:00 Invited Talk Dana Randall
10:00-10:20 An Improved Upper Bound on the Density of Universal Random Graphs D. Dellamonica Jr., Y. Kohayakawa, V. Rödl, and A. Ruciski
10:20-10:40 Erdös-Rényi Sequences and Deterministic construction of Expanding Cayley Graphs V. Arvind, P. Mukhopadhyay and
P. Nimbhorkar
10:40-11:00 Random Walks and Bisections in Random Circulant Graphs B. Mans and I. Shparlinski
11:00-11:20 Break
11:20-11:40 On Plane Constrained Bounded-Degree Spanners P. Bose, R. Fagerberg, A. Van Renssen and
S. Verdonschot
11:40-12:00 Approximating the Edge Length of 2-Edge Connected Planar Geometric Graphs on a Set of Points S. Dobrev, E. Kranakis, D. Krizanc,
O. Morales-Ponce, and L. Stacho
12:00-12:20 Coloring Planar Homothets and Three-Dimensional Hypergraphs J. Cardinal and M. Korman
12:20-12:40 A Generalization of the Convex Kakeya Problem H.-K. Ahn, S. Won Bae, O. Cheong,
J. Gudmundsson, T. Tokuyama and
A. Vigneron
12:40-15:00 Lunch
15:00-15:20 Parameterized Complexity of MaxSat Above Average R. Crowston, G. Gutin, M. Jones, V. Raman, and S. Saurabh
15:20-15:40 Solving the 2-Disjoint Connected Subgraphs problem faster than 2n M. Cygan, M. Pilipczuk, M. Pilipczuk and
J. Wojtaszczyk
15:40-16:00 New Lower Bound on Max Cut of hypergraphs with an application to r-Set Splitting A. C. Giannopoulou, S. Kolay, and
S. Saurabh
16:00-16:20 k-Gap Interval Graphs F. Fomin, S. Gaspers, P. Golovach,
K. Suchan, S. Szeider, E. J. Van Leeuwen, M. Vatshelle and Y. Villanger
16:20-16:40 Break
16:40-17:00 Hausdorff Rank of Scattered Context-free Linear Orders Z. Ésik and S. Iván
17:00-17:20 Logspace Computations in Graph groups and Coxeter Groups V. Diekert, J. Kausch, and M. Lohrey
17:20-17:40 Oblivious Two-Way Finite Automata: Decidability and Complexity M. Kutrib, A. Malcher and G. Pighizzini
17:40-18:00 Density Classification on Infinite Lattices and Trees A. Bušić, N. Fatès, J. Mairesse, and
I. Marcovici
 18:00-18:40  Imre Simon Test-of-Time Award Ceremony

 Wednesday April 18, 2012

9:00-10:00 Invited Talk Marcos Kiwi
10:00-10:20 Clique-colouring and Biclique-colouring Unichord-free Graphs H. B. Macêdo Filho, R. Machado and
C. Figueiredo
10:20-10:40  Computing Minimum Geodetic Sets in Proper Interval Graphs  T. Ekim, A. Erey, P. Heggernes,
P. Van 'T Hof and D. Meister
10:40-11:00 On the Radon Number for P3-Convexity M. C. Dourado, D. Rautenbach,
V. Fernandes Dos Santos,
Philipp M. Schaefer, J. L. Szwarcfiter and
A. Toman
11:00-11:20 Break
11:20-11:40 Decidability Classes for Mobile Agents Computing P. Fraigniaud and A. Pelc
11:40-12:00 Renaming is Weaker than Set Agreement but for Perfect Renaming: A Map of Sub-Consensus Tasks A. Castañeda, D. Imbs, S. Rajsbaum and M. Raynal
12:00-12:20 An Equivariance Theorem with Applications to Renaming A. Castañeda, M. Herlihy and S. Rajsbaum
12:20-12:40 Opportunistic Information Dissemination in Mobile Ad-hoc Networks: Adaptiveness vs. Obliviousness and Randomization vs. Determinism M. Farach-Colton, A. Fernández Anta, A. Milani, M. A. Mosteiro and
S. Zaks
12:40-15:00 Lunch
15:30-20:00 Excursion
20:00-23:00 Banquet at the Monasterio de Santa Catalina

Thursday April 19, 2012

9:00-9:20 The Life and Work of Philippe Flajolet Daniel Panario
9:20-10:20 Invited Talk Luc Devroye
10:20-10:40 Break
10:40-11:00 Fully Analyzing an Algebraic Pólya Urn Model B. Morcrette
11:00-11:20 Pseudo-randomness of a Random Kronecker Sequence E. Cesaratto and B. Vallée
11:20-11:40 Hiring Above the m-th Best Candidate: A Generalization of Records in Permutations A. Helmi, C. Martínez and A. Panholzer
11:40-12:00 Independence of Tabulation-Based Hash Classes T. Q. Klassen and P. Woelfel
12:40-15:00 Lunch
15:00-15:20 On the Integrality Gap of the Subtour LP for the 1,2-TSP J. Qian, F. Schalekamp,
D. Williamson and A. Van Zuylen
15:20-15:40 On the Performance of Smith's Rule in Single-machine Scheduling with Nonlinear Cost W. Höhn and T. Jacobs
15:40-16:00 A O(1/ε2)n Sieving Algorithm for Approximate Integer Programming D. Dadush
16:00-16:20 A Better Approximation Ratio and an IP formulation for a Sensor Cover Problem R. da Ponte Barbosa and
Y. Wakabayashi
16:20-16:40 Break
16:40-17:00 Bichromatic 2-center of pairs of points E. M. Arkin, J. M. Díaz-Báñez,
F. Hurtado, P. Kumar, J. S. B. Mitchell,
B. Palop, P. Pérez-Lantero,
M. Saumell, and R. I. Silveira
17:00-17:20 Two-Dimensional Range Diameter Queries P. Davoodi, M. Smid, and
F. van Walderveen
17:20-17:40 Space-Efficient Approximation Scheme for Circular Earth Mover Distance J. Brody, H. Liang, and X. Sun
18:00-18:40 LATIN Business Meeting

Friday April 20, 2012

9:00-10:00 Invited Talk Kirk Pruhs
10:00-10:20 Revisiting the Cache Miss Analysis of Multithreaded Algorithms R. Cole, V. Ramachandran.
10:20-10:40 The Efficiency of MapReduce in Parallel External Memory G. Greiner and R. Jacob
10:40-11:00 Low Complexity Scheduling Algorithm Minimizing the Energy for Tasks with Agreeable Deadlines E. Angel, E. Bampis, and V. Chau
11:00-11:20 Break
11:20-11:40 On the Non-progressive Spread of Influence through Social Networks M. Fazli, M. Ghodsi, J. Habibi,
P. J. Khalilabadi, V. Mirrokni and
S. S. Sadeghabad
11:40-12:00 Advantage of Overlapping Clusters for Minimizing Conductance R. Khandekar, G. Kortsarz, and
V. Mirrokni
12:00-12:20 Cache me if you can: Capacitated Selfish Replication Games R. Gopalakrishnan, D. Kanoulas,
N. N. Karuturi, C. P. Rangan,
R. Rajaraman, and Ravi Sundaram.
12:20-12:40 On the Advice Complexity of the Knapsack Problem H.-J. Böckenhauer, D. Komm,
R. Kralovic and P. Rossmanith
12:40-15:00 Lunch
15:00-15:20 Efficient Arbitrary and Resolution Proofs of Unsatisfiability for Restricted tree-width Martin Fürer
15:20-15:40 On the Bend-number of Planar and Outerplanar Graphs D. Heldt, K. Knauer and T. Ueckerdt
15:40-16:00 Algorithms for some H-join decompositions Michel Habib, Antoine Mamcarz and Fabien De Montgolfie
16:00-16:20 End of Conference