Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, Paul G. Spirakis
Proceedings of the 37th International Colloquium on Automata, Languages and Programming, Part I
ICALP (1), 2010.

@proceedings{ICALP-v1-2010,
	address       = "Bordeaux, France",
	doi           = "10.1007/978-3-642-14165-2",
	editor        = "Samson Abramsky and Cyril Gavoille and Claude Kirchner and Friedhelm Meyer auf der Heide and Paul G. Spirakis",
	isbn          = "978-3-642-14164-5",
	publisher     = "{Springer International Publishing}",
	series        = "{Lecture Notes in Computer Science}",
	title         = "{Proceedings of the 37th International Colloquium on Automata, Languages and Programming, Part I}",
	volume        = 6198,
	year          = 2010,
}

Contents (62 items)

8 ×#on the
8 ×#problem
7 ×#algorithm
7 ×#approximate
5 ×#testing
4 ×#complexity
4 ×#graph
4 ×#performance
4 ×#polynomial
4 ×#scheduling

ICALP-v1-2010-MonienDT

Local Search: Simple, Successful, But Sometimes Sluggish (BM, DD, TT), pp. 1–17.

ICALP-v1-2010-Welzl #constraints #satisfiability

When Conflicting Constraints Can Be Resolved — The Lovász Local Lemma and Satisfiability (EW), p. 18.

ICALP-v1-2010-BonichonGHP

Plane Spanners of Maximum Degree Six (NB, CG, NH, LP), pp. 19–30.

ICALP-v1-2010-BrietFV #constraints #problem #rank

The Positive Semidefinite Grothendieck Problem with Rank Constraint (JB, FMdOF, FV), pp. 31–42.

ICALP-v1-2010-AmirELPS #detection

Cycle Detection and Correction (AA, EE, AL, EP, NS), pp. 43–54.

ICALP-v1-2010-Kral #composition

Decomposition Width of Matroids (DK), pp. 55–66.

ICALP-v1-2010-BateniHIM #game studies #network

The Cooperative Game Theory Foundations of Network Bargaining Games (MB, MH, NI, HM), pp. 67–78.

ICALP-v1-2010-HarksK #game studies #nash #on the

On the Existence of Pure Nash Equilibria in Weighted Congestion Games (TH, MK), pp. 79–89.

ICALP-v1-2010-BorodinL #combinator #design #on the

On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions (AB, BL), pp. 90–101.

ICALP-v1-2010-AtseriasM #game studies #proving

Mean-Payoff Games and Propositional Proofs (AA, ENM), pp. 102–113.

ICALP-v1-2010-AnagnostopoulosGLS #design #network #online

Online Network Design with Outliers (AA, FG, SL, PS), pp. 114–126.

ICALP-v1-2010-LibertY #encryption #performance

Efficient Completely Non-malleable Public Key Encryption (BL, MY), pp. 127–139.

ICALP-v1-2010-Ito #approximate #proving

Polynomial-Space Approximation of No-Signaling Provers (TI), pp. 140–151.

ICALP-v1-2010-ApplebaumIK #performance #verification

From Secrecy to Soundness: Efficient Verification via Secure Computation (BA, YI, EK), pp. 152–163.

ICALP-v1-2010-IaconoO

Mergeable Dictionaries (JI, ÖÖ), pp. 164–175.

ICALP-v1-2010-FakcharoenpholLN #algorithm #performance #problem

Faster Algorithms for Semi-matching Problems (JF, BL, DN), pp. 176–187.

ICALP-v1-2010-LiYZ #clustering

Clustering with Diversity (JL, KY, QZ), pp. 188–200.

ICALP-v1-2010-Duan #data type

New Data Structures for Subgraph Connectivity (RD), pp. 201–212.

ICALP-v1-2010-DietzfelbingerGMMPR #satisfiability

Tight Thresholds for Cuckoo Hashing via XORSAT (MD, AG, MM, AM, RP, MR), pp. 213–225.

ICALP-v1-2010-ColeR #multi #sorting

Resource Oblivious Sorting on Multicores (RC, VR), pp. 226–237.

ICALP-v1-2010-JimenezM #sorting

Interval Sorting (RMJ, CM), pp. 238–249.

ICALP-v1-2010-BansalK #problem #scheduling

Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems (NB, SK), pp. 250–261.

ICALP-v1-2010-GuptaNR #algorithm #optimisation #robust

Thresholded Covering Algorithms for Robust and Max-min Optimization (AG, VN, RR), pp. 262–274.

ICALP-v1-2010-CaiCL #graph #morphism #theorem

Graph Homomorphisms with Complex Values: A Dichotomy Theorem (JyC, XC, PL), pp. 275–286.

ICALP-v1-2010-BansalBN #problem

Metrical Task Systems and the k-Server Problem on HSTs (NB, NB, JN), pp. 287–298.

ICALP-v1-2010-EisenbrandHNSVW #realtime #scheduling

Scheduling Periodic Tasks in a Hard Real-Time Environment (FE, NH, MN, MS, JV, AW), pp. 299–311.

ICALP-v1-2010-GuptaKP #scheduling

Scalably Scheduling Power-Heterogeneous Processors (AG, RK, KP), pp. 312–323.

ICALP-v1-2010-BansalKN #algorithm #scalability #scheduling

Better Scalable Algorithms for Broadcast Scheduling (NB, RK, VN), pp. 324–335.

ICALP-v1-2010-EpsteinLS #online #order

Max-min Online Allocations with a Reordering Buffer (LE, AL, RvS), pp. 336–347.

