ICALP 2009
36th International Colloquium on
Automata, Languages and
Programming


July 5 - 12, 2009
Rhodes - Greece


ACCEPTED PAPERS


The Track A accepted papers list.

  • Erik D. Demaine, Gad Landau and Oren Weimann. On Cartesian Trees and Range Minimum Querie
  • Oren Weimann and Raphael Yuster. Computing the Girth of a Planar Graph in O(n log n) Time
  • Ning Chen, Nicole Immorlica, Anna Karlin, Mohammad Mahdian and Atri Rudra. Approximating Matches Made in Heaven
  • Andre Nies. Superhighness and strong jump traceability
  • Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs and Dmitriy Rogozhnikov-Katz. Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule
  • Erik D. Demaine, MohammadTaghi Hajiaghayi and Philip Klein. Node-weighted Steiner Tree and Group Steiner Tree in Planar Graphs
  • Julien Clιment, Brigitte Vallee, Philippe Flajolet and James Allen Fill. The number of Symbol Comparisons in Quicksort and Quickselect
  • Amin Coja-Oghlan. A better algorithm for random k-SAT
  • Klaus Jansen. An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables
  • Michael Fellows, Fedor Fomin, Daniel Lokshtanov, Elena Losievskaja, Frances A. Rosamond and Saket Saurabh. Distortion is Fixed Parameter Tractable
  • Sudipto Guha and Zhiyi Huang. Revisiting the Direct Sum Theorem and Space Lower Bounds in Random Order Streams
  • Amit Chakrabarti, Graham Cormode and Andrew McGregor. Annotations in Data Streams
  • Chrisil Arackaparambil, Joshua Brody and Amit Chakrabarti. Functional Monitoring Without Monotonicity
  • Kazuyuki Amano. Bounds on the Size of Small Depth Circuits for Approximating Majority
  • Hiroki Morizumi. Limiting Negations in Formulas'
  • Monaldo Mastrolilli and Ola Svensson. 'Improved Bounds for Flow Shop Scheduling''
  • Yuriy Arbitman, Moni Naor and Gil Segev. De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results
  • Yuval Emek, Pierre Fraigniaud, Amos Korman and Adi Rosen. Online Computation with Advice
  • Telikepalli Kavitha, Julian Mestre and Meghana Nasre. Popular Mixed Matchings
  • Mathieu Hoyrup and Cristobal Rojas. Applications of Effective Probability Theory to Martin-Loef Randomness
  • Jesper Nederlof. Fast polynomial-space algorithms using Mobius inversion: Improving on Steiner Tree and related problems
  • Stepan Holub and Dirk Nowotka. The Ehrenfeucht-Silberger Problem
  • Bruno Durand, Alexander Shen and Andrei Romashchenko. High Complexity Tilings with Sparse Errors
  • Eric J Mc Dermid. A 3/2-approximation algorithm for general stable marriage
  • Parikshit Gopalan, Ryan O'Donnell, Rocco Servedio, Amir Shpilka and Karl Wimmer. Testing Fourier dimensionality and sparsity
  • Alexandr Andoni, Piotr Indyk, Krzysztof Onak and Ronitt Rubinfeld. External Sampling
  • Steve Chien and Alistair Sinclair. Strong and Pareto Price of Anarchy in Congestion Games
  • Daniel Golovin. B-Treaps: A Uniquely Represented Alternative to B-Trees
  • Hirotada Kobayashi, Francois Le Gall, Harumichi Nishimura and Martin Roetteler. General Scheme for Perfect Quantum Network Coding with Free Classical Communication
  • Yuli Ye and Allan Borodin. Elimination Graphs
  • Chandra Chekuri and Nitish Korula. A Graph Reduction Step Preserving Element-Connectivity and Applications
  • Nathalie Aubrun and Marie-Pierre Bιal. Decidability of conjugacy of tree shifts of finite type
  • Adam Klivans, Phil Long and Rocco Servedio. Learning Halfspaces with Malicious Noise
  • Tak-Wah Lam, Lap-Kei Lee, Hing-Fung Ting, Isaac To and Prudence W.H. Wong. Sleep with Guilt and Work Faster to Minimize Flow plus Energy
  • Philip Bille and Mikkel Thorup. Faster Regular Expression Matching
  • Venkatesan Chakaravarthy, Vinayaka Pandit, Sambuddha Roy and Yogish Sabharwal. Approximating Decision Trees with Multiway Branches
  • Neeraj Kayal and Timur Nezhmetdinov. Factoring groups efficiently
  • Geir Agnarsson, Magnϊs Mαr Halldσrsson and Elena Losievskaja. SDP-based Algorithms for Maximum Independent Set Problems on Hypergraphs
  • Michael Dom, Daniel Lokshtanov and Saket Saurabh. Incompressibility through Colors and IDs
  • Enav Weinreb, Eyal Kushilevitz and Jan Draisma. Partition Arguments in Multiparty Communication Complexity
  • Jιrιmie Roland and Mario Szegedy. Amortized communication complexity of distributions
  • Noga Alon, Daniel Lokshtanov and Saket Saurabh. Fast FAST
  • Beat Gfeller and Peter Sanders. Towards Optimal Range Medians
  • Barna Saha and Samir Khuller. On Finding Dense Subgraphs
  • Erik D. Demaine, MohammadTaghi Hajiaghayi and Ken-ichi Kawarabayashi. Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs
  • Arash Farzan, Rajeev Raman and Srinivasa Rao Satti. Universal representation of Succinct Trees?
  • Marek Cygan and Marcin Pilipczuk. Exact and approximate Bandwidth
  • Omid Amini, Fedor Fomin and Saket Saurabh. Counting Subgraphs via Homomorphisms
  • Nir Ailon and Edo Liberty. Correlation Clustering Revisited: The ``True Cost of Error Minimization Problems''
  • Miklσs Ajtai, Vitaly Feldman, Avinatan Hassidim and Jelani Nelson. Sorting and Selection with Imprecise Comparisons
  • Harry Buhrman, Lance Fortnow and Rahul Santhanam. Unconditional Lower Bounds against Advice
  • Arash Farzan and Ian Munro. Dynamic Succinct Ordered Trees
  • Endre Boros and Kazuhisa Makino. A Fast and Simple Parallel Algorithm for the Monotone Duality Problem
  • Ioannis Koutis and Ryan Williams. Limits and applications of group algebras for parameterized problems
  • Sanjeev Arora, David Steurer and Avi Wigderson. Towards a study of low-complexity graphs
  • Robert Elsaesser and Thomas Sauerwald. Tight Bounds for the Cover Time of Multiple Random Walks
  • Harish Chandran, Nikhil Gopalkrishnan and John Reif. The Tile Complexity of Linear Assemblies
  • Luca Becchetti and Elias Koutsoupias. Competitive analysis of aggregate max in windowed streaming
  • Martin Dietzfelbinger and Michael Rink. Applications of a splitting trick
  • Christos Koufogiannakis and Neal Young. Greedy $\degree$-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
  • Benjamin Doerr, Tobias Friedrich and Thomas Sauerwald. Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness
  • Magnus M. Halldorsson and Roger Wattenhofer. Wireless Communication is in APX

