Accepted Papers

Track A - Track B - Track C


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

Justin Thaler. Semi-Streaming Algorithms for Annotated Graph Streams
Allan Grønlund and Kasper Green Larsen. Towards Tight Lower Bounds for Range Reporting on the RAM
Kasper Green Larsen and Jelani Nelson. The Johnson-Lindenstrauss Lemma is Optimal for Linear Dimensionality Reduction
Andreas Galanis, Andreas Göbel, Leslie Ann Goldberg, John Lapinskas and David Richerby. Amplifiers for the Moran Process
Christian Sommer. All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing
Pavel Hrubes and Amir Yehudayoff. On isoperimetric profiles and computational complexity
Joshua Grochow, Ketan Mulmuley and Youming Qiao. Boundaries of VP and VNP
Till Fluschnik, Danny Hermelin, André Nichterlein and Rolf Niedermeier. Fractals for Kernelization Lower Bounds, With an Application to Length-Bounded Cut Problems
Justin Thaler. Lower Bounds for the Approximate Degree of Block-Composed Functions
Hans L. Bodlaender, Jesper Nederlof and Tom van der Zanden. Subexponential Time Algorithms for Embedding H-Minor Free Graphs
Mika Göös, Toniann Pitassi and Thomas Watson. The Landscape of Communication Complexity Classes
Mark de Berg, Kevin Buchin, Bart M. P. Jansen and Gerhard J. Woeginger. Fine-grained complexity analysis of two classic TSP variants
Di Wang, Satish Rao and Michael Mahoney. Unified Acceleration Method for Packing and Covering Problems via Diameter Reduction
Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Heng Guo and Daniel Štefankovič . Approximation via Correlation Decay when Strong Spatial Mixing Fails
Andreas Galanis, Leslie Ann Goldberg and Mark Jerrum. A complexity trichotomy for approximately counting list H-colourings
Frans Schalekamp, Anke van Zuylen and Suzanne van der Ster. A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest
Neeraj Kayal, Chandan Saha and Sébastien Tavenas. An almost Cubic Lower Bound for Depth Three Arithmetic Circuits
Andrew Childs, Wim Van Dam, Shih-Han Hung and Igor Shparlinski. Optimal quantum algorithm for polynomial interpolation
Mark Braverman, Ran Gelles, Jieming Mao and Rafail Ostrovsky. Coding for interactive communication correcting insertions and deletions
Jelena Marasevic, Clifford Stein and Gil Zussman. A Fast Distributed Stateless Algorithm for $\alpha$-Fair Packing Problems
Michael B. Cohen, Jelani Nelson and David P. Woodruff. Optimal approximate matrix product in terms of stable rank
Yitong Yin. Simple average-case lower bounds for approximate near-neighbor from isoperimetric inequalities
Shi Bai, Damien Stehle and Weiqiang Wen. Improved Reduction from the Bounded Distance Decoding Problem to the Unique Shortest Vector Problem in Lattices
Zachary Friggstad and Yifeng Zhang. Tight Analysis of a Multiple-Swap Heurstic for Budgeted Red-Blue Median
Andreas Emil Feldmann and Dániel Marx. The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems
Henry Yuen. A parallel repetition theorem for all entangled games
Zeyuan Allen-Zhu, Zhenyu Liao and Yang Yuan. Faster Algorithms for Maximum Inscribed Balls and Minimum Enclosing Balls
Tsuyoshi Ito and Stacey Jeffery. Approximate Span Programs
Vipul Goyal, Dakshita Khurana, Ilya Mironov, Omkant Pandey and Amit Sahai. Do Distributed Differentially-Private Protocols Require Oblivious Transfer?
Huck Bennett, Daniel Reichman and Igor Shinkar. On Percolation and NP-Hardness
Anupam Gupta-Speaker, Guru Guruganesh and Melanie Schmidt. Approximation algorithms for aversion k-clustering and local k-median
Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin, Tomoyuki Morimae and Harumichi Nishimura. Space-Efficient Error Reduction for Unitary Quantum Computations
Radu Curticapean. Parity Separation: A Scientifically Proven Method for Permanent Weight Loss
Alexandr Andoni, Assaf Naor and Ofer Neiman. Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost
Chandra Chekuri, Alina Ene and Marcin Pilipczuk. Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs
Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate and Seiichiro Tani. Power of Quantum Computation with Few Clean Qubits
Martin Grohe. Quasi-4-Connected Components
Akanksha Agrawal, Daniel Lokshtanov, Diptapriyo Majumdar, Amer Mouawad and Saket Saurabh. Kernelization of Cycle Packing with Relaxed Disjointness Constraints
Vincent Cohen-Addad, Chris Schwiegelshohn and Christian Sohler. Diameter and k-Center in Sliding Windows
David Adjiashvili, Viktor Bindewald and Dennis Michaels. Robust Assignments via Ear Decompositions and Randomized Rounding
Thomas Dueholm Hansen and Uri Zwick. Random-Edge is slower than Random-Facet on abstract cubes
Sandy Heydrich and Rob van Stee. Beating the Harmonic lower bound for online bin packing
Søren Dahlgaard. On the Hardness of Partially Dynamic Graph Problems and Connections to Diameter
Amos Fiat, Anna Karlin, Elias Koutsoupias, Claire Mathieu and Rotem Zach. Carpooling in Social Networks
Klaus Jansen, Kim-Manuel Klein and Jose Verschae. Closing the Gap for Makespan Scheduling via Sparsification Techniques
Benoit Libert, Somindu C. Ramanna and Moti Yung. Functional Commitment Schemes: From Polynomial Commitments to Pairing-Based Accumulators from Simple Assumptions
Peyman Afshani and Jesper Sindahl Nielsen. Data Structure Lower Bounds for Document Indexing Problems
Tatiana Starikovskaya and Raphael Clifford. Approximate Hamming distance in a stream
Sina Dehghani, Mohammadtaghi Hajiaghayi, Hamid Mahini and Saeed Seddighin. Price of Competition and Dueling Games
Samuli Leppänen, Adam Kurpisz and Monaldo Mastrolilli. Tight Sum-of-Squares lower bounds for binary polynomial optimization problems
Mark Braverman and Jon Schneider. Information complexity is computable
Sina Dehghani, Soheil Ehsani, Mohammadtaghi Hajiaghayi, Vahid Liaghat, Harald Racke and Saeed Seddighin. Online Weighted Degree-Bounded Steiner Networks via Novel Online Mixed Packing/Covering
Ilario Bonacina. Total space in Resolution is at least width squared
Telikepalli Kavitha. Popular Half-integral Matchings
Nishanth Chandran, Vipul Goyal, Pratyay Mukherjee, Omkant Pandey and Jalaj Upadhyay. Look-ahead Non-malleable Codes
Meena Boppana, Rani Hod, Michael Mitzenmacher and Tom Morgan. Voronoi Choice Games
Stephane Durocher and Debajyoti Mondal. Relating Graph Thickness to Planar Layers and Bend Complexity
Deeparnab Chakrabarty, Prachi Goyal and Ravishankar Krishnaswamy. The Non-Uniform k-Center Problem.
Vassilis Zikas, Rafail Ostrovsky and Richard Lipton. Provably Secure Virus Detection: Using The Observer Effect Against Malware
Noa Elad, Satyen Kale and Joseph Naor. Online Semidefinite Programming
Maria-Florina Balcan, Nika Haghtalab and Colin White. k-center Clustering under Perturbation Resilience
Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer and Ning Xie. AC0(MOD2) lower bounds for the Boolean inner product
Manoj Prabhakaran and Vinod M Prabhakaran. Rényi Information Complexity and an Information Theoretic Characterization of the Partition Bound
Samuel Hetterich. Analysing Survey Propagation Guided Decimation on Random Formulas
Dániel Marx and Valia Mitsou. Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth
Amey Bhangale, Rajiv Gandhi, Mohammadtaghi Hajiaghayi, Rohit Khandekar and Guy Kortsarz. Bicovering: Covering edges with two small subsets of vertices
Christoph Berkholz and Jakob Nordstrom. Supercritical Space-Width Trade-offs for Resolution
Zengfeng Huang and Pan Peng. Dynamic Graph Stream Algorithms in o(n) Space
Loukas Georgiadis, Giuseppe F. Italiano and Nikos Parotsidis. Incremental 2-Edge-Connectivity in Directed Graphs
Jesper W. Mikkelsen. Randomization can be as helpful as a glimpse of the future in online computation
Arturs Backurs, Nishanth Dikkala and Christos Tzamos. Tight Hardness Results for Maximum Weight Rectangles
Jaroslaw Blasiok and Jelani Nelson. An improved analysis of the ER-SpUD dictionary learning algorithm
Stephen Cook, Jeff Edmonds, Venkatesh Medabalimi and Toniann Pitassi. Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs
Shalev Ben-David and Robin Kothari. Randomized query complexity of sabotaged and composed functions
Avishay Tal. On the Sensitivity Conjecture
Facundo Memoli, Anastasios Sidiropoulos and Vijay Sridhar. Quasimetric embeddings and their applications
Mark Bun and Justin Thaler. Improved Bounds on the Sign-Rank of AC^0
Sara Ahmadian and Chaitanya Swamy. Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers
Gökalp Demirci and Shi Li. Constant Approximation for Capacitated k-Median with (1+epsilon)-Capacity Violation
Piotr Berman, Meiram Murzabulatov and Sofya Raskhodnikova. Tolerant Testers of Image Properties
Di Wang, Michael Mahoney, Satish Rao and Peng Zhang. Approximating the Solution to Mixed Packing and Covering LPs in parallel $\tilde{O}(\epsilon^{-3})$ time
Bundit Laekhanukit. Approximating Directed Steiner Problems via Tree Embedding
Ioannis Panageas and Nisheeth Vishnoi. Mixing Time of Markov Chains, Dynamical Systems and Evolution
Jonah Brown-Cohen and Prasad Raghavendra. Correlation Decay and Tractability of CSPs
Itai Arad, Miklos Santha, Aarthi Sundaram and Shengyu Zhang. Linear time algorithm for quantum 2SAT
Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta and Nithin Mahendra Varma. Erasure-Resilient Property Testing
Aviv Adler, Constantinos Daskalakis and Erik Demaine. The Complexity of Hex and the Jordan Curve Theorem
Andrea Lincoln, Virginia Vassilevska Williams, Joshua Wang and Ryan Williams. Deterministic Time-Space Tradeoffs for k-SUM
Jun Wan, Yu Xia, Liang Li and Thomas Moscibroda. Information Cascades on Arbitrary Topologies


