ICALP 2015 Accepted Papers for Track A: Algorithms, Complexity and Games

Leslie Ann Goldberg, Rob Gysel and John Lapinskas. Approximately Counting Locally-Optimal Structures
Andreas Göbel, Leslie Ann Goldberg and David Richerby. Counting Homomorphisms to Square-Free Graphs, Modulo 2
Clément Canonne. Big Data on the Rise: Testing monotonicity of distributions
Andreas Galanis, Leslie Ann Goldberg and Mark Jerrum. Approximately Counting H-Colourings is #BIS-Hard
Yossi Azar and Ilan Cohen. Serving in the Dark should be done Non-Uniformly
Sungjin Im and Benjamin Moseley. Weighted Reordering Buffer Improved via Variants of Knapsack Covering Inequalities
Jedrzej Kaniewski, Troy Lee and Ronald de Wolf. Query Complexity in expectation
Archontia Giannopoulou, Bart M. P. Jansen, Daniel Lokshtanov and Saket Saurabh. Uniform Kernelization Complexity of Hitting Forbidden Minors
Noa Avigdor-Elgrabli, Sungjin Im, Benjamin Moseley and Yuval Rabani. On the Randomized Competitive Ratio of Reordering Buffer Management with Non-Uniform Costs
Yixin Cao. Unit Interval Editing is Fixed-Parameter Tractable
Andreas Emil Feldmann, Jochen Koenemann, Isaac Fung and Ian Post. A (1 + ε)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs
Zdenek Dvorak and Martin Kupec. On Planar Boolean CSP
Amer Mouawad, Naomi Nishimura, Vinayak Pathak and Venkatesh Raman. Shortest reconfiguration paths in the solution space of Boolean formulas
Susanne Albers and Dario Frascaria. Quantifying Competitiveness in Paging with Locality of Reference
Thomas Dueholm Hansen, Haim Kaplan, Robert Tarjan and Uri Zwick. Hollow heaps
Jerry Li and John Peebles. Replacing Mark Bits with Randomness in Fibonacci Heaps
Dean Doron and Amnon Ta-Shma. On the Problem of Approximating the Eigenvalues of Undirected Graphs in Probabilistic Logspace
Nir Ailon. Tighter Fourier Transform Complexity Tradeoffs
Andreas Björklund, Holger Dell and Thore Husfeldt. The Parity of Set Systems under Random Restrictions with Applications to Exponential Time Problems
Andreas Björklund, Vikram Kamat, Lukasz Kowalik and Meirav Zehavi. Spotting Trees with Few Leaves
Sumit Ganguly. Taylor Polynomial Estimator for Estimating Frequency Moments
Xiaohui Bei, Ning Chen and Shengyu Zhang. Solving Linear Programming with Constraints Unknown
Fedor V Fomin, Petteri Kaski, Daniel Lokshtanov, Fahad Panolan and Saket Saurabh. Parameterized single-exponential time polynomial space algorithm for Steiner Tree
Fedor Fomin, Alexander Golovnev, Alexander Kulikov and Ivan Mihajlin. Lower Bounds for the Graph Homomorphism Problem
Swagato Sanyal. Near-optimal Upper Bound on Fourier dimension of Boolean Functions in terms of Fourier sparsity
Balagopal Komarath, Jayalal Sarma and K. S. Sunil. Comparator Circuits over Finite Bounded Posets
Salman Beigi, Omid Etesami and Amin Gohari. Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources
Omri Weinstein and David P. Woodruff. The Simultaneous Communication of Disjointness with Applications to Data Streams
Marek Karpinski, Andrzej Lingas and Dzmitry Sledneu. A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set
Oded Goldreich, Tom Gur and Ron Rothblum. Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs
Aaron Bernstein and Clifford Stein. Fully Dynamic Matching in Bipartite Graphs
Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan and Saket Saurabh. Deterministic Truncation of Linear Matroids
Jatin Batra, Tobias Mömke and Andreas Wiese. A (2+epsilon)-Approximation Algorithm for the Storage Allocation Problem
Paul Beame and Vincent Liew. Finding the Median (Obliviously) with Bounded Space
Agnes Cseh, Chien-Chung Huang and Telikepalli Kavitha. Popular matchings with one-sided ties
Sampath Kannan, Claire Mathieu and Hang Zhou. Near-Linear Query Complexity for Graph Inference
Sevag Gharibian and Jamie Sikora. Ground state connectivity of local Hamiltonians
Joseph Mitchell, Valentin Polishchuk, Mikko Sysikaski and Haitao Wang. An Optimal Algorithm for Minimum-Link Rectilinear Paths in Rectilinear Domains
Marvin Künnemann and Bodo Manthey. Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic
Mark Bun and Justin Thaler. Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
Ulrike Grosse, Joachim Gudmundsson, Christian Knauer, Michiel Smid and Fabian Stehn. Fast Algorithms for Diameter-Optimally Augmenting Trees
Boris Aronov and Matthew J. Katz. Batched Point Location in SINR Diagrams via Algebraic Tools
Brett Hemenway and Mary Wootters. Linear-time list recovery of high-rate expander codes
Babak Behsaz, Zachary Friggstad, Mohammad Salavatipour and Rohit Sivakumar. Approximation Algorithms for Min-Sum k-Clustering and Balanced k-Median
Monika Henzinger, Sebastian Krinninger and Danupon Nanongkai. Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
Yasushi Kawase, Yusuke Kobayashi and Yutaro Yamaguchi. Finding a Path in Group-Labeled Graphs with Two Labels Forbidden
Subhash Khot and Rishi Saket. Approximating CSPs using LP Relaxation
Sayan Bhattacharya, Monika Henzinger and Giuseppe F. Italiano. Design of Dynamic Algorithms via Primal-Dual Method
Huacheng Yu. An Improved Combinatorial Algorithm for Boolean Matrix Multiplication
Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura and Nikos Parotsidis. 2-Vertex Connectivity in Directed Graphs
Huang Lingxiao and Jian Li. Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points
Serge Gaspers and Gregory Sorkin. Separate, Measure and Conquer: Faster Algorithms for Max 2-CSP and Counting Dominating Sets
Thomas Erlebach, Michael Hoffmann and Frank Kammer. On Temporal Graph Exploration
Monika Henzinger, Sebastian Krinninger and Veronika Loitzenbauer. Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time
Jian Li and Yifei Jin. A PTAS for the Weighted Unit Disk Cover Problem
Olaf Beyersdorff, Leroy Chew, Meena Mahajan and Anil Shukla. Feasible Interpolation for QBF Resolution Calculi
Jugal Garg, Ruta Mehta, Vijay Vazirani and Sadra Yazdanbod. ETR-Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria
Lila Fontes, Rahul Jain, Iordanis Kerenidis, Mathieu Laurière, Sophie Laplante and Jérémie Roland. Relative discrepancy does not separate information and communication complexity
Radu Curticapean. Block interpolation: A framework for tight exponential-time counting complexity
Antonio Faonio, Jesper Buus Nielsen and Daniele Venturi. Mind Your Coins: Fully Leakage-Resilient Signatures with Graceful Degradation
Adam Kurpisz, Samuli Leppanen and Monaldo Mastrolilli. On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy
Matthew Patitz, Shinnosuke Seki, Pierre-Étienne Meunier, Lila Kari and Steffen Kopecki. Binary pattern tile set synthesis is NP-hard
Aloni Cohen and Justin Holmgren. Multilinear Pseudorandom Functions
Daniel Lokshtanov, Saket Saurabh and Ramanujan M. S.. Linear Time Parameterized Algorithms for SUBSET FEEDBACK VERTEX SET
Laurent Bienvenu, Damien Desfontaines and Alexander Shen. What percentage of programs halt?
Hamid Jahanjou, Eric Miles and Emanuele Viola. Local reductions
Chandra Chekuri, Shalmoli Gupta and Kent Quanrud. Streaming Algorithms for Submodular Function Maximization
Elliot Anshelevich, Koushik Kar and Shreyas Sekar. Envy-Free Pricing in Large Markets: Approximating Revenue and Welfare
Manuel Bodirsky, Barnaby Martin and Antoine Mottet. Constraint Satisfaction Problems Over The Integers with Successor
Christoph Berkholz and Martin Grohe. Limitations of Algebraic Approaches to Graph Isomorphism Testing
Yann Disser, Max Klimm and Elisabeth Lübbecke. Scheduling Bidirectional Traffic on a Path
Peter Fulla and Stanislav Živný. A Galois Connection for Valued Constraint Languages of Infinite Size
Gil Cohen and Igor Shinkar. Zero-Fixing Extractors for Sub-Logarithmic Entropy
Maciej Skorski, Alexander Golovnev and Krzysztof Pietrzak. Condensed Unpredictability
Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad and Amin Saberi. Approximation Algorithms for Computing Maximin Share Allocations
Pawel Gawrychowski, Shay Mozes and Oren Weimann. Submatrix Maximum Queries in Monge Matrices are Equivalent to Predecessor Searching
Amir Nayyeri and Anastasios Sidiropoulos. Computing Frechet distance between higher-dimensional objects
Johan Thapper and Stanislav Živný. Sherali-Adams relaxations for valued CSPs
Neeraj Kayal, Pascal Koiran, Timothee Pecatte and Chandan Saha. Lower Bounds for sums of powers of low degree univariates
Shweta Agrawal, Yuval Ishai, Dakshita Khurana and Anat Paskin-Cherniavsky. Statistical Randomized Encodings: A Complexity Theoretic View
Amey Bhangale, Swastik Kopparty and Sushant Sachdeva. Simultaneous Approximation of Constraint Satisfaction Problems
Marcin Kozik and Joanna Ochremiak. Algebraic Properties of Valued Constraint Satisfaction Problem
Marco Molinaro, David Woodruff and Grigory Yaroslavtsev. Amplification of One-Way Information Complexity via Codes and Noise Sensitivity
Yajun Wang and Sam Chiu-Wai Wong. Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm
Aleksandar Nikolov. An Improved Private Mechanism for Small Databases
Jurek Czyzowicz, Leszek Gasieniec, Adrian Kosowski, Evangelos Kranakis, Paul Spirakis and Przemysław Uznański. On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols
Matthew Coudron and Thomas Vidick. Interactive proofs with approximately commuting provers
Benjamin A. Burton, Clément Maria and Jonathan Spreer. Algorithms and complexity for Turaev-Viro invariants
Pawel Gawrychowski and Patrick K. Nicholson. Optimal Encodings for Range Top-k, Selection, and Min-Max