The Track B accepted papers list.

  • Thomas Place and Luc Segoufin. A decidable characterization of LT on trees
  • Michael Ummels and Dominik Wojtczak. The Complexity of Nash Equilibria in Simple Stochastic Multiplayer Games
  • Ugo Dal Lago and Simone Martini. On Constructor Rewrite Systems and the Lambda-Calculus
  • Jean-Eric Pin and Mario J. J. Branco. Equations defining the polynomial closure of a lattice of regular languages
  • Patricia Bouyer and Vojtech Forejt. Reachability in Stochastic Timed Games
  • Jakub Michaliszyn. Decidability of the Guarded Fragment with the Transitive Closure
  • Naoki Kobayashi and Luke Ong. Complexity of Model Checking Recursion Schemes for Fragments of the Modal Mu-Calculus
  • Vincent Gripon and Olivier Serre. Qualitative Concurrent Games with Imperfect Information
  • Martin Beaudry and François Lemieux. Faithful Loops for Aperiodic E-ordered Monoids
  • Philippe Chaput, Vincent Danos, Prakash Panangaden and Gordon Plotkin. Approximating Markov Processes By Averaging
  • Jean-Pierre Jouannaud and Vincent van Oostrom. Diagrammatic Completion
  • Pawel Parys and Igor Walukiewicz. Weak Alternating Timed Automata
  • Christian Dax, Felix Klaedtke and Martin Lange. On Regular Temporal Logics with Past
  • Manuel Bodirsky, Peter Jonsson and Timo von Oertzen. Semilinear Program Feasibility
  • Thomas Colcombet. The theory of stabilization monoids and regular cost functions
  • Sylvie Boldo. Floats & Ropes: a case study for formal numerical program verification
  • Achim Blumensath, Martin Otto and Mark Weyer. Boundedness of monadic second-order formulae over finite words
  • Christel Baier, Nathalie Bertrand, Patricia Bouyer and Thomas Brihaye. When are Timed Automata Determinizable?
  • Lucia Acciai and Michele Boreale. Deciding safety properties in infinite-state pi-calculus via behavioural types
  • Paul-André Melliès, Nicolas Tabareau and Christine Tasson. An explicit formula for the free exponential modality of linear logic
  • Lars Kuhtz and Bernd Finkbeiner. LTL Path Checking is Efficiently Parallelizable
  • Thomas Colcombet and Konrad Zdanowski. A Tight Lower Bound for Determinization of Buchi automata
  • Jean Goubault-Larrecq and Alain FINKEL. Forward Analysis for WSTS, Part II: Complete WSTS

