default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID35th 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:
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 W. 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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2026-02-10 22:33 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
