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

Invited Lectures

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

Complexity: Boolean Functions and Circuits

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

Data Structures

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

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
Augustin Chaintreau, Pierre Fraigniaud, Emmanuelle Lebhar:
Networks Become Navigable as Nodes Move and Forget. 133-144
David Pritchard:
Fast Distributed Computation of Cuts Via Random Circulations. 145-160
Prasad Chebolu, Alan M. Frieze, Páll Melsted:
Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time. 161-172

Design and Analysis of Algorithms

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

Scheduling

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

Codes and Coding

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

Coloring

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

Randomness in Computation

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

Online and Dynamic Algorithms

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

Approximation Algorithms

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

Property Testing

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

Parameterized Algorithms and Complexity

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

Graph Algorithms

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

Computational Complexity

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

Games and Automata

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

Group Testing, Streaming, and Quantum

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

Algorithmic Game Theory

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

Quantum

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

Last update Wed May 23 00:50:06 2012 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page