domingo, 12 de febrero de 2012

Latin American Symposium on Theoretical Informatics


En Abril (16-20) la Universidad Católica San Pablo será sede del congreso Latin American Symposium on Theoretical Informatics, uno de los congresos internacionales más importantes en el área de computación a nivel mundial

Además paralelamente se realizará el Primer Latin American Theoretical Informatics School: 

Conferencias a presentarse:

  • A Theory and Algorithms for Combinatorial Reoptimization - H. Shachnai, G. Tamir and T. Tamir (Israel).
  • Reoptimization of some Maximum Weight Induced Hereditary Subgraph Problems - N. Boria, J. Monnot and V. Paschos (Francia).
  • Structural Complexity of Multiobjective NP Search Problems - K. Fleszar, C. Glasser, F. Lipp, C. Reitwießner and M. Witek (Alemania).
  • The Feedback Arc Set Problem with Triangle Inequality is a Vertex Cover Problem - M. Mastrolilli (Suiza).
  • Approximating Minimum Label s-t Cut via Linear Programming - L.Tang and P. Zhang (China).
  • Survivable Network Activation Problems - Z. Nutov (Israel).
  • Degree-Constrained Node-Connectivity - Z. Nutov (Israel).
  • The Relationship between Inner Product and Counting Cycles - X. Sun, C. Wang and W. Yu (China).
  • NE is not NP Turing Reducible to Nonexpoentially Dense NP Sets - B. Fu (USA).
  • Capacity achieving two-write WOM codes - A. Shpilka (Israel).
  • Indexed Multi-Pattern Matching - T. Gagie, K. Karhu, J. Kärkkäinen, V. Mäkinen, L. Salmela and J. Tarhio (Finlandia).
  • Forbidden Patterns - J. Fischer, T. Gagie, T. Kopelowitz, M. Lewenstein,V. Mäkinen, L. Salmela and Niko Välimäki (Finlandia).
  • An Improved Upper Bound on the Density of Universal Random Graphs - D. Dellamonica Jr. (USA), Y. Kohayakawa (Brasil), V. Rödl (USA), and A. Ruciski (Polonia).
  • Erdös-Rényi Sequences and Deterministic construction of Expanding Cayley Graphs - V. Arvind, P. Mukhopadhyay and P. Nimbhorkar (India).
  • Random Walks and Bisections in Random Circulant Graphs - B. Mans and I. Shparlinski (Australia).
  • On Plane Constrained Bounded-Degree Spanners - P. Bose (Canadá), R. Fagerberg (Dinamarca), A. Van Renssen (Canadá) and S. Verdonschot (Canadá)
  • Approximating the Edge Length of 2-Edge Connected Planar Geometric Graphs on a Set of Points - S. Dobrev (República Eslovaca), E. Kranakis (Canadá), D. Krizanc (USA), O. Morales-Ponce (Canadá) and L. Stacho (Canadá).
  • Coloring Planar Homothets and Three-Dimensional Hypergraphs - J. Cardinal and M. Korman (Bélgica).
  • A Generalization of the Convex Kakeya Problem - H.-K. Ahn (Korea del Sur), S. Won Bae (Korea del Sur), O. Cheong (Korea del Sur), J. Gudmundsson (Australia), T. Tokuyama (Japón) and A. Vigneron (Arabia Saudita).
  • Parameterized Complexity of MaxSat Above Average - R. Crowston (UK), G. Gutin (UK), M. Jones (UK), V. Raman (India), and S. Saurabh (India).
  • Solving the 2-Disjoint Connected Subgraphs problem faster than 2n - M. Cygan, M. Pilipczuk, M. Pilipczuk and J. Wojtaszczyk (Noruega).
  • New Lower Bound on Max Cut of hypergraphs with an application to r-Set Splitting - A. C. Giannopoulou, S. Kolay, and S. Saurabh (India).
  • k-Gap Interval Graphs - F. Fomin (Noruega), S. Gaspers (Austria), P. Golovach (UK), K. Suchan (Polonia), S. Szeider (Austria), E. J. Van Leeuwen (Noruega), M. Vatshelle (Noruega) and Y. Villanger (Noruega).
  • Hausdorff Rank of Scattered Context-free Linear Orders - Z. Ésik and S. Iván (Hungría).
  • Logspace Computations in Graph groups and Coxeter Groups - V. Diekert, J. Kausch, and M. Lohrey (Alemania).
  • Oblivious Two-Way Finite Automata: Decidability and Complexity - M. Kutrib, A. Malcher and G. Pighizzini (Alemania).
  • Density Classification on Infinite Lattices and Trees - A. Bušic', N. Fatès, J. Mairesse, and I. Marcovici (Francia).
  • Clique-colouring and Biclique-colouring Unichord-free Graphs - H. B. Macêdo Filho, R. Machado and C. Figueiredo (Brasil).
  • Computing Minimum Geodetic Sets in Proper Interval Graphs - T. Ekim (Turquía), A. Erey (Turquía), P. Heggernes (Noruega), P. Van 'T Hof (Noruega) and D. Meister (Alemania).
  • 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 (Alemania).
  • Decidability Classes for Mobile Agents Computing - P. Fraigniaud (Francia) and A. Pelc (Canadá).
  • 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 (Mexico).
  • An Equivariance Theorem with Applications to Renaming - A. Castañeda (Mexico), M. Herlihy (USA) and S. Rajsbaum (Mexico).
  • Opportunistic Information Dissemination in Mobile Ad-hoc Networks: Adaptiveness vs. Obliviousness and Randomization vs. Determinism
  • M. Farach-Colton (USA), A. Fernández Anta (España), A. Milani (Francia), M. A. Mosteiro (USA) and S. Zaks (Israel).
  • Fully Analyzing an Algebraic Pólya Urn Model - B. Morcrette (Francia).
  • Pseudo-randomness of a Random Kronecker Sequence - E. Cesaratto and B. Vallée (Francia).
  • Hiring Above the m-th Best Candidate: A Generalization of Records in Permutations - A. Helmi (España), C. Martínez (España) and A. Panholzer (Austria).
  • Independence of Tabulation-Based Hash Classes - T. Q. Klassen and P. Woelfel (Canadá).
  • On the Integrality Gap of the Subtour LP for the 1,2-TSP - J. Qian (USA), F. Schalekamp (USA), D. Williamson (USA) and A. Van Zuylen (Alemania).
  • On the Performance of Smith's Rule in Single-machine Scheduling with Nonlinear Cost - W. Höhn (Alemania) and T. Jacobs (Japón).
  • A O(1/?2)n Sieving Algorithm for Approximate Integer Programming - D. Dadush (USA).
  • A Better Approximation Ratio and an IP formulation for a Sensor Cover Problem - R. da Ponte Barbosa and Y. Wakabayashi (Japón).
  • Bichromatic 2-center of pairs of points - E. M. Arkin (USA), J. M. Díaz-Báñez (España), F. Hurtado (España), P. Kumar (USA), J. S. B. Mitchell (USA), B. Palop (España), P. Pérez-Lantero (Chile), M. Saumell (España), and R. I. Silveira (España).
  • Two-Dimensional Range Diameter Queries - P. Davoodi (Dinamarca), M. Smid (Canadá), and F. van Walderveen (Dinamarca).
  • Space-Efficient Approximation Scheme for Circular Earth Mover Distance - J. Brody, H. Liang, and X. Sun (China).
  • Revisiting the Cache Miss Analysis of Multithreaded Algorithms - R. Cole, V. Ramachandran (USA).
  • The Efficiency of MapReduce in Parallel External Memory - G. Greiner and R. Jacob (Suiza).
  • Low Complexity Scheduling Algorithm Minimizing the Energy for Tasks with Agreeable Deadlines - E. Angel, E. Bampis, and V. Chau (Francia).
  • 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  (Irán).
  • Advantage of Overlapping Clusters for Minimizing Conductance - R. Khandekar, G. Kortsarz, and V. Mirrokni (USA).
  • Catch me if you can: Capacitated Selfish Replication Games - R. Gopalakrishnan (USA), D. Kanoulas (USA), N. N. Karuturi (India), C. P. Rangan (India), R. Rajaraman (USA), and Ravi Sundaram (USA).
  • On the Advice Complexity of the Knapsack Problem - H.-J. Böckenhauer (Suiza), D. Komm (Suiza), R. Kralovic (Suiza) and P. Rossmanith (Alemania).