35. ICALP 2008: Reykjavik, Iceland - Part I

Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, Igor Walukiewicz (Eds.): Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games. Lecture Notes in Computer Science 5125 Springer 2008, ISBN 978-3-540-70574-1 BibTeX

Invited Lectures

Bruno Courcelle:
Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects. 1-13
Electronic Edition (link) BibTeX
S. Muthukrishnan:
Internet Ad Auctions: Insights and Directions. 14-23
Electronic Edition (link) BibTeX

Complexity: Boolean Functions and Circuits

David Buchfuhrer, Christopher Umans:
The Complexity of Boolean Formula Minimization. 24-35
Electronic Edition (link) BibTeX
Dana Dachman-Soled, Homin K. Lee, Tal Malkin, Rocco A. Servedio, Andrew Wan, Hoeteck Wee:
Optimal Cryptographic Hardness of Learning Monotone Functions. 36-47
Electronic Edition (link) BibTeX
Endre Boros, Khaled M. Elbassioni, Kazuhisa Makino:
On Berge Multiplication for Monotone Boolean Dualization. 48-59
Electronic Edition (link) BibTeX
Nitin Saxena:
Diagonal Circuit Identity Testing and Lower Bounds. 60-71
Electronic Edition (link) BibTeX

Data Structures

Yitong Yin:
Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity. 72-83
Electronic Edition (link) BibTeX
Milan Ruzic:
Constructing Efficient Dictionaries in Close to Sorting Time. 84-95
Electronic Edition (link) BibTeX
Susanne Albers, Sonja Lauer:
On List Update with Locality of Reference. 96-107
Electronic Edition (link) BibTeX
Guy E. Blelloch, Virginia Vassilevska, Ryan Williams:
A New Combinatorial Approach for Sparse Graph Problems. 108-120
Electronic Edition (link) BibTeX

Random Walks and Random Structures

Chen Avin, Michal Koucký, Zvi Lotker:
How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs). 121-132
Electronic Edition (link) BibTeX
Augustin Chaintreau, Pierre Fraigniaud, Emmanuelle Lebhar:
Networks Become Navigable as Nodes Move and Forget. 133-144
Electronic Edition (link) BibTeX
David Pritchard:
Fast Distributed Computation of Cuts Via Random Circulations. 145-160
Electronic Edition (link) BibTeX
Prasad Chebolu, Alan M. Frieze, Páll Melsted:
Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time. 161-172
Electronic Edition (link) BibTeX

Design and Analysis of Algorithms

Ferdinando Cicalese, Eduardo Sany Laber:
Function Evaluation Via Linear Programming in the Priced Information Model. 173-185
Electronic Edition (link) BibTeX
Yossi Azar, Benjamin E. Birnbaum, Anna R. Karlin, Claire Mathieu, C. Thach Nguyen:
Improved Approximation Algorithms for Budgeted Allocations. 186-197
Electronic Edition (link) BibTeX
Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto:
The Travelling Salesman Problem in Bounded Degree Graphs. 198-209
Electronic Edition (link) BibTeX
Fedor V. Fomin, Yngve Villanger:
Treewidth Computation and Extremal Combinatorics. 210-221
Electronic Edition (link) BibTeX

Scheduling

C. Greg Plaxton:
Fast Scheduling of Weighted Unit Jobs with Release Times and Deadlines. 222-233
Electronic Edition (link) BibTeX
Klaus Jansen, Ralf Thöle:
Approximation Algorithms for Scheduling Parallel Jobs: Breaking the Approximation Ratio of 2. 234-245
Electronic Edition (link) BibTeX
Friedrich Eisenbrand, Thomas Rothvoß:
A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation. 246-257
Electronic Edition (link) BibTeX

Codes and Coding

Noga Alon, Rani Hod:
Optimal Monotone Encodings. 258-270
Electronic Edition (link) BibTeX
Kazuo Iwama, Harumichi Nishimura, Mike Paterson, Rudy Raymond, Shigeru Yamashita:
Polynomial-Time Construction of Linear Network Coding. 271-282
Electronic Edition (link) BibTeX
Qi Cheng, Daqing Wan:
Complexity of Decoding Positive-Rate Reed-Solomon Codes. 283-293
Electronic Edition (link) BibTeX

