Luca Aceto, Monika Henzinger, Jirí Sgall
Proceedings of the 38th International Colloquium on Automata, Languages and Programming, Part I
ICALP (1), 2011.

@proceedings{ICALP-v1-2011,
	address       = "Zurich, Switzerland",
	doi           = "10.1007/978-3-642-22006-7",
	editor        = "Luca Aceto and Monika Henzinger and Jirí Sgall",
	isbn          = "978-3-642-22005-0",
	publisher     = "{Springer International Publishing}",
	series        = "{Lecture Notes in Computer Science}",
	title         = "{Proceedings of the 38th International Colloquium on Automata, Languages and Programming, Part I}",
	volume        = 6755,
	year          = 2011,
}

Contents (66 items)

10 ×#problem
9 ×#bound
8 ×#algorithm
8 ×#approximate
8 ×#graph
6 ×#complexity
6 ×#on the
4 ×#game studies
4 ×#quantum
4 ×#set

ICALP-v1-2011-BermanBMRY #approximate #problem

Improved Approximation for the Directed Spanner Problem (PB, AB, KM, SR, GY), pp. 1–12.

ICALP-v1-2011-Laekhanukit #algorithm #approximate #low cost #set

An Improved Approximation Algorithm for Minimum-Cost Subset k-Connectivity — (BL), pp. 13–24.

ICALP-v1-2011-AdamaszekCLW #approximate #design #geometry #network

Approximation Schemes for Capacitated Geometric Network Design (AA, AC, AL, JOW), pp. 25–36.

ICALP-v1-2011-QianW #algorithm #online #problem

An O(logn)-Competitive Algorithm for Online Constrained Forest Problems (JQ, DPW), pp. 37–48.

ICALP-v1-2011-Zhang #bound #communication #complexity #on the #power of #quantum

On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity (SZ), pp. 49–60.

ICALP-v1-2011-AaronsonD #quantum

Advice Coins for Classical and Quantum Computation (SA, AD), pp. 61–72.

ICALP-v1-2011-ChaillouxKR #complexity #quantum

Quantum Commitments from Complexity Assumptions (AC, IK, BR), pp. 73–85.

ICALP-v1-2011-HarrowMS #quantum #reduction

Limitations on Quantum Dimensionality Reduction (AWH, AM, AJS), pp. 86–97.

ICALP-v1-2011-CanzarEKM #on the

On Tree-Constrained Matchings and Generalizations (SC, KME, GWK, JM), pp. 98–109.

ICALP-v1-2011-AdlerKKLST #bound #graph

Tight Bounds for Linkages in Planar Graphs (IA, SGK, PKK, DL, SS, DMT), pp. 110–121.

ICALP-v1-2011-ChimaniH #approximate

A Tighter Insertion-Based Approximation of the Crossing Number (MC, PH), pp. 122–134.

ICALP-v1-2011-KawarabayashiKS #approximate #bound #distance #graph

Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs (KiK, PNK, CS), pp. 135–146.

ICALP-v1-2011-BorosEFGMM #analysis #approximate #game studies #probability

Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes (EB, KME, MF, VG, KM, BM), pp. 147–158.

ICALP-v1-2011-DyerM #game studies

Pairwise-Interaction Games (MED, VM), pp. 159–170.

ICALP-v1-2011-ElsasserT #complexity

Settling the Complexity of Local Max-Cut (Almost) Completely (RE, TT), pp. 171–182.

ICALP-v1-2011-Nonner #clique #clustering #graph

Clique Clustering Yields a PTAS for max-Coloring Interval Graphs (TN), pp. 183–194.

ICALP-v1-2011-EpsteinILN #on the

On Variants of File Caching (LE, CI, AL, JNG), pp. 195–206.

ICALP-v1-2011-BockenhauerKKK #complexity #on the #problem

On the Advice Complexity of the k-Server Problem (HJB, DK, RK, RK), pp. 207–218.

ICALP-v1-2011-ChanLLLT #energy #multi

Sleep Management on Multiple Machines for Energy and Flow Time (SHC, TWL, LKL, CML, HFT), pp. 219–231.

ICALP-v1-2011-AnandGM #how #question

Meeting Deadlines: How Much Speed Suffices? (SA, NG, NM), pp. 232–243.

ICALP-v1-2011-DurocherHMNS #constant #linear

Range Majority in Constant Time and Linear Space (SD, MH, JIM, PKN, MS), pp. 244–255.

ICALP-v1-2011-BrodalT #query

Dynamic Planar Range Maxima Queries (GSB, KT), pp. 256–267.

ICALP-v1-2011-FarzanK #distance #graph #navigation

Compact Navigation and Distance Oracles for Graphs with Small Treewidth (AF, SK), pp. 268–280.

ICALP-v1-2011-HirtZ

Player-Centric Byzantine Agreement (MH, VZ), pp. 281–292.

ICALP-v1-2011-AllenderFG #power of #random #string

Limits on the Computational Power of Random Strings (EA, LF, WIG), pp. 293–304.

ICALP-v1-2011-Coja-OghlanP #process #random #satisfiability

The Decimation Process in Random k-SAT (ACO, AYPP), pp. 305–316.

ICALP-v1-2011-MagniezNSX #bound #complexity #random #recursion

Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority (FM, AN, MS, DX), pp. 317–329.

ICALP-v1-2011-ODonnellWZ #fourier

The Fourier Entropy-Influence Conjecture for Certain Classes of Boolean Functions (RO, JW, YZ), pp. 330–341.

