ICALP 2016
12-15 July 2016, Rome, Italy
Accepted Papers
Accepted Papers for ICALP 2016 Track A: Algorithms, Complexity and Games
Semi-Streaming Algorithms for Annotated Graph Streams
Towards Tight Lower Bounds for Range
Reporting on the RAM
The Johnson-Lindenstrauss Lemma is Optimal
for Linear Dimensionality Reduction
Amplifiers for the Moran Process
All-Pairs Approximate Shortest Paths
and Distance Oracle Preprocessing
On isoperimetric profiles and computational
complexity
Boundaries of VP and VNP
Fractals for Kernelization Lower Bounds, With
an Application to Length-Bounded Cut Problems
Lower Bounds for the Approximate Degree of Block-Composed Functions
Subexponential Time Algorithms for Embedding
H-Minor Free Graphs
The Landscape of Communication
Complexity Classes
Fine-grained complexity analysis of two
classic TSP variants
Unified
Acceleration Method for Packing and Covering Problems via Diameter
Reduction
Approximation via Correlation
Decay when Strong Spatial Mixing Fails
A complexity
trichotomy for approximately counting list H-colourings
A Duality
Based 2-Approximation Algorithm for Maximum Agreement Forest
An almost Cubic Lower
Bound for Depth Three Arithmetic Circuits
Optimal quantum algorithm for polynomial interpolation
Coding for
interactive communication correcting insertions and deletions
A Fast Distributed Stateless Algorithm
for $\alpha$-Fair Packing Problems
Optimal approximate
matrix product in terms of stable rank
Simple average-case lower bounds
for approximate near-neighbor from isoperimetric inequalities
Improved Reduction from the Bounded Distance
Decoding Problem to the Unique Shortest Vector Problem in Lattices
Tight Analysis
of a Multiple-Swap Heurstic for Budgeted Red-Blue Median
The Complexity Landscape of Fixed-Parameter Directed Steiner Network
Problems
A parallel repetition theorem for all
entangled games
Faster Algorithms for Maximum Inscribed
Balls and Minimum Enclosing Balls
Approximate Span Programs
Do Distributed Differentially-Private
Protocols Require Oblivious Transfer?
On Percolation and
NP-Hardness
Approximation algorithms for aversion
k-clustering and local k-median
Space-Efficient Error Reduction for Unitary
Quantum Computations
Parity Separation: A Scientifically Proven
Method for Permanent Weight Loss
Impossibility of Sketching of the 3D
Transportation Metric with Quadratic Cost
Constant Congestion Routing of Symmetric
Demands in Planar Directed Graphs
Power of Quantum Computation with Few
Clean Qubits
Quasi-4-Connected
Components
Kernelization of Cycle Packing with Relaxed
Disjointness Constraints
Diameter
and k-Center in Sliding Windows
Robust Assignments
via Ear Decompositions and Randomized Rounding
Random-Edge is slower than Random-Facet
on abstract cubes
Beating the Harmonic lower bound for
online bin packing
On the Hardness of Partially Dynamic Graph Problems
and Connections to Diameter
Carpooling in
Social Networks
Closing the Gap for Makespan Scheduling via
Sparsification Techniques
Functional Commitment
Schemes: From Polynomial Commitments to Pairing-Based Accumulators
from Simple Assumptions
Data Structure Lower Bounds for Document
Indexing Problems
Approximate Hamming distance in a stream
Price of Competition and Dueling Games
Tight Sum-of-Squares lower bounds for
binary polynomial optimization problems
Information complexity is computable
Online Weighted Degree-Bounded Steiner
Networks via Novel Online Mixed Packing/Covering
Total space in Resolution is at least width
squared
Popular Half-integral Matchings
Look-ahead Non-malleable Codes
Voronoi Choice
Games
Relating Graph Thickness to Planar Layers
and Bend Complexity
The Non-Uniform k-Center Problem.
Provably Secure
Virus Detection: Using The Observer Effect Against Malware
Online Semidefinite Programming
k-center Clustering
under Perturbation Resilience
AC0(MOD2) lower bounds for the Boolean
inner product
Rényi
Information Complexity and an Information Theoretic Characterization
of the Partition Bound
Analysing Survey Propagation Guided Decimation
on Random Formulas
Double-exponential and triple-exponential
bounds for choosability problems parameterized by treewidth
Bicovering: Covering edges with two small
subsets of vertices
Supercritical Space-Width
Trade-offs for Resolution
Dynamic Graph Stream Algorithms in o(n)
Space
Incremental 2-Edge-Connectivity in Directed
Graphs
Randomization can be
as helpful as a glimpse of the future in online computation
Tight Hardness Results for Maximum Weight
Rectangles
An improved analysis of the ER-SpUD dictionary
learning algorithm
Lower Bounds for
Nondeterministic Semantic Read-Once Branching Programs
Randomized query complexity of sabotaged
and composed functions
On
the Sensitivity Conjecture
Quasimetric
embeddings and their applications
Improved Bounds on the Sign-Rank of AC^0
Approximation Algorithms for Clustering
Problems with Lower Bounds and Outliers
Constant Approximation for Capacitated k-Median
with (1+epsilon)-Capacity Violation
Tolerant Testers of Image Properties
Approximating the Solution to Mixed Packing
and Covering LPs in parallel $\tilde{O}(\epsilon^{-3})$ time
Approximating Directed Steiner Problems
via Tree Embedding
Mixing Time of Markov Chains, Dynamical
Systems and Evolution
Correlation Decay and Tractability of
CSPs
Linear time algorithm for quantum 2SAT
Erasure-Resilient
Property Testing
The Complexity
of Hex and the Jordan Curve Theorem
Deterministic Time-Space Tradeoffs for
k-SUM
Accepted Papers for ICALP 2016 Track B: Logic, Semantics, Automata and Theory of Programming
The decidable properties
of subrecursive functions
Polynomial Time
corresponds to Solutions of Polynomial Ordinary Differential Equations
of Polynomial Length. The General Purpose Analog Computer and Computable
Analysis are two efficiently equivalent models of computations
Proving the
Herman-Protocol Conjecture
Minimizing resources of sweeping and
streaming string transducers
On the Complexity
of Grammar-Based Compression over Fixed Alphabets
Deciding topological complexity of Buchi
languages
Characterizing classes
of regular languages using prefix codes of bounded synchronization
delay
Deciding Piecewise Testable Separability
for Regular Tree Languages
A Polynomial-Time Algorithm for Reachability
in Branching VASS in Dimension One
Algorithmic optimization for the realization
of an effective subshift by a sofic
Nesting Depth of Operators in Graph Database
Queries: Expressiveness Vs. Evaluation Complexity
On Word and Frontier Languages of Unsafe
Higher-Order Grammars
On the Skolem Problem
for Continuous Linear Dynamical Systems
Anti-Powers in Infinite
Words
A program
logic for union bounds b proving accuracy of differentially private
computations
Proof
Complexity Modulo the Polynomial Hierarchy: Understanding Alternation
as a Source of Hardness
Computation Tree Logic for Synchronization
Properties
Analysing decisive stochastic processes
A Linear
Acceleration Theorem for 2D Cellular Automata on all Complete Neighborhoods
Past,
Present, and Infinite Future
Solutions
of Word Equations over Partially Commutative Structures
The Complexity of Rational Synthesis
A Hierarchy of Local Decision
Reachability in Networks
of Register Protocols under Stochastic Schedulers
New Interpretation and Generalization
of the Kameda-Weiner Method
Constraint satisfaction problems for
reducts of homogeneous graphs
Composition of stochastic
transition systems based on spans and couplings
On Restricted Nonnegative
Matrix Factorization
Thin MSO with a probabilistic path quantifier
The Bridge Between
Regular Cost Functions and Omega-Regular Languages
On Equivalence
and Uniformisation Problems for Finite Transducers
The Sch\"{u}tzenberger product for Syntactic Spaces
Sensitivity of Counting Queries
The complexity of
downward closure comparisons
Logic of Local Inference for Contextuality in Quantum Physics and
Beyond
The Taming of the Semi-Linear Set
Accepted Papers for ICALP 2016 Track C: Foundations of Networked Computation: Models, Algorithms and Information Management
Distance labeling schemes for trees
Network of Complements
Discordant voting
processes on finite graphs
Competitive Analysis of Constrained Queueing Systems
Faster Deterministic
Communication in Radio Networks
Graph Minors
for Preserving Terminal Distances Approximately - Lower and Upper
Bounds
Partition bound is quadratically tight
for product distributions
Near Optimal Adjacency Labeling Schemes for
Power-Law Graphs
Reservation Exchange Markets for Internet Advertising
Fast, Robust, Quantizable Approximate
Consensus
Improved Protocols and Hardness Results
for the Two-Player Cryptogenography Problem
House Markets with Matroid and Knapsack
Constraints
Sublinear-Space
Bounded-Delay Enumeration for Massive Network Analytics: Maximal
Cliques
Bootstrap percolation on geometric inhomogeneous
random graphs
On the Resiliency
of Randomized Routing Against Multiple Edge Failures
On the Size and the Approximability of
Minimum Temporally Connected Subgraphs
Leader Election in
Unreliable Radio Networks
The Linear Voting Model
Bounds on the Voter Model in Dynamic
Networks
Efficient Plurality Consensus, or: The
benefits of cleaning up from time to time
An Optimal Dual Fault Tolerant Reachability
Oracle