Accepted Papers for ICALP 2016 Track B: Logic, Semantics, Automata and Theory of Programming

Mathieu Hoyrup. The decidable properties of subrecursive functions
Olivier Bournez, Daniel Graça and Amaury Pouly. 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
Maria Bruna, Radu Grigore, Stefan Kiefer, Joel Ouaknine and James Worrell. Proving the Herman-Protocol Conjecture
Félix Baschenis, Olivier Gauwin, Anca Muscholl and Gabriele Puppis. Minimizing resources of sweeping and streaming string transducers
Katrin Casel, Henning Fernau, Serge Gaspers, Benjamin Gras and Markus L. Schmid. On the Complexity of Grammar-Based Compression over Fixed Alphabets
Michał Skrzypczak and Igor Walukiewicz. Deciding topological complexity of Buchi languages
Volker Diekert and Tobias Walter. Characterizing classes of regular languages using prefix codes of bounded synchronization delay
Jean Goubault-Larrecq and Sylvain Schmitz. Deciding Piecewise Testable Separability for Regular Tree Languages
Stefan Göller, Christoph Haase, Ranko Lazic and Patrick Totzke. A Polynomial-Time Algorithm for Reachability in Branching VASS in Dimension One
Mathieu Sablik and Michael Schraudner. Algorithmic optimization for the realization of an effective subshift by a sofic
M. Praveen and B Srivathsan. Nesting Depth of Operators in Graph Database Queries: Expressiveness Vs. Evaluation Complexity
Kazuyuki Asada and Naoki Kobayashi. On Word and Frontier Languages of Unsafe Higher-Order Grammars
Ventsislav Chonev, Joel Ouaknine and James Worrell. On the Skolem Problem for Continuous Linear Dynamical Systems
Gabriele Fici, Antonio Restivo, Manuel Silva and Luca Quadro Zamboni. Anti-Powers in Infinite Words
Gilles Barthe, Marco Gaboardi, Benjamin Grégoire, Justin Hsu and Pierre-Yves Strub. A program logic for union bounds b proving accuracy of differentially private computations
Hubie Chen. Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness
Krishnendu Chatterjee and Laurent Doyen. Computation Tree Logic for Synchronization Properties
Nathalie Bertrand, Patricia Bouyer, Thomas Brihaye and Pierre Carlier. Analysing decisive stochastic processes
Victor Poupet and Anaël Grandjean. A Linear Acceleration Theorem for 2D Cellular Automata on all Complete Neighborhoods
Thomas Wilke. Past, Present, and Infinite Future
Volker Diekert, Artur Jeż and Manfred Kufleitner. Solutions of Word Equations over Partially Commutative Structures
Rodica Condurache, Emmanuel Filiot, Raffaella Gentilini and Jean-Francois Raskin. The Complexity of Rational Synthesis
Laurent Feuilloley, Pierre Fraigniaud and Juho Hirvonen. A Hierarchy of Local Decision
Patricia Bouyer, Nicolas Markey, Mickael Randour, Arnaud Sangnier and Daniel Stan. Reachability in Networks of Register Protocols under Stochastic Schedulers
Hellis Tamm. New Interpretation and Generalization of the Kameda-Weiner Method
Manuel Bodirsky, Barnaby Martin, Michael Pinsker and András Pongrácz. Constraint satisfaction problems for reducts of homogeneous graphs
Daniel Gburek, Christel Baier and Sascha Klüppelholz. Composition of stochastic transition systems based on spans and couplings
Dmitry Chistikov, Stefan Kiefer, Ines Marusic, Mahsa Shirmohammadi and James Worrell. On Restricted Nonnegative Matrix Factorization
Mikolaj Bojanczyk. Thin MSO with a probabilistic path quantifier
Thomas Colcombet and Nathanaël Fijalkow. The Bridge Between Regular Cost Functions and Omega-Regular Languages
Emmanuel Filiot, Ismaël Jecker, Christof Löding and Sarah Winter. On Equivalence and Uniformisation Problems for Finite Transducers
Mai Gehrke, Daniela Petrisan and Luca Reggio. The Sch\"{u}tzenberger product for Syntactic Spaces
Myrto Arapinis, Diego Figueira and Marco Gaboardi. Sensitivity of Counting Queries
Georg Zetzsche. The complexity of downward closure comparisons
Kohei Kishida. Logic of Local Inference for Contextuality in Quantum Physics and Beyond
Dmitry Chistikov and Christoph Haase. The Taming of the Semi-Linear Set


