domingo, 12 de febrero de 2012

Latin American Symposium on Theoretical Informatics


PONENTES CONFIRMADOS DE ALEMANIA, ARABIA SAUDITA, AUSTRALIA, AUSTRIA, BÉLGICA, BRASIL, CANADÁ, CHILE, CHINA, DINAMARCA, ESPAÑA, FINLANDIA, FRANCIA, HUNGRÍA, INDIA, IRÁN, ISRAEL, JAPÓN, KOREA DEL SUR, MEXICO, NORUEGA, POLONIA, REINO UNIDO, REPÚBLICA ESLOVACA, SUIZA, TURQUÍA, USA. 

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