Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, Igor Walukiewicz
Proceedings of the 35th International Colloquium on Automata, Languages and Programming, Track A: Algorithms, Automata, Complexity, and Games
ICALP (1), 2008.

@proceedings{ICALP-A-2008,
	address       = "Reykjavik, Iceland",
	editor        = "Luca Aceto and Ivan Damgård and Leslie Ann Goldberg and Magnús M. Halldórsson and Anna Ingólfsdóttir and Igor Walukiewicz",
	isbn          = "978-3-540-70574-1",
	publisher     = "{Springer International Publishing}",
	series        = "{Lecture Notes in Computer Science}",
	title         = "{Proceedings of the 35th International Colloquium on Automata, Languages and Programming, Track A: Algorithms, Automata, Complexity, and Games}",
	volume        = 5125,
	year          = 2008,
}

Contents (72 items)

11 ×#graph
9 ×#problem
8 ×#approximate
7 ×#algorithm
7 ×#bound
7 ×#complexity
5 ×#performance
5 ×#quantum
5 ×#random
5 ×#testing

ICALP-A-2008-Courcelle #aspect-oriented #graph #higher-order #logic #monad

Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects (BC), pp. 1–13.

ICALP-A-2008-Muthukrishnan #internet

Internet Ad Auctions: Insights and Directions (SM), pp. 14–23.

ICALP-A-2008-BuchfuhrerU #complexity

The Complexity of Boolean Formula Minimization (DB, CU), pp. 24–35.

ICALP-A-2008-Dachman-SoledLMSWW #encryption #learning

Optimal Cryptographic Hardness of Learning Monotone Functions (DDS, HKL, TM, RAS, AW, HW), pp. 36–47.

ICALP-A-2008-BorosEM #multi #on the

On Berge Multiplication for Monotone Boolean Dualization (EB, KME, KM), pp. 48–59.

ICALP-A-2008-Saxena #bound #testing

Diagonal Circuit Identity Testing and Lower Bounds (NS), pp. 60–71.

ICALP-A-2008-Yin #complexity #nondeterminism #proving

Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity (YY), pp. 72–83.

ICALP-A-2008-Ruzic #performance #sorting

Constructing Efficient Dictionaries in Close to Sorting Time (MR), pp. 84–95.

ICALP-A-2008-AlbersL #locality #on the

On List Update with Locality of Reference (SA, SL), pp. 96–107.

ICALP-A-2008-BlellochVW #approach #combinator #graph #problem

A New Combinatorial Approach for Sparse Graph Problems (GEB, VV, RW), pp. 108–120.

ICALP-A-2008-AvinKL #evolution #graph #how #random

How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs) (CA, MK, ZL), pp. 121–132.

ICALP-A-2008-ChaintreauFL #network

Networks Become Navigable as Nodes Move and Forget (AC, PF, EL), pp. 133–144.

ICALP-A-2008-Pritchard #distributed #performance #random

Fast Distributed Computation of Cuts Via Random Circulations (DP), pp. 145–160.

ICALP-A-2008-CheboluFM #graph #random

Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time (PC, AMF, PM), pp. 161–172.

ICALP-A-2008-CicaleseL #evaluation #linear #programming

Function Evaluation Via Linear Programming in the Priced Information Model (FC, ESL), pp. 173–185.

ICALP-A-2008-AzarBKMN #algorithm #approximate

Improved Approximation Algorithms for Budgeted Allocations (YA, BEB, ARK, CM, CTN), pp. 186–197.

ICALP-A-2008-BjorklundHKK #bound #graph #problem

The Travelling Salesman Problem in Bounded Degree Graphs (AB, TH, PK, MK), pp. 198–209.

ICALP-A-2008-FominV #combinator

Treewidth Computation and Extremal Combinatorics (FVF, YV), pp. 210–221.

ICALP-A-2008-Plaxton #performance #scheduling

Fast Scheduling of Weighted Unit Jobs with Release Times and Deadlines (CGP), pp. 222–233.

ICALP-A-2008-JansenT #algorithm #approximate #parallel #scheduling

Approximation Algorithms for Scheduling Parallel Jobs: Breaking the Approximation Ratio of 2 (KJ, RT), pp. 234–245.

