Automata, Languages and Programming: 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I

Front Matter....Pages -
Assigning Papers to Referees....Pages 1-2
Algorithmic Game Theory: A Snapshot....Pages 3-11
SDP-Based Algorithms for Maximum Independent Set Problems on Hypergraphs....Pages 12-23
Correlation Clustering Revisited: The “True” Cost of Error Minimization Problems....Pages 24-36
Sorting and Selection with Imprecise Comparisons....Pages 37-48
Fast FAST ....Pages 49-58
Bounds on the Size of Small Depth Circuits for Approximating Majority....Pages 59-70
Counting Subgraphs via Homomorphisms....Pages 71-82
External Sampling....Pages 83-94
Functional Monitoring without Monotonicity....Pages 95-106
De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results....Pages 107-118
Towards a Study of Low-Complexity Graphs....Pages 119-131
Decidability of Conjugacy of Tree-Shifts of Finite Type....Pages 132-143
Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule....Pages 144-155
Competitive Analysis of Aggregate Max in Windowed Streaming....Pages 156-170
Faster Regular Expression Matching....Pages 171-182
A Fast and Simple Parallel Algorithm for the Monotone Duality Problem....Pages 183-194
Unconditional Lower Bounds against Advice....Pages 195-209
Approximating Decision Trees with Multiway Branches....Pages 210-221
Annotations in Data Streams....Pages 222-234
The Tile Complexity of Linear Assemblies....Pages 235-253
A Graph Reduction Step Preserving Element-Connectivity and Applications....Pages 254-265
Approximating Matches Made in Heaven....Pages 266-278
Strong and Pareto Price of Anarchy in Congestion Games....Pages 279-291
A Better Algorithm for Random k -SAT....Pages 292-303
Exact and Approximate Bandwidth....Pages 304-315
Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs....Pages 316-327
Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs....Pages 328-340
On Cartesian Trees and Range Minimum Queries....Pages 341-353
Applications of a Splitting Trick....Pages 354-365
Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness....Pages 366-377
Incompressibility through Colors and IDs....Pages 378-389
Partition Arguments in Multiparty Communication Complexity....Pages 390-402
High Complexity Tilings with Sparse Errors....Pages 403-414
Tight Bounds for the Cover Time of Multiple Random Walks....Pages 415-426
Online Computation with Advice....Pages 427-438
Dynamic Succinct Ordered Trees....Pages 439-450
Universal Succinct Representations of Trees?....Pages 451-462
Distortion Is Fixed Parameter Tractable....Pages 463-474
Towards Optimal Range Medians....Pages 475-486
B-Treaps: A Uniquely Represented Alternative to B-Trees....Pages 487-499
Testing Fourier Dimensionality and Sparsity....Pages 500-512
Revisiting the Direct Sum Theorem and Space Lower Bounds in Random Order Streams....Pages 513-524
Wireless Communication Is in APX....Pages 525-536
The Ehrenfeucht-Silberger Problem....Pages 537-548
Applications of Effective Probability Theory to Martin-Löf Randomness....Pages 549-561
An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables....Pages 562-573
Popular Mixed Matchings....Pages 574-584
Factoring Groups Efficiently....Pages 585-596
On Finding Dense Subgraphs....Pages 597-608
Learning Halfspaces with Malicious Noise....Pages 609-621
General Scheme for Perfect Quantum Network Coding with Free Classical Communication....Pages 622-633
Greedy ${\ensuremath{\Delta}}$ -Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost....Pages 634-652
Limits and Applications of Group Algebras for Parameterized Problems....Pages 653-664
Sleep with Guilt and Work Faster to Minimize Flow Plus Energy....Pages 665-676
Improved Bounds for Flow Shop Scheduling....Pages 677-688
A 3/2-Approximation Algorithm for General Stable Marriage....Pages 689-700
Limiting Negations in Formulas....Pages 701-712
Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems....Pages 713-725
Superhighness and Strong Jump Traceability....Pages 726-737
Amortized Communication Complexity of Distributions....Pages 738-749
The Number of Symbol Comparisons in QuickSort and QuickSelect....Pages 750-763
Computing the Girth of a Planar Graph in O ( n log n ) Time....Pages 764-773
Elimination Graphs....Pages 774-785
Back Matter....Pages -