36. ICALP 2009: Rhodes, Greece - Part I

Invited Lectures

• Kurt Mehlhorn:
  Assigning Papers to Referees. 1-2
  
• Christos H. Papadimitriou:
  Algorithmic Game Theory: A Snapshot. 3-11
  

Contributed Papers

• Geir Agnarsson, Magnús M. Halldórsson, Elena Losievskaja:
  SDP-Based Algorithms for Maximum Independent Set Problems on Hypergraphs. 12-23
  
• Nir Ailon, Edo Liberty:
  Correlation Clustering Revisited: The "True" Cost of Error Minimization Problems. 24-36
  
• Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim, Jelani Nelson:
  Sorting and Selection with Imprecise Comparisons. 37-48
  
• Noga Alon, Daniel Lokshtanov, Saket Saurabh:
  Fast FAST. 49-58
  
• Kazuyuki Amano:
  Bounds on the Size of Small Depth Circuits for Approximating Majority. 59-70
  
• Omid Amini, Fedor V. Fomin, Saket Saurabh:
  Counting Subgraphs via Homomorphisms. 71-82
  
• Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld:
  External Sampling. 83-94
  
• Chrisil Arackaparambil, Joshua Brody, Amit Chakrabarti:
  Functional Monitoring without Monotonicity. 95-106
  
• Yuriy Arbitman, Moni Naor, Gil Segev:
  De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results. 107-118
  
• Sanjeev Arora, David Steurer, Avi Wigderson:
  Towards a Study of Low-Complexity Graphs. 119-131
  
• Nathalie Aubrun, Marie-Pierre Béal:
  Decidability of Conjugacy of Tree-Shifts of Finite Type. 132-143
  
• Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs, Dmitriy Katz:
  Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule. 144-155
  
• Luca Becchetti, Elias Koutsoupias:
  Competitive Analysis of Aggregate Max in Windowed Streaming. 156-170
  
• Philip Bille, Mikkel Thorup:
  Faster Regular Expression Matching. 171-182
  
• Endre Boros, Kazuhisa Makino:
  A Fast and Simple Parallel Algorithm for the Monotone Duality Problem. 183-194
  
• Harry Buhrman, Lance Fortnow, Rahul Santhanam:
  Unconditional Lower Bounds against Advice. 195-209
  
• Venkatesan T. Chakaravarthy, Vinayaka Pandit, Sambuddha Roy, Yogish Sabharwal:
  Approximating Decision Trees with Multiway Branches. 210-221
  
• Amit Chakrabarti, Graham Cormode, Andrew McGregor:
  Annotations in Data Streams. 222-234
  
• Harish Chandran, Nikhil Gopalkrishnan, John H. Reif:
  The Tile Complexity of Linear Assemblies. 235-253
  
• Chandra Chekuri, Nitish Korula:
  A Graph Reduction Step Preserving Element-Connectivity and Applications. 254-265
  
• Ning Chen, Nicole Immorlica, Anna R. Karlin, Mohammad Mahdian, Atri Rudra:
  Approximating Matches Made in Heaven. 266-278
  
• Steve Chien, Alistair Sinclair:
  Strong and Pareto Price of Anarchy in Congestion Games. 279-291
  
• Amin Coja-Oghlan:
  A Better Algorithm for Random k-SAT. 292-303
  
• Marek Cygan, Marcin Pilipczuk:
  Exact and Approximate Bandwidth. 304-315
  
• Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi:
  Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs. 316-327
  
• Erik D. Demaine, MohammadTaghi Hajiaghayi, Philip N. Klein:
  Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs. 328-340
  
• Erik D. Demaine, Gad M. Landau, Oren Weimann:
  On Cartesian Trees and Range Minimum Queries. 341-353
  
• Martin Dietzfelbinger, Michael Rink:
  Applications of a Splitting Trick. 354-365
  
• Benjamin Doerr, Tobias Friedrich, Thomas Sauerwald:
  Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness. 366-377
  
• Michael Dom, Daniel Lokshtanov, Saket Saurabh:
  Incompressibility through Colors and IDs. 378-389
  