ICALP-v1-2011-FeldmanNS #algorithm

Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm — (MF, JN, RS), pp. 342–353.

ICALP-v1-2011-ChekuriE #problem

Submodular Cost Allocation Problem and Applications (CC, AE), pp. 354–366.

ICALP-v1-2011-KakimuraM #independence #robust

Robust Independence Systems (NK, KM), pp. 367–378.

ICALP-v1-2011-Varadaraja #approximate #problem

Buyback Problem — Approximate Matroid Intersection with Cancellation Costs (ABV), pp. 379–390.

ICALP-v1-2011-FaustPV #how

Tamper-Proof Circuits: How to Trade Leakage for Tamper-Resilience (SF, KP, DV), pp. 391–402.

ICALP-v1-2011-AroraG #algorithm #fault #learning

New Algorithms for Learning in Presence of Errors (SA, RG), pp. 403–415.

ICALP-v1-2011-HarkinsH #algorithm #bound #game studies #learning

Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds (RCH, JMH), pp. 416–423.

ICALP-v1-2011-BulatovM #constraints

Constraint Satisfaction Parameterized by Solution Size (AAB, DM), pp. 424–436.

ICALP-v1-2011-BodlaenderJK #analysis #combinator #kernel #preprocessor

Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization (HLB, BMPJ, SK), pp. 437–448.

ICALP-v1-2011-CyganPPW #feedback #parametricity #set

Subset Feedback Vertex Set Is Fixed-Parameter Tractable (MC, MP, MP, JOW), pp. 449–461.

ICALP-v1-2011-HermelinMLW

Domination When the Stars Are Out (DH, MM, EJvL, GJW), pp. 462–473.

ICALP-v1-2011-AustrinK #distance #problem #reduction

A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem (PA, SK), pp. 474–485.

ICALP-v1-2011-FeigeR #independence #set

Recoverable Values for Independent Sets (UF, DR), pp. 486–497.

ICALP-v1-2011-KuhnM #graph

Vertex Cover in Graphs with Locally Few Colors (FK, MM), pp. 498–509.

ICALP-v1-2011-MakarychevS #constraints

Maximizing Polynomials Subject to Assignment Constraints (KM, MS), pp. 510–520.

ICALP-v1-2011-GoldbergJ #algorithm #polynomial

A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid (LAG, MJ), pp. 521–532.

ICALP-v1-2011-BordewichK #agile #bound #graph #set

Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width (MB, RJK), pp. 533–544.

ICALP-v1-2011-ChakrabortyGM #performance

Efficient Sample Extractors for Juntas with Applications (SC, DGS, AM), pp. 545–556.

ICALP-v1-2011-NgoPR #matrix

Efficiently Decodable Error-Correcting List Disjunct Matrices and Applications — (HQN, EP, AR), pp. 557–568.

ICALP-v1-2011-FortnowS #robust #simulation

Robust Simulations and Significant Separations (LF, RS), pp. 569–580.

ICALP-v1-2011-Drucker

A PCP Characterization of AM (AD), pp. 581–592.

ICALP-v1-2011-CliffordJ #bound #integer #multi #online

Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model (RC, MJ), pp. 593–604.

ICALP-v1-2011-HuangP #game studies #probability

Automatizability and Simple Stochastic Games (LH, TP), pp. 605–617.

ICALP-v1-2011-FilmusPS #bound #exponential

Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds (YF, TP, RS), pp. 618–629.

ICALP-v1-2011-BeyersdorffGLR #bound

Parameterized Bounded-Depth Frege Is Not Optimal (OB, NG, ML, AAR), pp. 630–641.

ICALP-v1-2011-NordstromR #on the #satisfiability #trade-off

On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution (JN, AAR), pp. 642–653.

ICALP-v1-2011-BulteauFR #sorting

Sorting by Transpositions Is Difficult (LB, GF, IR), pp. 654–665.

ICALP-v1-2011-HuangK #problem

Popular Matchings in the Stable Marriage Problem (CCH, TK), pp. 666–677.

ICALP-v1-2011-ChengMS #graph

Center Stable Matchings and Centers of Cover Graphs of Distributive Lattices (CTC, EM, IS), pp. 678–689.

ICALP-v1-2011-AbrahamDFGW #algorithm

VC-Dimension and Shortest Path Algorithms (IA, DD, AF, AVG, RFFW), pp. 690–699.

ICALP-v1-2011-Mengel #constraints #problem

Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems — (SM), pp. 700–711.

ICALP-v1-2011-GuoLV #complexity #problem #symmetry

The Complexity of Symmetric Boolean Parity Holant Problems — (HG, PL, LGV), pp. 712–723.

ICALP-v1-2011-JansenS #constant #polynomial

Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth (MJJ, RS), pp. 724–735.

ICALP-v1-2011-AllenderW #algebra #branch #on the #power of #source code

On the Power of Algebraic Branching Programs of Width Two (EA, FW), pp. 736–747.

ICALP-v1-2011-Moldenhauer #algorithm #approximate #graph

Primal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs (CM), pp. 748–759.

ICALP-v1-2011-BermanBGRWY #transitive

Steiner Transitive-Closure Spanners of Low-Dimensional Posets (PB, AB, EG, SR, DPW, GY), pp. 760–772.

ICALP-v1-2011-DingX #clustering #problem

Solving the Chromatic Cone Clustering Problem via Minimum Spanning Sphere (HD, JX), pp. 773–784.

ICALP-v1-2011-LokshtanovM #clustering #strict

Clustering with Local Restrictions (DL, DM), pp. 785–797.