Coloring

Jirí Fiala, Petr A. Golovach, Jan Kratochvíl:
Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract). 294-305
Electronic Edition (link) BibTeX
Sriram Pemmaraju, Aravind Srinivasan:
The Randomized Coloring Procedure with Symmetry-Breaking. 306-319
Electronic Edition (link) BibTeX
Flavio Chierichetti, Andrea Vattani:
The Local Nature of List Colorings for Graphs of High Girth. 320-332
Electronic Edition (link) BibTeX
Ken-ichi Kawarabayashi:
Approximating List-Coloring on a Fixed Surface. 333-344
Electronic Edition (link) BibTeX

Randomness in Computation

Markus Bläser, Moritz Hardt, David Steurer:
Asymptotically Optimal Hitting Sets Against Polynomials. 345-356
Electronic Edition (link) BibTeX
Alexandr Andoni, Robert Krauthgamer:
The Smoothed Complexity of Edit Distance. 357-369
Electronic Edition (link) BibTeX
Ming-Yang Kao, Robert T. Schweller:
Randomized Self-assembly for Approximate Shapes. 370-384
Electronic Edition (link) BibTeX
Martin Dietzfelbinger, Rasmus Pagh:
Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract). 385-396
Electronic Edition (link) BibTeX

Online and Dynamic Algorithms

Nedialko B. Dimitrov, C. Greg Plaxton:
Competitive Weighted Matching in Transversal Matroids. 397-408
Electronic Edition (link) BibTeX
Nikhil Bansal, Ho-Leung Chan, Tak Wah Lam, Lap-Kei Lee:
Scheduling for Speed Bounded Processors. 409-420
Electronic Edition (link) BibTeX
Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, Robert Endre Tarjan:
Faster Algorithms for Incremental Topological Ordering. 421-433
Electronic Edition (link) BibTeX
Gudmund Skovbjerg Frandsen, Piotr Sankowski:
Dynamic Normal Forms and Dynamic Characteristic Polynomial. 434-446
Electronic Edition (link) BibTeX

Approximation Algorithms

Jeff M. Phillips:
Algorithms for epsilon-Approximations of Terrains. 447-458
Electronic Edition (link) BibTeX
Eduardo Sany Laber, Marco Molinaro:
An Approximation Algorithm for Binary Searching in Trees. 459-471
Electronic Edition (link) BibTeX
Chandra Chekuri, Sanjeev Khanna:
Algorithms for 2-Route Cut Problems. 472-484
Electronic Edition (link) BibTeX
Glencora Borradaile, Philip N. Klein:
The Two-Edge Connectivity Survivable Network Problem in Planar Graphs. 485-501
Electronic Edition (link) BibTeX

Property Testing

Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Rocco A. Servedio, Andrew Wan:
Efficiently Testing Sparse GF(2) Polynomials. 502-514
Electronic Edition (link) BibTeX
Krzysztof Onak:
Testing Properties of Sets of Points in Metric Spaces. 515-526
Electronic Edition (link) BibTeX
Satyen Kale, C. Seshadhri:
An Expansion Tester for Bounded Degree Graphs. 527-538
Electronic Edition (link) BibTeX
Yuichi Yoshida, Hiro Ito:
Property Testing on k-Vertex-Connectivity of Graphs. 539-550
Electronic Edition (link) BibTeX

Parameterized Algorithms and Complexity

Igor Razgon, Barry O'Sullivan:
Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract). 551-562
Electronic Edition (link) BibTeX
Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin:
On Problems without Polynomial Kernels (Extended Abstract). 563-574
Electronic Edition (link) BibTeX
Ioannis Koutis:
Faster Algebraic Algorithms for Path and Packing Problems. 575-586
Electronic Edition (link) BibTeX
Yijia Chen, Marc Thurley, Mark Weyer:
Understanding the Complexity of Induced Subgraph Isomorphisms. 587-596
Electronic Edition (link) BibTeX

Graph Algorithms