• Jan Draisma, Eyal Kushilevitz, Enav Weinreb:
  Partition Arguments in Multiparty Communication Complexity. 390-402
  
• Bruno Durand, Andrei E. Romashchenko, Alexander Shen:
  High Complexity Tilings with Sparse Errors. 403-414
  
• Robert Elsässer, Thomas Sauerwald:
  Tight Bounds for the Cover Time of Multiple Random Walks. 415-426
  
• Yuval Emek, Pierre Fraigniaud, Amos Korman, Adi Rosén:
  Online Computation with Advice. 427-438
  
• Arash Farzan, J. Ian Munro:
  Dynamic Succinct Ordered Trees. 439-450
  
• Arash Farzan, Rajeev Raman, S. Srinivasa Rao:
  Universal Succinct Representations of Trees? 451-462
  
• Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Elena Losievskaja, Frances A. Rosamond, Saket Saurabh:
  Distortion Is Fixed Parameter Tractable. 463-474
  
• Beat Gfeller, Peter Sanders:
  Towards Optimal Range Medians. 475-486
  
• Daniel Golovin:
  B-Treaps: A Uniquely Represented Alternative to B-Trees. 487-499
  
• Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, Karl Wimmer:
  Testing Fourier Dimensionality and Sparsity. 500-512
  
• Sudipto Guha, Zhiyi Huang:
  Revisiting the Direct Sum Theorem and Space Lower Bounds in Random Order Streams. 513-524
  
• Magnús M. Halldórsson, Roger Wattenhofer:
  Wireless Communication Is in APX. 525-536
  
• Stepan Holub, Dirk Nowotka:
  The Ehrenfeucht-Silberger Problem. 537-548
  
• Mathieu Hoyrup, Cristobal Rojas:
  Applications of Effective Probability Theory to Martin-Löf Randomness. 549-561
  
• Klaus Jansen:
  An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables. 562-573
  
• Telikepalli Kavitha, Julián Mestre, Meghana Nasre:
  Popular Mixed Matchings. 574-584
  
• Neeraj Kayal, Timur Nezhmetdinov:
  Factoring Groups Efficiently. 585-596
  
• Samir Khuller, Barna Saha:
  On Finding Dense Subgraphs. 597-608
  
• Adam R. Klivans, Philip M. Long, Rocco A. Servedio:
  Learning Halfspaces with Malicious Noise. 609-621
  
• Hirotada Kobayashi, François Le Gall, Harumichi Nishimura, Martin Rötteler:
  General Scheme for Perfect Quantum Network Coding with Free Classical Communication. 622-633
  
• Christos Koufogiannakis, Neal E. Young:
  Greedy D{\ensuremath{\Delta}}-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost. 634-652
  
• Ioannis Koutis, Ryan Williams:
  Limits and Applications of Group Algebras for Parameterized Problems. 653-664
  
• Tak Wah Lam, Lap-Kei Lee, Hing-Fung Ting, Isaac Kar-Keung To, Prudence W. H. Wong:
  Sleep with Guilt and Work Faster to Minimize Flow Plus Energy. 665-676
  
• Monaldo Mastrolilli, Ola Svensson:
  Improved Bounds for Flow Shop Scheduling. 677-688
  
• Eric McDermid:
  A 3/2-Approximation Algorithm for General Stable Marriage. 689-700
  
• Hiroki Morizumi:
  Limiting Negations in Formulas. 701-712
  
• Jesper Nederlof:
  Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems. 713-725
  
• André Nies:
  Superhighness and Strong Jump Traceability. 726-737
  
• Jérémie Roland, Mario Szegedy:
  Amortized Communication Complexity of Distributions. 738-749
  
• Brigitte Vallée, Julien Clément, James Allen Fill, Philippe Flajolet:
  The Number of Symbol Comparisons in QuickSort and QuickSelect. 750-763
  
• Oren Weimann, Raphael Yuster:
  Computing the Girth of a Planar Graph in O(n logn) Time. 764-773
  
• Yuli Ye, Allan Borodin:
  Elimination Graphs. 774-785