Automata, Languages and Programming: 36th International Colloquium, Icalp 2009, Rhodes, Greece, July 5-12, 2009, Proceedings - Lecture Notes in Computer Science

Jacket Description/Back: The two-volume set LNCS 5555 and LNCS 5556 constitutes the refereed proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP 2009, held in Rhodes, Greece, in July 2009. The 126 revised full papers (62 papers for track A, 24 for track B, and 22 for track C) presented were carefully reviewed and selected from a total of 370 submissions. The papers are grouped in three major tracks on algorithms, automata, complexity and games; on logic, semantics, theory of programming, as well as on foundations of networked computation: models, algorithms and information management. LNCS 5556 contains 46 contributions of tracks B and C selected from 147 submissions as well as 2 invited lectures. This two-volume set lauches the new subline of Lecture Notes in Computer Science, entitled LNCS Advanced Research in Computing and Software Science (ARCoSS). Table of Contents: Invited Lectures -- Assigning Papers to Referees / Kurt Mehlhorn -- Algorithmic Game Theory: A Snapshot / Christos H. Papadimitriou -- Contributed Papers -- SDP-Based Algorithms for Maximum Independent Set Problems on Hypergraphs / Geir Agnarsson, MagnUs M. HalldOrsson, Elena Losievskaja -- Correlation Clustering Revisited: The True Cost of Error Minimization Problems / Nir Ailon, Edo Liberty -- Sorting and Selection with Imprecise Comparisons / MiklOs Ajtai, Vitaly Feldman, Avinatan Hassidim, Jelani Nelson -- Fast FAST / Noga Alon, Daniel Lokshtanov, Saket Saurabh -- Bounds on the Size of Small Depth Circuits for Approximating Majority / Kazuyuki Amano -- Counting Subgraphs via Homomorphisms / Omid Amini, Fedor V. Fomin, Saket Saurabh -- External Sampling / Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld -- Functional Monitoring without Monotonicity / Chrisil Arackaparambil, Joshua Brody, Amit Chakrabarti -- De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results / Yuriy Arbitman, Moni Naor, Gil Segev -- Towards a Study of Low-Complexity Graphs / Sanjeev Arora, David Steurer, Avi Wigderson -- Decidability of Conjugacy of Tree-Shifts of Finite Type / Nathalie Aubrun, Marie-Pierre BEal -- Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule / Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs, Dmitriy Katz -- Competitive Analysis of Aggregate Max in Windowed Streaming / Luca Becchetti, Elias Koutsoupias -- Faster Regular Expression Matching / Philip Bille, Mikkel Thorup -- A Fast and Simple Parallel Algorithm for the Monotone Duality Problem / Endre Boros, Kazuhisa Makino -- Unconditional Lower Bounds against Advice / Harry Buhrman, Lance Fortnow, Rahul Santhanam -- Approximating Decision Trees with Multiway Branches / Venkatesan T. Chakaravarthy, Vinayaka Pandit, Sambuddha Roy, Yogish Sabharwal -- Annotations in Data Streams / Amit Chakrabarti, Graham Cormode, Andrew McGregor -- The Tile Complexity of Linear Assemblies / Harish Chandran, Nikhil Gopalkrishnan, John Reif -- A Graph Reduction Step Preserving Element-Connectivity and Applications / Chandra Chekuri, Nitish Korula -- Approximating Matches Made in Heaven / Ning Chen, Nicole Immorlica, Anna R. Karlin, Mohammad Mahdian, Atri Rudra -- Strong and Pareto Price of Anarchy in Congestion Games / Steve Chien, Alistair Sinclair -- A Better Algorithm for Random k-SAT / Amin Coja-Oghlan -- Exact and Approximate Bandwidth / Marek Cygan, Marcin Pilipczuk -- Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs / Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi -- Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs / Erik D. Demaine, MohammadTaghi Hajiaghayi, Philip N. Klein -- On Cartesian Trees and Range Minimum Queries / Erik D. Demaine, Gad M. Landau, Oren Weimann -- Applications of a Splitting Trick / Martin Dietzfelbinger, Michael Rink -- Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness / Benjamin Doerr, Tobias Friedrich, Thomas Sauerwald -- Incompressibility through Colors and IDs / Michael Dom, Daniel Lokshtanov, Saket Saurabh -- Partition Arguments in Multiparty Communication Complexity / Jan Draisma, Eyal Kushilevitz, Enav Weinreb -- High Complexity Tilings with Sparse Errors / Bruno Durand, Andrei Romashchenko, Alexander Shen -- Tight Bounds for the Cover Time of Multiple Random Walks / Robert ElsAsser, Thomas Sauerwald -- Online Computation with Advice / Yuval Emek, Pierre Fraigniaud, Amos Korman, Adi RosEn -- Dynamic Succinct Ordered Trees / Arash Farzan, J. Ian Munro -- Universal Succinct Representations of Trees? / Arash Farzan, Rajeev Raman, S. Srinivasa Rao -- Distortion Is Fixed Parameter Tractable / Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Elena Losievskaja, Frances A. Rosamond, Saket Saurabh -- Towards Optimal Range Medians / Beat Gfeller, Peter Sanders -- B-Treaps: A Uniquely Represented Alternative to B-Trees / Daniel Golovin -- Testing Fourier Dimensionality and Sparsity / Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, Karl Wimmer -- Revisiting the Direct Sum Theorem and Space Lower Bounds in Random Order Streams / Sudipto Guha, Zhiyi Huang -- Wireless Communication Is in APX / MagnUs M. HalldOrsson, Roger Wattenhofer -- The Ehrenfeucht-Silberger Problem / StepAn Holub, Dirk Nowotka -- Applications of Effective Probability Theory to Martin-LOf Randomness / Mathieu Hoyrup, CristObal Rojas -- An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables / Klaus Jansen -- Popular Mixed Matchings / Telikepalli Kavitha, JuliAn Mestre, Meghana Nasre -- Factoring Groups Efficiently / Neeraj Kayal, Timur Nezhmetdinov -- On Finding Dense Subgraphs / Samir Khuller, Barna Saha -- Learning Halfspaces with Malicious Noise / Adam R. Klivans, Philip M. Long, Rocco A. Servedio -- General Scheme for Perfect Quantum Network Coding with Free Classical Communication / Hirotada Kobayashi, FranCois Le Gall, Harumichi Nishimura, Martin RUtteler -- Greedy ?-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost / Christos Koufogiannakis, Neal E. Young -- Limits and Applications of Group Algebras for Parameterized Problems / Ioannis Koutis, Ryan Williams -- Sleep with Guilt and Work Faster to Minimize Flow Plus Energy / Tak-Wah Lam, Lap-Kei Lee, Hing-Fung Ting, Isaac K. K. To, Prudence W. H. Wong -- Improved Bounds for Flow Shop Scheduling / Monaldo Mastrolilli, Ola Svensson -- A 3/2-Approximation Algorithm for General Stable Marriage / Eric McDermid -- Limiting Negations in Formulas / Hiroki Morizumi -- Fast Polynomial-Space Algorithms Using MObius Inversion: Improving on Steiner Tree and Related Problems / Jesper Nederlof -- Superhighness and Strong Jump Traceability / AndrE Nies -- Amortized Communication Complexity of Distributions / JErEmie Roland, Mario Szegedy -- The Number of Symbol Comparisons in QuickSort and QuickSelect / Brigitte VallEe, Julien ClEment, James Allen Fill, Philippe Flajolet -- Computing the Girth of a Planar Graph in O(n log n) Time / Oren Weimann, Raphael Yuster -- Elimination Graphs / Yuli Ye, Allan Borodin -- Author Index.

Contributor Bio:  Thomas, Wolfgang Prof. Dr. Heinz-Dieter Ebbinghaus und Prof. Dr. JArg Flum forschen und lehren am Institut fA1/4r Mathematik der UniversitAt Freiburg, Prof. Dr. Wolfgang Thomas ist Inhaber des Lehrstuhls fA1/4r Informatik 7 (Logik und Theorie diskreter Systeme) der RWTH Aachen.