ICALP-A-2008-EisenbrandR #realtime #scheduling

A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation (FE, TR), pp. 246–257.

ICALP-A-2008-AlonH #encoding

Optimal Monotone Encodings (NA, RH), pp. 258–270.

ICALP-A-2008-IwamaNPRY #linear #network #polynomial

Polynomial-Time Construction of Linear Network Coding (KI, HN, MP, RR, SY), pp. 271–282.

ICALP-A-2008-ChengW #complexity

Complexity of Decoding Positive-Rate Reed-Solomon Codes (QC, DW), pp. 283–293.

ICALP-A-2008-FialaGK #complexity #distance #problem

Computational Complexity of the Distance Constrained Labeling Problem for Trees (JF, PAG, JK), pp. 294–305.

ICALP-A-2008-PemmarajuS #random #symmetry

The Randomized Coloring Procedure with Symmetry-Breaking (SVP, AS), pp. 306–319.

ICALP-A-2008-ChierichettiV #graph

The Local Nature of List Colorings for Graphs of High Girth (FC, AV), pp. 320–332.

ICALP-A-2008-Kawarabayashi #approximate

Approximating List-Coloring on a Fixed Surface (KiK), pp. 333–344.

ICALP-A-2008-BlaserHS #set

Asymptotically Optimal Hitting Sets Against Polynomials (MB, MH, DS), pp. 345–356.

ICALP-A-2008-AndoniK #complexity #distance #edit distance

The Smoothed Complexity of Edit Distance (AA, RK), pp. 357–369.

ICALP-A-2008-KaoS #approximate #random #self

Randomized Self-assembly for Approximate Shapes (MYK, RTS), pp. 370–384.

ICALP-A-2008-DietzfelbingerP #approximate #data type #retrieval

Succinct Data Structures for Retrieval and Approximate Membership (MD, RP), pp. 385–396.

ICALP-A-2008-DimitrovP

Competitive Weighted Matching in Transversal Matroids (NBD, CGP), pp. 397–408.

ICALP-A-2008-BansalCLL #bound #scheduling

Scheduling for Speed Bounded Processors (NB, HLC, TWL, LKL), pp. 409–420.

ICALP-A-2008-HaeuplerKMST #algorithm #incremental #performance

Faster Algorithms for Incremental Topological Ordering (BH, TK, RM, SS, RET), pp. 421–433.

ICALP-A-2008-FrandsenS #normalisation #polynomial

Dynamic Normal Forms and Dynamic Characteristic Polynomial (GSF, PS), pp. 434–446.

ICALP-A-2008-Phillips #algorithm #approximate

Algorithms for epsilon-Approximations of Terrains (JMP), pp. 447–458.

ICALP-A-2008-LaberM #algorithm #approximate

An Approximation Algorithm for Binary Searching in Trees (ESL, MM), pp. 459–471.

ICALP-A-2008-ChekuriK #algorithm #problem

Algorithms for 2-Route Cut Problems (CC, SK), pp. 472–484.

ICALP-A-2008-BorradaileK #graph #network #problem

The Two-Edge Connectivity Survivable Network Problem in Planar Graphs (GB, PNK), pp. 485–501.

ICALP-A-2008-DiakonikolasLMSW #testing

Efficiently Testing Sparse GF(2) Polynomials (ID, HKL, KM, RAS, AW), pp. 502–514.

ICALP-A-2008-Onak #metric #testing

Testing Properties of Sets of Points in Metric Spaces (KO), pp. 515–526.

ICALP-A-2008-KaleS #bound #graph

An Expansion Tester for Bounded Degree Graphs (SK, CS), pp. 527–538.

ICALP-A-2008-YoshidaI #graph #testing

Property Testing on k-Vertex-Connectivity of Graphs (YY, HI), pp. 539–550.

ICALP-A-2008-RazgonO #parametricity #satisfiability

Almost 2-SAT Is Fixed-Parameter Tractable (IR, BO), pp. 551–562.

ICALP-A-2008-BodlaenderDFH #kernel #on the #polynomial #problem

On Problems without Polynomial Kernels (HLB, RGD, MRF, DH), pp. 563–574.

