ICALP 2015 Accepted Papers for Track A: Algorithms, Complexity and Games
Leslie Ann Goldberg, Rob Gysel and John Lapinskas. Approximately Counting Locally-Optimal Structures 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 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 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 Sumit Ganguly. Taylor Polynomial Estimator for Estimating Frequency Moments Fedor V Fomin, Petteri Kaski, Daniel Lokshtanov, Fahad Panolan and Saket Saurabh. Parameterized single-exponential time polynomial space algorithm for Steiner Tree Swagato Sanyal. Near-optimal Upper Bound on Fourier dimension of Boolean Functions in terms of Fourier sparsity
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
Aaron Bernstein and Clifford Stein. Fully Dynamic Matching in Bipartite Graphs 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
Sevag Gharibian and Jamie Sikora. Ground state connectivity of local Hamiltonians Marvin Künnemann and Bodo Manthey. Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic 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
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 Huacheng Yu. An Improved Combinatorial Algorithm for Boolean Matrix Multiplication Huang Lingxiao and Jian Li. Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points 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 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
Laurent Bienvenu, Damien Desfontaines and Alexander Shen. What percentage of programs halt? Hamid Jahanjou, Eric Miles and Emanuele Viola. Local reductions
Peter Fulla and Stanislav Živný. A Galois Connection for Valued Constraint Languages of Infinite Size 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 Johan Thapper and Stanislav Živný. Sherali-Adams relaxations for valued CSPs 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 Yajun Wang and Sam Chiu-Wai Wong. Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm
Matthew Coudron and Thomas Vidick. Interactive proofs with approximately commuting provers