The Track C accepted papers list.

  • Sudipto Guha and Kamesh Munagala. Multi-armed Bandits with Metric Switching Costs
  • Rosario Pugliese, Francesco Tiezzi and Nobuko Yoshida. On observing dynamic prioritised actions in SOC
  • Damon Mosk-Aoyama and Tim Roughgarden. Worst-Case Efficiency Analysis of Queueing Disciplines
  • Ioannis Chatzigiannakis, Othon Michail and Paul Spirakis. Mediated Population Protocols
  • Kook Jin Ahn and Sudipto Guha. Graph Sparsification in the Semi- streaming Model
  • Flavio Chierichetti, Silvio Lattanzi and Alessandro Panconesi. Rumor Spreading in Social Networks
  • Andrea Clementi, Francesco Pasquale and Riccardo Silvestri. MANETS: High mobility can make up for low transmission power
  • Dariusz Kowalski and Andrzej Pelc. Leader Election in Ad Hoc Radio Networks: a Keen Ear Helps
  • Nitish Korula and Martin Pal.Algorithms for Secretary Problems on Graphs and Hypergraphs
  • Tobias Friedrich, Thomas Sauerwald and Dan Vilenchik. Smoothed Analysis of Balancing Networks
  • Christian Scheideler and Stefan Schmid. A Distributed and Oblivious Heap
  • Aris Anagnostopoulos, Ravi Kumar, Mohammad Mahdian and Eli Upfal. Sort Me If You Can: How to Sort Dynamic Data
  • Rocco De Nicola, Diego Latella, Michele Loreti and Mieke Massink. Rate-based Transition Systems for Stochastic Process Calculi
  • Dimitris Fotakis, Alexis Kaporis and Paul Spirakis. Efficient Methods for Selfish Network Design
  • Colin Cooper, David Ilcinkas, Ralf Klasing and Adrian Kosowski. Derandomizing Random Walks in Undirected Graphs Using Locally Fair Exploration Strategies
  • Rachid Guerraoui and Eric Ruppert. Names Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures
  • Alexander Fanghaenel, Thomas Kesselheim and Berthold Voecking. Improved Algorithms for Latency Minimization in Wireless Networks
  • Constantinos Daskalakis and Christos Papadimitriou. On a Network Generalization of the Minmax Theorem
  • Colin Cooper, Alan Frieze and Tomasz Radzik. Multiple random walks and interacting particle systems
  • Li Zhang, Proportional response dynamics for the Fisher market
  • Yossi Azar, Aleksander Madry, Thomas Moscibroda, Debmalya Panigrahi and Aravind Srinivasan. Maximum Bipartite Flow in Networks with Adaptive Channel Width
  • Maged Ibrahim, Aggelos Kiayias, Moti Yung and Hong-Sheng Zhou: Secure Function Collection with Sublinear Storage

Print - Search - Maintained by CTI / RU1
Page last modified on April 13, 2009, at 09:52 AM