| 2016 | 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy, July 11-15, 2016 Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, Davide Sangiorgi |
| 2016 | A Complexity Trichotomy for Approximately Counting List H-Colourings. Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum |
| 2016 | A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest. Frans Schalekamp, Anke van Zuylen, Suzanne van der Ster |
| 2016 | A Fast Distributed Stateless Algorithm for alpha-Fair Packing Problems. Jelena Marasevic, Clifford Stein, Gil Zussman |
| 2016 | A Hierarchy of Local Decision. Laurent Feuilloley, Pierre Fraigniaud, Juho Hirvonen |
| 2016 | A Linear Acceleration Theorem for 2D Cellular Automata on All Complete Neighborhoods. Anaël Grandjean, Victor Poupet |
| 2016 | A Parallel Repetition Theorem for All Entangled Games. Henry Yuen |
| 2016 | A Polynomial-Time Algorithm for Reachability in Branching VASS in Dimension One. Stefan Göller, Christoph Haase, Ranko Lazic, Patrick Totzke |
| 2016 | A Program Logic for Union Bounds. Gilles Barthe, Marco Gaboardi, Benjamin Grégoire, Justin Hsu, Pierre-Yves Strub |
| 2016 | AC^0 o MOD_2 Lower Bounds for the Boolean Inner Product. Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie |
| 2016 | Algorithmic Complexity for the Realization of an Effective Subshift By a Sofic. Mathieu Sablik, Michael Schraudner |
| 2016 | All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing. Christian Sommer |
| 2016 | Amplifiers for the Moran Process. Andreas Galanis, Andreas Göbel, Leslie Ann Goldberg, John Lapinskas, David Richerby |
| 2016 | An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits. Neeraj Kayal, Chandan Saha, Sébastien Tavenas |
| 2016 | An Improved Analysis of the ER-SpUD Dictionary Learning Algorithm. Jaroslaw Blasiok, Jelani Nelson |
| 2016 | An Optimal Dual Fault Tolerant Reachability Oracle. Keerti Choudhary |
| 2016 | Analysing Decisive Stochastic Processes. Nathalie Bertrand, Patricia Bouyer, Thomas Brihaye, Pierre Carlier |
| 2016 | Analysing Survey Propagation Guided Decimationon Random Formulas. Samuel Hetterich |
| 2016 | Anti-Powers in Infinite Words. Gabriele Fici, Antonio Restivo, Manuel Silva, Luca Q. Zamboni |
| 2016 | Approximate Hamming Distance in a Stream. Raphaël Clifford, Tatiana Starikovskaya |
| 2016 | Approximate Span Programs. Tsuyoshi Ito, Stacey Jeffery |
| 2016 | Approximating Directed Steiner Problems via Tree Embedding. Bundit Laekhanukit |
| 2016 | Approximating the Solution to Mixed Packing and Covering LPs in Parallel O˜(epsilon^{-3}) Time. Michael W. Mahoney, Satish Rao, Di Wang, Peng Zhang |
| 2016 | Approximation Algorithms for Aversion k-Clustering via Local k-Median. Anupam Gupta, Guru Guruganesh, Melanie Schmidt |
| 2016 | Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers. Sara Ahmadian, Chaitanya Swamy |
| 2016 | Approximation via Correlation Decay When Strong Spatial Mixing Fails. Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Daniel Stefankovic |
| 2016 | Beating the Harmonic Lower Bound for Online Bin Packing. Sandy Heydrich, Rob van Stee |
| 2016 | Bicovering: Covering Edges With Two Small Subsets of Vertices. Amey Bhangale, Rajiv Gandhi, Mohammad Taghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz |
| 2016 | Block-Wise Non-Malleable Codes. Nishanth Chandran, Vipul Goyal, Pratyay Mukherjee, Omkant Pandey, Jalaj Upadhyay |
| 2016 | Bootstrap Percolation on Geometric Inhomogeneous Random Graphs. Christoph Koch, Johannes Lengler |
| 2016 | Boundaries of VP and VNP. Joshua A. Grochow, Ketan D. Mulmuley, Youming Qiao |
| 2016 | Bounds on the Voter Model in Dynamic Networks. Petra Berenbrink, George Giakkoupis, Anne-Marie Kermarrec, Frederik Mallmann-Trenn |
| 2016 | Carpooling in Social Networks. Amos Fiat, Anna R. Karlin, Elias Koutsoupias, Claire Mathieu, Rotem Zach |
| 2016 | Characterizing Classes of Regular Languages Using Prefix Codes of Bounded Synchronization Delay. Volker Diekert, Tobias Walter |
| 2016 | Closing the Gap for Makespan Scheduling via Sparsification Techniques. Klaus Jansen, Kim-Manuel Klein, José Verschae |
| 2016 | Coding for Interactive Communication Correcting Insertions and Deletions. Mark Braverman, Ran Gelles, Jieming Mao, Rafail Ostrovsky |
| 2016 | Competitive Analysis of Constrained Queueing Systems. Sungjin Im, Janardhan Kulkarni, Kamesh Munagala |
| 2016 | Composition of Stochastic Transition Systems Based on Spans and Couplings. Daniel Gburek, Christel Baier, Sascha Klüppelholz |
| 2016 | Computation Tree Logic for Synchronization Properties. Krishnendu Chatterjee, Laurent Doyen |
| 2016 | Compute Choice. Devavrat Shah |
| 2016 | Constant Approximation for Capacitated k-Median with (1+epsilon)-Capacity Violation. H. Gökalp Demirci, Shi Li |
| 2016 | Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs. Chandra Chekuri, Alina Ene, Marcin Pilipczuk |
| 2016 | Constraint Satisfaction Problems for Reducts of Homogeneous Graphs. Manuel Bodirsky, Barnaby Martin, Michael Pinsker, András Pongrácz |
| 2016 | Correlation Decay and Tractability of CSPs. Jonah Brown-Cohen, Prasad Raghavendra |
| 2016 | Data Structure Lower Bounds for Document Indexing Problems. Peyman Afshani, Jesper Sindahl Nielsen |
| 2016 | Deciding Piecewise Testable Separability for Regular Tree Languages. Jean Goubault-Larrecq, Sylvain Schmitz |
| 2016 | Deciding the Topological Complexity of Büchi Languages. Michal Skrzypczak, Igor Walukiewicz |
| 2016 | Deterministic Time-Space Trade-Offs for k-SUM. Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, R. Ryan Williams |
| 2016 | Diameter and k-Center in Sliding Windows. Vincent Cohen-Addad, Chris Schwiegelshohn, Christian Sohler |
| 2016 | Discordant Voting Processes on Finite Graphs. Colin Cooper, Martin E. Dyer, Alan M. Frieze, Nicolas Rivera |
| 2016 | Distance Labeling Schemes for Trees. Stephen Alstrup, Inge Li Gørtz, Esben Bistrup Halvorsen, Ely Porat |
| 2016 | Do Distributed Differentially-Private Protocols Require Oblivious Transfer?. Vipul Goyal, Dakshita Khurana, Ilya Mironov, Omkant Pandey, Amit Sahai |
| 2016 | Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth. Dániel Marx, Valia Mitsou |
| 2016 | Dynamic Graph Stream Algorithms in o(n) Space. Zengfeng Huang, Pan Peng |
| 2016 | Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time. Petra Berenbrink, Tom Friedetzky, George Giakkoupis, Peter Kling |
| 2016 | Erasure-Resilient Property Testing. Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, Nithin Varma |
| 2016 | Fast, Robust, Quantizable Approximate Consensus. Bernadette Charron-Bost, Matthias Függer, Thomas Nowak |
| 2016 | Faster Deterministic Communication in Radio Networks. Artur Czumaj, Peter Davies |
| 2016 | Fine-Grained Complexity Analysis of Two Classic TSP Variants. Mark de Berg, Kevin Buchin, Bart M. P. Jansen, Gerhard J. Woeginger |
| 2016 | Formally Verifying a Compiler: What Does It Mean, Exactly? Xavier Leroy |
| 2016 | Fractals for Kernelization Lower Bounds, With an Application to Length-Bounded Cut Problems. Till Fluschnik, Danny Hermelin, André Nichterlein, Rolf Niedermeier |
| 2016 | Front Matter, Table of Contents, Preface, Organization, List of Authors. |
| 2016 | Functional Commitment Schemes: From Polynomial Commitments to Pairing-Based Accumulators from Simple Assumptions. Benoît Libert, Somindu C. Ramanna, Moti Yung |
| 2016 | Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds. Yun Kuen Cheung, Gramoz Goranci, Monika Henzinger |
| 2016 | Hardness of Approximation. Subhash Khot |
| 2016 | House Markets with Matroid and Knapsack Constraints. Piotr Krysta, Jinshan Zhang |
| 2016 | Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost. Alexandr Andoni, Assaf Naor, Ofer Neiman |
| 2016 | Improved Bounds on the Sign-Rank of AC^0. Mark Bun, Justin Thaler |
| 2016 | Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem. Benjamin Doerr, Marvin Künnemann |
| 2016 | Improved Reduction from the Bounded Distance Decoding Problem to the Unique Shortest Vector Problem in Lattices. Shi Bai, Damien Stehlé, Weiqiang Wen |
| 2016 | Incremental 2-Edge-Connectivity in Directed Graphs. Loukas Georgiadis, Giuseppe F. Italiano, Nikos Parotsidis |
| 2016 | Information Cascades on Arbitrary Topologies. Jun Wan, Yu Xia, Liang Li, Thomas Moscibroda |
| 2016 | Information Complexity Is Computable. Mark Braverman, Jon Schneider |
| 2016 | Kernelization of Cycle Packing with Relaxed Disjointness Constraints. Akanksha Agrawal, Daniel Lokshtanov, Diptapriyo Majumdar, Amer E. Mouawad, Saket Saurabh |
| 2016 | Leader Election in Unreliable Radio Networks. Mohsen Ghaffari, Calvin C. Newport |
| 2016 | Linear Time Algorithm for Quantum 2SAT. Itai Arad, Miklos Santha, Aarthi Sundaram, Shengyu Zhang |
| 2016 | Logic of Local Inference for Contextuality in Quantum Physics and Beyond. Kohei Kishida |
| 2016 | Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs. Stephen A. Cook, Jeff Edmonds, Venkatesh Medabalimi, Toniann Pitassi |
| 2016 | Lower Bounds for the Approximate Degree of Block-Composed Functions. Justin Thaler |
| 2016 | Minimizing Resources of Sweeping and Streaming String Transducers. Félix Baschenis, Olivier Gauwin, Anca Muscholl, Gabriele Puppis |
| 2016 | Mixing Time of Markov Chains, Dynamical Systems and Evolution. Ioannis Panageas, Nisheeth K. Vishnoi |
| 2016 | Model Checking and Strategy Synthesis for Stochastic Games: From Theory to Practice. Marta Z. Kwiatkowska |
| 2016 | Near Optimal Adjacency Labeling Schemes for Power-Law Graphs. Casper Petersen, Noy Rotbart, Jakob Grue Simonsen, Christian Wulff-Nilsen |
| 2016 | Nesting Depth of Operators in Graph Database Queries: Expressiveness vs. Evaluation Complexity. M. Praveen, B. Srivathsan |
| 2016 | Networks of Complements. Moshe Babaioff, Liad Blumrosen, Noam Nisan |
| 2016 | New Interpretation and Generalization of the Kameda-Weiner Method. Hellis Tamm |
| 2016 | On Equivalence and Uniformisation Problems for Finite Transducers. Emmanuel Filiot, Ismaël Jecker, Christof Löding, Sarah Winter |
| 2016 | On Isoperimetric Profiles and Computational Complexity. Pavel Hrubes, Amir Yehudayoff |
| 2016 | On Percolation and NP-Hardness. Huck Bennett, Daniel Reichman, Igor Shinkar |
| 2016 | On Restricted Nonnegative Matrix Factorization. Dmitry Chistikov, Stefan Kiefer, Ines Marusic, Mahsa Shirmohammadi, James Worrell |
| 2016 | On Word and Frontier Languages of Unsafe Higher-Order Grammars. Kazuyuki Asada, Naoki Kobayashi |
| 2016 | On the Complexity of Grammar-Based Compression over Fixed Alphabets. Katrin Casel, Henning Fernau, Serge Gaspers, Benjamin Gras, Markus L. Schmid |
| 2016 | On the Hardness of Partially Dynamic Graph Problems and Connections to Diameter. Søren Dahlgaard |
| 2016 | On the Resiliency of Randomized Routing Against Multiple Edge Failures. Marco Chiesa, Andrei V. Gurtov, Aleksander Madry, Slobodan Mitrovic, Ilya Nikolaevskiy, Michael Schapira, Scott Shenker |
| 2016 | On the Sensitivity Conjecture. Avishay Tal |
| 2016 | On the Size and the Approximability of Minimum Temporally Connected Subgraphs. Kyriakos Axiotis, Dimitris Fotakis |
| 2016 | On the Skolem Problem for Continuous Linear Dynamical Systems. Ventsislav Chonev, Joël Ouaknine, James Worrell |
| 2016 | Online Semidefinite Programming. Noa Elad, Satyen Kale, Joseph (Seffi) Naor |
| 2016 | Online Weighted Degree-Bounded Steiner Networks via Novel Online Mixed Packing/Covering. Sina Dehghani, Soheil Ehsani, Mohammad Taghi Hajiaghayi, Vahid Liaghat, Harald Räcke, Saeed Seddighin |
| 2016 | Optimal Approximate Matrix Product in Terms of Stable Rank. Michael B. Cohen, Jelani Nelson, David P. Woodruff |
| 2016 | Optimal Quantum Algorithm for Polynomial Interpolation. Andrew M. Childs, Wim van Dam, Shih-Han Hung, Igor E. Shparlinski |
| 2016 | Optimization Algorithms for Faster Computational Geometry. Zeyuan Allen Zhu, Zhenyu Liao, Yang Yuan |
| 2016 | Parity Separation: A Scientifically Proven Method for Permanent Weight Loss. Radu Curticapean |
| 2016 | Partition Bound Is Quadratically Tight for Product Distributions. Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan |
| 2016 | Past, Present, and Infinite Future. Thomas Wilke |
| 2016 | 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. Olivier Bournez, Daniel Silva Graça, Amaury Pouly |
| 2016 | Popular Half-Integral Matchings. Telikepalli Kavitha |
| 2016 | Power of Quantum Computation with Few Clean Qubits. Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, Seiichiro Tani |
| 2016 | Price of Competition and Dueling Games. Sina Dehghani, Mohammad Taghi Hajiaghayi, Hamid Mahini, Saeed Seddighin |
| 2016 | Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness. Hubie Chen |
| 2016 | Provably Secure Virus Detection: Using The Observer Effect Against Malware. Richard J. Lipton, Rafail Ostrovsky, Vassilis Zikas |
| 2016 | Proving the Herman-Protocol Conjecture. Maria Bruna, Radu Grigore, Stefan Kiefer, Joël Ouaknine, James Worrell |
| 2016 | Quasi-4-Connected Components. Martin Grohe |
| 2016 | Quasimetric Embeddings and Their Applications. Facundo Mémoli, Anastasios Sidiropoulos, Vijay Sridhar |
| 2016 | Random-Edge Is Slower Than Random-Facet on Abstract Cubes. Thomas Dueholm Hansen, Uri Zwick |
| 2016 | Randomization Can Be as Helpful as a Glimpse of the Future in Online Computation. Jesper W. Mikkelsen |
| 2016 | Randomized Query Complexity of Sabotaged and Composed Functions. Shalev Ben-David, Robin Kothari |
| 2016 | Reachability in Networks of Register Protocols under Stochastic Schedulers. Patricia Bouyer, Nicolas Markey, Mickael Randour, Arnaud Sangnier, Daniel Stan |
| 2016 | Relating Graph Thickness to Planar Layers and Bend Complexity. Stephane Durocher, Debajyoti Mondal |
| 2016 | Reservation Exchange Markets for Internet Advertising. Gagan Goel, Stefano Leonardi, Vahab S. Mirrokni, Afshin Nikzad, Renato Paes Leme |
| 2016 | Robust Assignments via Ear Decompositions and Randomized Rounding. David Adjiashvili, Viktor Bindewald, Dennis Michaels |
| 2016 | Rényi Information Complexity and an Information Theoretic Characterization of the Partition Bound. Manoj M. Prabhakaran, Vinod M. Prabhakaran |
| 2016 | Semi-Streaming Algorithms for Annotated Graph Streams. Justin Thaler |
| 2016 | Sensitivity of Counting Queries. Myrto Arapinis, Diego Figueira, Marco Gaboardi |
| 2016 | Simple Average-Case Lower Bounds for Approximate Near-Neighbor from Isoperimetric Inequalities. Yitong Yin |
| 2016 | Solutions of Word Equations Over Partially Commutative Structures. Volker Diekert, Artur Jez, Manfred Kufleitner |
| 2016 | Space-Efficient Error Reduction for Unitary Quantum Computations. Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin, Tomoyuki Morimae, Harumichi Nishimura |
| 2016 | Subexponential Time Algorithms for Embedding H-Minor Free Graphs. Hans L. Bodlaender, Jesper Nederlof, Tom C. van der Zanden |
| 2016 | Sublinear-Space Bounded-Delay Enumeration for Massive Network Analytics: Maximal Cliques. Alessio Conte, Roberto Grossi, Andrea Marino, Luca Versari |
| 2016 | Supercritical Space-Width Trade-Offs for Resolution. Christoph Berkholz, Jakob Nordström |
| 2016 | The Bridge Between Regular Cost Functions and Omega-Regular Languages. Thomas Colcombet, Nathanaël Fijalkow |
| 2016 | The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems. Andreas Emil Feldmann, Dániel Marx |
| 2016 | The Complexity of Downward Closure Comparisons. Georg Zetzsche |
| 2016 | The Complexity of Hex and the Jordan Curve Theorem. Aviv Adler, Constantinos Daskalakis, Erik D. Demaine |
| 2016 | The Complexity of Rational Synthesis. Rodica Condurache, Emmanuel Filiot, Raffaella Gentilini, Jean-François Raskin |
| 2016 | The Decidable Properties of Subrecursive Functions. Mathieu Hoyrup |
| 2016 | The Johnson-Lindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction. Kasper Green Larsen, Jelani Nelson |
| 2016 | The Landscape of Communication Complexity Classes. Mika Göös, Toniann Pitassi, Thomas Watson |
| 2016 | The Linear Voting Model. Colin Cooper, Nicolas Rivera |
| 2016 | The Non-Uniform k-Center Problem. Deeparnab Chakrabarty, Prachi Goyal, Ravishankar Krishnaswamy |
| 2016 | The Schützenberger Product for Syntactic Spaces. Mai Gehrke, Daniela Petrisan, Luca Reggio |
| 2016 | The Taming of the Semi-Linear Set. Dmitry Chistikov, Christoph Haase |
| 2016 | Thin MSO with a Probabilistic Path Quantifier. Mikolaj Bojanczyk |
| 2016 | Tight Analysis of a Multiple-Swap Heurstic for Budgeted Red-Blue Median. Zachary Friggstad, Yifeng Zhang |
| 2016 | Tight Hardness Results for Maximum Weight Rectangles. Arturs Backurs, Nishanth Dikkala, Christos Tzamos |
| 2016 | Tight Sum-Of-Squares Lower Bounds for Binary Polynomial Optimization Problems. Adam Kurpisz, Samuli Leppänen, Monaldo Mastrolilli |
| 2016 | Tolerant Testers of Image Properties. Piotr Berman, Meiram Murzabulatov, Sofya Raskhodnikova |
| 2016 | Total Space in Resolution Is at Least Width Squared. Ilario Bonacina |
| 2016 | Towards Tight Lower Bounds for Range Reporting on the RAM. Allan Grønlund, Kasper Green Larsen |
| 2016 | Unified Acceleration Method for Packing and Covering Problems via Diameter Reduction. Di Wang, Satish Rao, Michael W. Mahoney |
| 2016 | Voronoi Choice Games. Meena Boppana, Rani Hod, Michael Mitzenmacher, Tom Morgan |
| 2016 | k-Center Clustering Under Perturbation Resilience. Maria-Florina Balcan, Nika Haghtalab, Colin White |