Accepted Papers for ICALP 2016 Track C: Foundations of Networked Computation: Models, Algorithms and Information Management

Stephen Alstrup, Inge Li Gørtz, Esben Bistrup Halvorsen and Ely Porat. Distance labeling schemes for trees
Moshe Babaioff, Liad Blumrosen and Noam Nisan. Network of Complements
Colin Cooper, Alan Frieze, Nicolás Rivera and Martin Dyer. Discordant voting processes on finite graphs
Sungjin Im, Janardhan Kulkarni and Kamesh Munagala. Competitive Analysis of Constrained Queueing Systems
Artur Czumaj and Peter Davies. Faster Deterministic Communication in Radio Networks
Yun Kuen Cheung, Gramoz Goranci and Monika Henzinger. Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds
Prahladh Harsha, Rahul Jain and Jaikumar Radhakrishnan. Partition bound is quadratically tight for product distributions
Casper Petersen, Noy Rotbart, Jakob Grue-Simonsen and Christian Wulff-Nilsen. Near Optimal Adjacency Labeling Schemes for Power-Law Graphs
Gagan Goel, Stefano Leonardi, Vahab Mirrokni, Afshin Nikzad and Renato Paes-Leme. Reservation Exchange Markets for Internet Advertising
Bernadette Charron-Bost, Matthias Függer and Thomas Nowak. Fast, Robust, Quantizable Approximate Consensus
Benjamin Doerr and Marvin Künnemann. Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem
Piotr Krysta and Jinshan Zhang. House Markets with Matroid and Knapsack Constraints
Alessio Conte, Roberto Grossi, Andrea Marino and Luca Versari. Sublinear-Space Bounded-Delay Enumeration for Massive Network Analytics: Maximal Cliques
Christoph Koch and Johannes Lengler. Bootstrap percolation on geometric inhomogeneous random graphs
Marco Chiesa, Andrei Gurtov, Aleksander Madry, Slobodan Mitrovic, Ilya Nikolaevskiy, Michael Schapira and Scott Shenker. On the Resiliency of Randomized Routing Against Multiple Edge Failures
Kyriakos Axiotis and Dimitris Fotakis. On the Size and the Approximability of Minimum Temporally Connected Subgraphs
Mohsen Ghaffari and Calvin Newport. Leader Election in Unreliable Radio Networks
Nicolás Rivera and Colin Cooper. The Linear Voting Model
Petra Berenbrink, George Giakkoupis, Anne-Marie Kermarrec and Frederik Mallmann-Trenn. Bounds on the Voter Model in Dynamic Networks
Petra Berenbrink, Tom Friedetzky, George Giakkoupis and Peter Kling. Efficient Plurality Consensus, or: The benefits of cleaning up from time to time
Keerti Choudhary. An Optimal Dual Fault Tolerant Reachability Oracle