ICALP-v1-2010-FountoulakisP #multi #power of #random

Orientability of Random Hypergraphs and the Power of Multiple Choices (NF, KP), pp. 348–359.

ICALP-v1-2010-GuruswamiS #on the

On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs (VG, RS), pp. 360–371.

ICALP-v1-2010-RueST #graph #programming

Dynamic Programming for Graphs on Surfaces (JR, IS, DMT), pp. 372–383.

ICALP-v1-2010-KoblerKLV #canonical #graph #representation

Interval Graphs: Canonical Representation in Logspace (JK, SK, BL, OV), pp. 384–395.

ICALP-v1-2010-GoldbergJ #approximate

Approximating the Partition Function of the Ferromagnetic Potts Model (LAG, MJ), pp. 396–407.

ICALP-v1-2010-ShpilkaV #on the #polynomial #testing

On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors (AS, IV), pp. 408–419.

ICALP-v1-2010-Litow #on the

On Sums of Roots of Unity (BEL), pp. 420–425.

ICALP-v1-2010-DellHW #complexity #exponential #polynomial

Exponential Time Complexity of the Permanent and the Tutte Polynomial (HD, TH, MW), pp. 426–437.

ICALP-v1-2010-BhattacharyaDMT #approximate #on the

On Approximate Horn Formula Minimization (AB, BD, DM, GT), pp. 438–450.

ICALP-v1-2010-BeimelDKW #communication #complexity

Choosing, Agreeing, and Eliminating in Communication Complexity (AB, SBD, EK, EW), pp. 451–462.

ICALP-v1-2010-Woodruff #polynomial

Additive Spanners in Nearly Quadratic Time (DPW), pp. 463–474.

ICALP-v1-2010-LeeZ #communication #complexity #composition #theorem

Composition Theorems in Communication Complexity (TL, SZ), pp. 475–489.

ICALP-v1-2010-GrandoniR #design #network #problem

Network Design via Core Detouring for Problems without a Core (FG, TR), pp. 490–502.

ICALP-v1-2010-Ambos-SpiesB #exponential

Weak Completeness Notions for Exponential Time (KAS, TB), pp. 503–514.

ICALP-v1-2010-BojanczykP #automaton #evaluation #nondeterminism #performance #using

Efficient Evaluation of Nondeterministic Automata Using Factorization Forests (MB, PP), pp. 515–526.

ICALP-v1-2010-JacobsCLM #complexity #on the

On the Complexity of Searching in Trees: Average-Case Minimization (TJ, FC, ESL, MM), pp. 527–539.

ICALP-v1-2010-KroviMOR #detection #quantum

Finding Is as Easy as Detecting for Quantum Walks (HK, FM, MO, JR), pp. 540–551.

ICALP-v1-2010-Cheraghchi #adaptation #testing

Improved Constructions for Non-adaptive Threshold Group Testing (MC), pp. 552–564.

ICALP-v1-2010-RubinfeldX #independence #testing

Testing Non-uniform k-Wise Independent Distributions over Product Spaces (RR, NX), pp. 565–581.

ICALP-v1-2010-GamzuS #approximate

A Sublogarithmic Approximation for Highway and Tollbooth Pricing (IG, DS), pp. 582–593.

ICALP-v1-2010-MakarychevMS #algorithm #approximate #polynomial #problem #reduction

Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-Based Approximation Algorithm (KM, RM, MS), pp. 594–604.

ICALP-v1-2010-GreveJLT #approximate #bound

Cell Probe Lower Bounds and Approximations for Range Mode (MG, AGJ, KDL, JT), pp. 605–616.

ICALP-v1-2010-GuruswamiKOPTW

SDP Gaps for 2-to-1 and Other Label-Cover Variants (VG, SK, RO, PP, MT, YW), pp. 617–628.

ICALP-v1-2010-RudraU #algorithm #data type #testing

Data Stream Algorithms for Codeword Testing (AR, SU), pp. 629–640.

ICALP-v1-2010-HalldorssonHLS #algorithm #independence #set #streaming

Streaming Algorithms for Independent Sets (BVH, MMH, EL, MS), pp. 641–652.

ICALP-v1-2010-KratschW #preprocessor #problem

Preprocessing of Min Ones Problems: A Dichotomy (SK, MW), pp. 653–665.

ICALP-v1-2010-Xia #artificial reality #reduction #theorem

Holographic Reduction: A Domain Changed Application and Its Partial Converse Theorems (MX), pp. 666–677.

ICALP-v1-2010-GrossiOR #string #trade-off

Optimal Trade-Offs for Succinct String Indexes (RG, AO, RR), pp. 678–689.

ICALP-v1-2010-GuptaNR10a #adaptation #algorithm #approximate #problem

Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems (AG, VN, RR), pp. 690–701.

ICALP-v1-2010-YaoYZ #concurrent

Concurrent Knowledge Extraction in the Public-Key Model (ACCY, MY, YZ), pp. 702–714.

ICALP-v1-2010-PatrascuT #independence #linear #on the

On the k-Independence Required by Linear Probing and Minwise Independence (MP, MT), pp. 715–726.

ICALP-v1-2010-BjorklundHKK #linear

Covering and Packing in Linear Space (AB, TH, PK, MK), pp. 727–737.

ICALP-v1-2010-Georgiadis #graph #testing

Testing 2-Vertex Connectivity and Computing Pairs of Vertex-Disjoint s-t Paths in Digraphs (LG), pp. 738–749.