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