Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, Bettina Speckmann
Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, Part I
ICALP (1), 2015.

@proceedings{ICALP-v1-2015,
	address       = "Kyoto, Japan",
	doi           = "10.1007/978-3-662-47672-7",
	editor        = "Magnús M. Halldórsson and Kazuo Iwama and Naoki Kobayashi and Bettina Speckmann",
	isbn          = "978-3-662-47671-0",
	publisher     = "{Springer International Publishing}",
	series        = "{Lecture Notes in Computer Science}",
	title         = "{Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, Part I}",
	volume        = 9134,
	year          = 2015,
}

Contents (89 items)

14 ×#algorithm
13 ×#approximate
11 ×#graph
10 ×#problem
8 ×#complexity
7 ×#bound
6 ×#on the
5 ×#constraints
5 ×#set
4 ×#linear

ICALP-v1-2015-AgrawalIKP #complexity #encoding #perspective #random #statistics

Statistical Randomized Encodings: A Complexity Theoretic View (SA, YI, DK, APC), pp. 1–13.

ICALP-v1-2015-Ailon #bound #fourier

Tighter Fourier Transform Lower Bounds (NA), pp. 14–25.

ICALP-v1-2015-AlbersF #locality

Quantifying Competitiveness in Paging with Locality of Reference (SA, DF), pp. 26–38.

ICALP-v1-2015-AmanatidisMNS #algorithm #approximate

Approximation Algorithms for Computing Maximin Share Allocations (GA, EM, AN, AS), pp. 39–51.

ICALP-v1-2015-AnshelevichKS #approximate #scalability

Envy-Free Pricing in Large Markets: Approximating Revenue and Welfare (EA, KK, SS), pp. 52–64.

ICALP-v1-2015-AronovK #algebra #diagrams #tool support

Batched Point Location in SINR Diagrams via Algebraic Tools (BA, MJK), pp. 65–77.

ICALP-v1-2015-Avigdor-Elgrabli #on the #order #random

On the Randomized Competitive Ratio of Reordering Buffer Management with Non-Uniform Costs (NAE, SI, BM, YR), pp. 78–90.

ICALP-v1-2015-AzarC

Serving in the Dark should be done Non-Uniformly (YA, IRC), pp. 91–102.

ICALP-v1-2015-BeameLP #bound

Finding the Median (Obliviously) with Bounded Space (PB, VL, MP), pp. 103–115.

ICALP-v1-2015-BehsazFSS #algorithm #approximate #clustering

Approximation Algorithms for Min-Sum k-Clustering and Balanced k-Median (BB, ZF, MRS, RS), pp. 116–128.

ICALP-v1-2015-BeiCZ #constraints #linear #programming

Solving Linear Programming with Constraints Unknown (XB, NC, SZ), pp. 129–142.

ICALP-v1-2015-BeigiEG #distributed

Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources (SB, OE, AG), pp. 143–154.

ICALP-v1-2015-BerkholzG #algebra #graph #morphism #testing

Limitations of Algebraic Approaches to Graph Isomorphism Testing (CB, MG), pp. 155–166.

ICALP-v1-2015-BernsteinS #graph

Fully Dynamic Matching in Bipartite Graphs (AB, CS), pp. 167–179.

ICALP-v1-2015-BeyersdorffCMS #calculus

Feasible Interpolation for QBF Resolution Calculi (OB, LC, MM, AS), pp. 180–192.

ICALP-v1-2015-BhangaleKS #approximate #constraints #problem

Simultaneous Approximation of Constraint Satisfaction Problems (AB, SK, SS), pp. 193–205.

ICALP-v1-2015-BhattacharyaHI #algorithm #design

Design of Dynamic Algorithms via Primal-Dual Method (SB, MH, GFI), pp. 206–218.

ICALP-v1-2015-BienvenuDS #question #source code #what

What Percentage of Programs Halt? (LB, DD, AS), pp. 219–230.

ICALP-v1-2015-BjorklundDH #exponential #problem #random #set #strict

The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems (AB, HD, TH), pp. 231–242.

ICALP-v1-2015-BjorklundKKZ

Spotting Trees with Few Leaves (AB, VK, LK, MZ), pp. 243–255.

ICALP-v1-2015-BodirskyMM #constraints #integer #problem

Constraint Satisfaction Problems over the Integers with Successor (MB, BM, AM), pp. 256–267.

ICALP-v1-2015-BunT #approximate

Hardness Amplification and the Approximate Degree of Constant-Depth Circuits (MB, JT), pp. 268–280.

ICALP-v1-2015-BurtonMS #algorithm #complexity #invariant

Algorithms and Complexity for Turaev-Viro Invariants (BAB, CM, JS), pp. 281–293.

ICALP-v1-2015-Canonne #big data #testing

Big Data on the Rise? — Testing Monotonicity of Distributions (CLC), pp. 294–305.

ICALP-v1-2015-Cao #editing #parametricity

Unit Interval Editing is Fixed-Parameter Tractable (YC), pp. 306–317.

ICALP-v1-2015-ChekuriGQ #algorithm #streaming

