Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, David Peleg
Proceedings of the 40th International Colloquium on Automata, Languages, and Programming, Part I
ICALP (1), 2013.

@proceedings{ICALP-v1-2013,
	address       = "Riga, Latvia",
	doi           = "10.1007/978-3-642-39206-1",
	editor        = "Fedor V. Fomin and Rusins Freivalds and Marta Z. Kwiatkowska and David Peleg",
	isbn          = "978-3-642-39205-4",
	publisher     = "{Springer International Publishing}",
	series        = "{Lecture Notes in Computer Science}",
	title         = "{Proceedings of the 40th International Colloquium on Automata, Languages, and Programming, Part I}",
	volume        = 7965,
	year          = 2013,
}

Contents (71 items)

14 ×#algorithm
9 ×#complexity
9 ×#graph
8 ×#bound
7 ×#on the
6 ×#random
5 ×#approximate
5 ×#linear
5 ×#polynomial
5 ×#problem

ICALP-v1-2013-AbboudL

Exact Weight Subgraphs and the k-Sum Conjecture (AA, KL), pp. 1–12.

ICALP-v1-2013-0002BFGK

Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines (SA, KB, TF, NG, AK), pp. 13–24.

ICALP-v1-2013-AndoniNPW #bound #linear #sketching

Tight Lower Bound for Linear Sketches of Moments (AA, HLN, YP, YW), pp. 25–32.

ICALP-v1-2013-AumullerD #clustering

Optimal Partitioning for Dual Pivot Quicksort — (MA, MD), pp. 33–44.

ICALP-v1-2013-AustrinKKM #algorithm #set #trade-off

Space-Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm (PA, PK, MK, JM), pp. 45–56.

ICALP-v1-2013-AvisT #combinator #complexity #on the

On the Extension Complexity of Combinatorial Polytopes (DA, HRT), pp. 57–68.

ICALP-v1-2013-BabenkoGGN #algorithm #optimisation

Algorithms for Hub Label Optimization (MAB, AVG, AG, VN), pp. 69–80.

ICALP-v1-2013-BateniHL #algorithm #approximate #problem

Improved Approximation Algorithms for (Budgeted) Node-Weighted Steiner Problems (MB, MH, VL), pp. 81–92.

ICALP-v1-2013-BauerCRW

Search-Space Size in Contraction Hierarchies (RB, TC, IR, DW), pp. 93–104.

ICALP-v1-2013-BelovsCJKM #3d #quantum

Time-Efficient Quantum Walks for 3-Distinctness (AB, AMC, SJ, RK, FM), pp. 105–122.

ICALP-v1-2013-BhattacharyyaY #algebra

An Algebraic Characterization of Testable Boolean CSPs (AB, YY), pp. 123–134.

ICALP-v1-2013-BienkowskiBCDNSSY #algorithm #approximate #problem

Approximation Algorithms for the Joint Replenishment Problem with Deadlines (MB, JB, MC, NBD, TN, MS, GS, NEY), pp. 135–147.

ICALP-v1-2013-BilleFGKSV

Sparse Suffix Tree Construction in Small Space (PB, JF, ILG, TK, BS, HWV), pp. 148–159.

ICALP-v1-2013-BilleGLW

Tree Compression with Top Trees (PB, ILG, GML, OW), pp. 160–171.

ICALP-v1-2013-Blaser #commutative

Noncommutativity Makes Determinants Hard (MB), pp. 172–183.

ICALP-v1-2013-BlasiusRW #graph #orthogonal

Optimal Orthogonal Graph Drawing with Convex Bend Costs (TB, IR, DW), pp. 184–195.

ICALP-v1-2013-BodlaenderCKN #algorithm #exponential #problem

Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth (HLB, MC, SK, JN), pp. 196–207.

ICALP-v1-2013-BohlerCKLPZ #complexity #diagrams #higher-order #on the

On the Complexity of Higher Order Abstract Voronoi Diagrams (CB, PC, RK, CHL, EP, MZ), pp. 208–219.

ICALP-v1-2013-BorosEGM #algorithm #game studies #probability #pseudo #random

A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and a Few Random Positions (EB, KME, VG, KM), pp. 220–231.

ICALP-v1-2013-BravermanRWY