Feodor F. Dragan, Fedor V. Fomin, Petr A. Golovach:
Spanners in Sparse Graphs. 597-608
Electronic Edition (link) BibTeX
Surender Baswana, Akshay Gaur, Sandeep Sen, Jayant Upadhyay:
Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error. 609-621
Electronic Edition (link) BibTeX
Liam Roditty, Asaf Shapira:
All-Pairs Shortest Paths with a Sublinear Additive Error. 622-633
Electronic Edition (link) BibTeX
Marc Tedder, Derek G. Corneil, Michel Habib, Christophe Paul:
Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations. 634-645
Electronic Edition (link) BibTeX

Computational Complexity

Andrei A. Bulatov:
The Complexity of the Counting Constraint Satisfaction Problem. 646-661
Electronic Edition (link) BibTeX
Andrei A. Krokhin, Dániel Marx:
On the Hardness of Losing Weight. 662-673
Electronic Edition (link) BibTeX
Troy Lee, Rajat Mittal:
Product Theorems Via Semidefinite Programming. 674-685
Electronic Edition (link) BibTeX
Eli Ben-Sasson, Prahladh Harsha, Oded Lachish, Arie Matsliah:
Sound 3-Query PCPPs Are Long. 686-697
Electronic Edition (link) BibTeX

Games and Automata

Javier Esparza, Thomas Gawlitza, Stefan Kiefer, Helmut Seidl:
Approximative Methods for Monotone Systems of Min-Max-Polynomial Equations. 698-710
Electronic Edition (link) BibTeX
Kousha Etessami, Dominik Wojtczak, Mihalis Yannakakis:
Recursive Stochastic Games with Positive Rewards. 711-723
Electronic Edition (link) BibTeX
Detlef Kähler, Thomas Wilke:
Complementation, Disambiguation, and Determinization of Büchi Automata Unified. 724-735
Electronic Edition (link) BibTeX
Gianluigi Greco, Francesco Scarcello:
Tree Projections: Hypergraph Games and Minimality. 736-747
Electronic Edition (link) BibTeX

Group Testing, Streaming, and Quantum

Ely Porat, Amir Rothschild:
Explicit Non-adaptive Combinatorial Group Testing Schemes. 748-759
Electronic Edition (link) BibTeX
Sudipto Guha, Andrew McGregor:
Tight Lower Bounds for Multi-pass Stream Computation Via Pass Elimination. 760-772
Electronic Edition (link) BibTeX
Oded Regev, Liron Schiff:
Impossibility of a Quantum Speed-Up with a Faulty Oracle. 773-781
Electronic Edition (link) BibTeX
Sean Hallgren, Aram Wettroth Harrow:
Superpolynomial Speedups Based on Almost Any Quantum Circuit. 782-795
Electronic Edition (link) BibTeX

Algorithmic Game Theory

Angelo Fanelli, Michele Flammini, Luca Moscardelli:
The Speed of Convergence in Congestion Games under Best-Response Dynamics. 796-807
Electronic Edition (link) BibTeX
Patrick Briest:
Uniform Budgets and the Envy-Free Pricing Problem. 808-819
Electronic Edition (link) BibTeX
George Christodoulou, Annamária Kovács, Michael Schapira:
Bayesian Combinatorial Auctions. 820-832
Electronic Edition (link) BibTeX
Yossi Azar, Iftah Gamzu:
Truthful Unification Framework for Packing Integer Programs with Choices. 833-844
Electronic Edition (link) BibTeX

Quantum

Julia Kempe, Oded Regev, Falk Unger, Ronald de Wolf:
Upper Bounds on the Noise Threshold for Fault-Tolerant Quantum Computing. 845-856
Electronic Edition (link) BibTeX
Mehdi Mhalla, Simon Perdrix:
Finding Optimal Flows Efficiently. 857-868
Electronic Edition (link) BibTeX
Andrew M. Childs, Troy Lee:
Optimal Quantum Adversary Lower Bounds for Ordered Search. 869-880
Electronic Edition (link) BibTeX
Lior Eldar, Oded Regev:
Quantum SAT for a Qutrit-Cinquit Pair Is QMA1-Complete. 881-892
Electronic Edition (link) BibTeX