Streaming Algorithms for Submodular Function Maximization (CC, SG, KQ), pp. 318–330.

ICALP-v1-2015-CohenH #multi #pseudo

Multilinear Pseudorandom Functions (AC, JH), pp. 331–342.

ICALP-v1-2015-CohenS

Zero-Fixing Extractors for Sub-Logarithmic Entropy (GC, IS), pp. 343–354.

ICALP-v1-2015-CoudronV #approximate #interactive #proving

Interactive Proofs with Approximately Commuting Provers (MC, TV), pp. 355–366.

ICALP-v1-2015-CsehHK

Popular Matchings with Two-Sided Preferences and One-Sided Ties (ÁC, CCH, TK), pp. 367–379.

ICALP-v1-2015-Curticapean #complexity #framework

Block Interpolation: A Framework for Tight Exponential-Time Counting Complexity (RC), pp. 380–392.

ICALP-v1-2015-CzyzowiczGKKSU #convergence #on the #protocol

On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols (JC, LG, AK, EK, PGS, PU), pp. 393–405.

ICALP-v1-2015-DisserKL #bidirectional #scheduling

Scheduling Bidirectional Traffic on a Path (YD, MK, EL), pp. 406–418.

ICALP-v1-2015-DoronT #approximate #graph #on the #probability #problem

On the Problem of Approximating the Eigenvalues of Undirected Graphs in Probabilistic Logspace (DD, ATS), pp. 419–431.

ICALP-v1-2015-DvorakK #csp #on the

On Planar Boolean CSP (ZD, MK), pp. 432–443.

ICALP-v1-2015-Erlebach0K #graph #on the

On Temporal Graph Exploration (TE, MH, FK), pp. 444–455.

ICALP-v1-2015-FaonioNV

Mind Your Coins: Fully Leakage-Resilient Signatures with Graceful Degradation (AF, JBN, DV), pp. 456–468.

ICALP-v1-2015-FeldmannFKP #bound #graph

A (1+ε ) ( 1 + ε ) -Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs (AEF, WSF, JK, IP), pp. 469–480.

ICALP-v1-2015-FominGKM #bound #graph #morphism #problem

Lower Bounds for the Graph Homomorphism Problem (FVF, AG, ASK, IM), pp. 481–493.

ICALP-v1-2015-FominKLPS #algorithm #polynomial

Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree (FVF, PK, DL, FP, SS), pp. 494–505.

ICALP-v1-2015-FontesJKLLR #communication #complexity

Relative Discrepancy Does not Separate Information and Communication Complexity (LF, RJ, IK, SL, ML, JR), pp. 506–516.

ICALP-v1-2015-FullaZ #constraints #infinity

A Galois Connection for Valued Constraint Languages of Infinite Size (PF, SZ), pp. 517–528.

ICALP-v1-2015-GalanisGJ #approximate

Approximately Counting H-Colourings is BIS-Hard (AG, LAG, MJ), pp. 529–541.

ICALP-v1-2015-Ganguly #polynomial

Taylor Polynomial Estimator for Estimating Frequency Moments (SG), pp. 542–553.

ICALP-v1-2015-GargMVY #multi #nash #symmetry

ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria (JG, RM, VVV, SY), pp. 554–566.

ICALP-v1-2015-GaspersS #algorithm #performance #set

Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets (SG, GBS), pp. 567–579.

ICALP-v1-2015-GawrychowskiMW #matrix #query

Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search (PG, SM, OW), pp. 580–592.

ICALP-v1-2015-GawrychowskiN #encoding

Optimal Encodings for Range Top- k k , Selection, and Min-Max (PG, PKN), pp. 593–604.

ICALP-v1-2015-GeorgiadisILP #graph

2-Vertex Connectivity in Directed Graphs (LG, GFI, LL, NP), pp. 605–616.

ICALP-v1-2015-GharibianS

Ground State Connectivity of Local Hamiltonians (SG, JS), pp. 617–628.

ICALP-v1-2015-GiannopoulouJLS #complexity #kernel

Uniform Kernelization Complexity of Hitting Forbidden Minors (ACG, BMPJ, DL, SS), pp. 629–641.

ICALP-v1-2015-0001GR #graph #morphism

Counting Homomorphisms to Square-Free Graphs, Modulo 2 (AG, LAG, DR), pp. 642–653.

ICALP-v1-2015-GoldbergGL #approximate

Approximately Counting Locally-Optimal Structures (LAG, RG, JL), pp. 654–665.

ICALP-v1-2015-GoldreichGR #branch #context-free grammar #proving #proximity #source code

Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs — (OG, TG, RDR), pp. 666–677.

ICALP-v1-2015-GrosseGKSS #algorithm #performance

Fast Algorithms for Diameter-Optimally Augmenting Paths (UG, JG, CK, MHMS, FS), pp. 678–688.

ICALP-v1-2015-HansenKTZ

Hollow Heaps (TDH, HK, RET, UZ), pp. 689–700.

ICALP-v1-2015-HemenwayW #linear