Direct Product via Round-Preserving Compression (MB, AR, OW, AY), pp. 232–243.

ICALP-v1-2013-BravermanOV #how #question #streaming

How Hard Is Counting Triangles in the Streaming Model? (VB, RO, DV), pp. 244–254.

ICALP-v1-2013-BringmannDNS #online #worst-case

Online Checkpointing with Improved Worst-Case Guarantees (KB, BD, AN, JS), pp. 255–266.

ICALP-v1-2013-BringmannF #generative #geometry #graph #performance #random

Exact and Efficient Generation of Geometric Random Variates and Random Graphs (KB, TF), pp. 267–278.

ICALP-v1-2013-BrunschR #algorithm

Finding Short Paths on Polytopes by the Shadow Vertex Algorithm (TB, HR), pp. 279–290.

ICALP-v1-2013-BulanekKS #on the #online #random

On Randomized Online Labeling with Polynomially Many Labels (JB, MK, MES), pp. 291–302.

ICALP-v1-2013-BunT #approximate #bound

Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities (MB, JT), pp. 303–314.

ICALP-v1-2013-ChanLNS

New Doubling Spanners: Better and Simpler (THHC, ML, LN, SS), pp. 315–327.

ICALP-v1-2013-ChekuriNS #graph

Maximum Edge-Disjoint Paths in k-Sums of Graphs (CC, GN, FBS), pp. 328–339.

ICALP-v1-2013-CheriyanGGS #on the #symmetry

On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy (JC, ZG, KG, SS), pp. 340–351.

ICALP-v1-2013-Curticapean

Counting Matchings of Size k Is W[1]-Hard (RC), pp. 352–363.

ICALP-v1-2013-CyganP #algorithm #bound #graph #performance

Faster Exponential-Time Algorithms in Graphs of Bounded Average Degree (MC, MP), pp. 364–375.

ICALP-v1-2013-DeDS #algorithm #analysis #difference #fourier #geometry #robust

A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry (AD, ID, RAS), pp. 376–387.

ICALP-v1-2013-DemaineILO

Combining Binary Search Trees (EDD, JI, SL, ÖÖ), pp. 388–399.

ICALP-v1-2013-DemainePRSSW #assembly

The Two-Handed Tile Assembly Model Is Not Intrinsically Universal (EDD, MJP, TAR, RTS, SMS, DW), pp. 400–412.

ICALP-v1-2013-DinurG #clustering

Clustering in the Boolean Hypercube in a List Decoding Regime (ID, EG), pp. 413–424.

ICALP-v1-2013-DuanM #algorithm #combinator #linear #polynomial

A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market (RD, KM), pp. 425–436.

ICALP-v1-2013-FilmusLMNV #bound #calculus #comprehension #polynomial #towards

Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds — (YF, ML, MM, JN, MV), pp. 437–448.

ICALP-v1-2013-FotakisT #game studies #on the #power of

On the Power of Deterministic Mechanisms for Facility Location Games (DF, CT), pp. 449–460.

ICALP-v1-2013-GilbertNPRS

ℓ2/ℓ2-Foreach Sparse Recovery with Low Risk (ACG, HQN, EP, AR, MJS), pp. 461–472.

ICALP-v1-2013-GlasserNRSW #polynomial #reduction #set

Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions (CG, DTN, CR, ALS, MW), pp. 473–484.

ICALP-v1-2013-GolovachHKV #algorithm #incremental #polynomial #set

An Incremental Polynomial Time Algorithm to Enumerate All Minimal Edge Dominating Sets (PAG, PH, DK, YV), pp. 485–496.

ICALP-v1-2013-Grier #finite #game studies

Deciding the Winner of an Arbitrary Finite Poset Game Is PSPACE-Complete (DG), pp. 497–503.

ICALP-v1-2013-GrossiRRV #random #string

Dynamic Compressed Strings with Random Access (RG, RR, SRS, RV), pp. 504–515.

ICALP-v1-2013-GuoW #complexity #csp

The Complexity of Planar Boolean #CSP with Complex Weights (HG, TW), pp. 516–527.

ICALP-v1-2013-GurR #complexity #streaming

Arthur-Merlin Streaming Complexity (TG, RR), pp. 528–539.

