Proceedings of the 35th International Colloquium on Automata, Languages and Programming, Track A: Algorithms, Automata, Complexity, and Games
BibSLEIGH corpus
BibSLEIGH tags
BibSLEIGH bundles
BibSLEIGH people
EDIT!
CC-BY
Open Knowledge
XHTML 1.0 W3C Rec
CSS 2.1 W3C CanRec
email twitter

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.

FLT
DBLP
Scholar
Full names Links ISxN
@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)

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.

Bibliography of Software Language Engineering in Generated Hypertext (BibSLEIGH) is created and maintained by Dr. Vadim Zaytsev.
Hosted as a part of SLEBOK on GitHub.