Linear-Time List Recovery of High-Rate Expander Codes (BH, MW), pp. 701–712.

ICALP-v1-2015-HenzingerKL #component #polynomial

Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time (MH, SK, VL), pp. 713–724.

ICALP-v1-2015-HenzingerKN #algorithm #graph #reachability

Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs (MH, SK, DN), pp. 725–736.

ICALP-v1-2015-ImM #order

Weighted Reordering Buffer Improved via Variants of Knapsack Covering Inequalities (SI, BM), pp. 737–748.

ICALP-v1-2015-JahanjouMV #reduction

Local Reductions (HJ, EM, EV), pp. 749–760.

ICALP-v1-2015-KaniewskiLW #complexity #query

Query Complexity in Expectation (JK, TL, RdW), pp. 761–772.

ICALP-v1-2015-KannanM0 #complexity #graph #query

Near-Linear Query Complexity for Graph Inference (SK, CM, HZ), pp. 773–784.

ICALP-v1-2015-KarpinskiLS #set

A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set (MK, AL, DS), pp. 785–796.

ICALP-v1-2015-KawaseKY #graph

Finding a Path in Group-Labeled Graphs with Two Labels Forbidden (YK, YK, YY), pp. 797–809.

ICALP-v1-2015-KayalKPS #bound

Lower Bounds for Sums of Powers of Low Degree Univariates (NK, PK, TP, CS), pp. 810–821.

ICALP-v1-2015-KhotS #approximate #using

Approximating CSPs Using LP Relaxation (SK, RS), pp. 822–833.

ICALP-v1-2015-KomarathSS #bound #finite

Comparator Circuits over Finite Bounded Posets (BK, JS, KSS), pp. 834–845.

ICALP-v1-2015-KozikO #algebra #constraints #problem

Algebraic Properties of Valued Constraint Satisfaction Problem (MK, JO), pp. 846–858.

ICALP-v1-2015-KunnemannM #approximate #comprehension #heuristic #towards

Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic (MK, BM), pp. 859–871.

ICALP-v1-2015-KurpiszLM #on the #problem

On the Hardest Problem Formulations for the 0/1 0 / 1 Lasserre Hierarchy (AK, SL, MM), pp. 872–885.

ICALP-v1-2015-LiP #fibonacci

Replacing Mark Bits with Randomness in Fibonacci Heaps (JL, JP), pp. 886–897.

ICALP-v1-2015-LiJ #problem

A PTAS for the Weighted Unit Disk Cover Problem (JL, YJ), pp. 898–909.

ICALP-v1-2015-HuangL #approximate #combinator #optimisation #probability #problem

Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points (LH, JL), pp. 910–921.

ICALP-v1-2015-LokshtanovMPS #linear

Deterministic Truncation of Linear Matroids (DL, PM, FP, SS), pp. 922–934.

ICALP-v1-2015-LokshtanovRS #algorithm #feedback #linear #set

Linear Time Parameterized Algorithms for Subset Feedback Vertex Set (DL, MSR, SS), pp. 935–946.

ICALP-v1-2015-MitchellPSW #algorithm

An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains (JSBM, VP, MS, HW), pp. 947–959.

ICALP-v1-2015-MolinaroWY #complexity

Amplification of One-Way Information Complexity via Codes and Noise Sensitivity (MM, DPW, GY), pp. 960–972.

ICALP-v1-2015-MomkeW #algorithm #approximate #problem

A (2+ε)-Approximation Algorithm for the Storage Allocation Problem (TM, AW), pp. 973–984.

ICALP-v1-2015-MouawadNPR #configuration management

Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas (AEM, NN, VP, VR), pp. 985–996.

ICALP-v1-2015-NayyeriS #distance

Computing the Fréchet Distance Between Polygons with Holes (AN, AS), pp. 997–1009.

ICALP-v1-2015-Nikolov #big data #database

An Improved Private Mechanism for Small Databases (AN), pp. 1010–1021.

ICALP-v1-2015-KariKMPS #np-hard #set #synthesis

Binary Pattern Tile Set Synthesis Is NP-hard (LK, SK, PÉM, MJP, SS), pp. 1022–1034.

ICALP-v1-2015-Sanyal #bound #fourier

Near-Optimal Upper Bound on Fourier Dimension of Boolean Functions in Terms of Fourier Sparsity (SS), pp. 1035–1045.

ICALP-v1-2015-SkorskiGP #predict

Condensed Unpredictability (MS, AG, KP), pp. 1046–1057.

ICALP-v1-2015-ThapperZ

Sherali-Adams Relaxations for Valued CSPs (JT, SZ), pp. 1058–1069.

ICALP-v1-2015-WangW #algorithm #online

Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm (YW, SCwW), pp. 1070–1081.

ICALP-v1-2015-WeinsteinW #communication #data type

The Simultaneous Communication of Disjointness with Applications to Data Streams (OW, DPW), pp. 1082–1093.

ICALP-v1-2015-Yu #algorithm #combinator #matrix #multi

An Improved Combinatorial Algorithm for Boolean Matrix Multiplication (HY), pp. 1094–1105.