ICALP-v1-2013-HemenwayOW

Local Correctability of Expander Codes (BH, RO, MW), pp. 540–551.

ICALP-v1-2013-HirtR #complexity #on the

On the Complexity of Broadcast Setup (MH, PR), pp. 552–563.

ICALP-v1-2013-IndykR #matrix #modelling #on the

On Model-Based RIP-1 Matrices (PI, IR), pp. 564–575.

ICALP-v1-2013-IshaiKLOPSZ #generative #pseudo #robust

Robust Pseudorandom Generators (YI, EK, XL, RO, MP, AS, DZ), pp. 576–588.

ICALP-v1-2013-JansenK #migration #online #polynomial #robust

A Robust AFPTAS for Online Bin Packing with Polynomial Migration, (KJ, KMK), pp. 589–600.

ICALP-v1-2013-KavithaV

Small Stretch Pairwise Spanners (TK, NMV), pp. 601–612.

ICALP-v1-2013-0002LPRRSS #algorithm #kernel #linear

Linear Kernels and Single-Exponential Algorithms via Protrusion Decompositions (EJK, AL, CP, FR, PR, IS, SS), pp. 613–624.

ICALP-v1-2013-Kolmogorov #linear #power of #programming

The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization (VK), pp. 625–636.

ICALP-v1-2013-KonradR #approximate #communication #streaming

Approximating Semi-matchings in Streaming and in Two-Party Communication (CK, AR), pp. 637–649.

ICALP-v1-2013-KucherovN #constant #realtime

Full-Fledged Real-Time Indexing for Constant Size Alphabets (GK, YN), pp. 650–660.

ICALP-v1-2013-KumarMN #bound

Arithmetic Circuit Lower Bounds via MaxRank (MK, GM, JS), pp. 661–672.

ICALP-v1-2013-Lampis #bound #graph #model checking

Model Checking Lower Bounds for Simple Graphs (ML), pp. 673–683.

ICALP-v1-2013-LauriaPRT #complexity #graph #proving

The Complexity of Proving That a Graph Is Ramsey (ML, PP, VR, NT), pp. 684–695.

ICALP-v1-2013-Leonardos #bound #complexity #random #recursion

An Improved Lower Bound for the Randomized Decision Tree Complexity of Recursive Majority, (NL), pp. 696–708.

ICALP-v1-2013-LeviR #graph

A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor (RL, DR), pp. 709–720.

ICALP-v1-2013-MarxV #algorithm #parametricity

Fixed-Parameter Algorithms for Minimum Cost Edge-Connectivity Augmentation (DM, LAV), pp. 721–732.

ICALP-v1-2013-MathieuZ #distance #graph #re-engineering

Graph Reconstruction via Distance Oracles (CM, HZ), pp. 733–744.

ICALP-v1-2013-MegowV #scheduling

Dual Techniques for Scheduling on a Machine with Varying Speed (NM, JV), pp. 745–756.

ICALP-v1-2013-MoruzN #algorithm #bound #random

Improved Space Bounds for Strongly Competitive Randomized Paging Algorithms (GM, AN), pp. 757–768.

ICALP-v1-2013-MuchaS #problem #scheduling #symmetry

No-Wait Flowshop Scheduling Is as Hard as Asymmetric Traveling Salesman Problem (MM, MS), pp. 769–779.

ICALP-v1-2013-ODonnellT #composition #fourier #theorem

A Composition Theorem for the Fourier Entropy-Influence Conjecture (RO, LYT), pp. 780–791.

ICALP-v1-2013-SviridenkoW #problem #scalability #set

Large Neighborhood Local Search for the Maximum Set Packing Problem (MS, JW), pp. 792–803.

ICALP-v1-2013-Uppman #complexity

The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom (HU), pp. 804–815.

ICALP-v1-2013-Velner #complexity #game studies #infinity

The Complexity of Infinitely Repeated Alternating Move Games (YV), pp. 816–827.

ICALP-v1-2013-WeimannY #approximate #graph #linear

Approximating the Diameter of Planar Graphs in Near Linear Time (OW, RY), pp. 828–839.

ICALP-v1-2013-WimmerY #invariant #morphism #testing

Testing Linear-Invariant Function Isomorphism (KW, YY), pp. 840–850.