ICALP-A-2008-Koutis #algebra #algorithm #performance #problem

Faster Algebraic Algorithms for Path and Packing Problems (IK), pp. 575–586.

ICALP-A-2008-ChenTW #complexity #comprehension #morphism

Understanding the Complexity of Induced Subgraph Isomorphisms (YC, MT, MW), pp. 587–596.

ICALP-A-2008-DraganFG #graph

Spanners in Sparse Graphs (FFD, FVF, PAG), pp. 597–608.

ICALP-A-2008-BaswanaGSU #constant #distance #fault #graph #polynomial

Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error (SB, AG, SS, JU), pp. 609–621.

ICALP-A-2008-RodittyS #fault #sublinear

All-Pairs Shortest Paths with a Sublinear Additive Error (LR, AS), pp. 622–633.

ICALP-A-2008-TedderCHP #composition #linear #permutation #recursion

Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations (MT, DGC, MH, CP), pp. 634–645.

ICALP-A-2008-Bulatov #complexity #constraints #problem

The Complexity of the Counting Constraint Satisfaction Problem (AAB), pp. 646–661.

ICALP-A-2008-KrokhinM #on the

On the Hardness of Losing Weight (AAK, DM), pp. 662–673.

ICALP-A-2008-LeeM #programming #theorem

Product Theorems Via Semidefinite Programming (TL, RM), pp. 674–685.

ICALP-A-2008-Ben-SassonHLM

Sound 3-Query PCPPs Are Long (EBS, PH, OL, AM), pp. 686–697.

ICALP-A-2008-EsparzaGKS #approximate #equation

Approximative Methods for Monotone Systems of Min-Max-Polynomial Equations (JE, TG, SK, HS), pp. 698–710.

ICALP-A-2008-EtessamiWY #game studies #probability #recursion

Recursive Stochastic Games with Positive Rewards (KE, DW, MY), pp. 711–723.

ICALP-A-2008-KahlerW #ambiguity #automaton

Complementation, Disambiguation, and Determinization of Büchi Automata Unified (DK, TW), pp. 724–735.

ICALP-A-2008-GrecoS #game studies

Tree Projections: Hypergraph Games and Minimality (GG, FS), pp. 736–747.

ICALP-A-2008-PoratR #adaptation #combinator #testing

Explicit Non-adaptive Combinatorial Group Testing Schemes (EP, AR), pp. 748–759.

ICALP-A-2008-GuhaM #bound #multi

Tight Lower Bounds for Multi-pass Stream Computation Via Pass Elimination (SG, AM), pp. 760–772.

ICALP-A-2008-RegevS #quantum

Impossibility of a Quantum Speed-Up with a Faulty Oracle (OR, LS), pp. 773–781.

ICALP-A-2008-HallgrenH #quantum

Superpolynomial Speedups Based on Almost Any Quantum Circuit (SH, AWH), pp. 782–795.

ICALP-A-2008-FanelliFM #convergence #game studies

The Speed of Convergence in Congestion Games under Best-Response Dynamics (AF, MF, LM), pp. 796–807.

ICALP-A-2008-Briest #problem

Uniform Budgets and the Envy-Free Pricing Problem (PB), pp. 808–819.

ICALP-A-2008-ChristodoulouKS #combinator

Bayesian Combinatorial Auctions (GC, AK, MS), pp. 820–832.

ICALP-A-2008-AzarG #framework #integer #source code #unification

Truthful Unification Framework for Packing Integer Programs with Choices (YA, IG), pp. 833–844.

ICALP-A-2008-KempeRUW #bound #fault tolerance #quantum

Upper Bounds on the Noise Threshold for Fault-Tolerant Quantum Computing (JK, OR, FU, RdW), pp. 845–856.

ICALP-A-2008-MhallaP

Finding Optimal Flows Efficiently (MM, SP), pp. 857–868.

ICALP-A-2008-ChildsL #bound #order #quantum

Optimal Quantum Adversary Lower Bounds for Ordered Search (AMC, TL), pp. 869–880.

ICALP-A-2008-EldarR #quantum #satisfiability

Quantum SAT for a Qutrit-Cinquit Pair Is QMA1-Complete (LE, OR), pp. 881–892.