default search action
43rd ICALP 2016: Rome, Italy
- Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, Davide Sangiorgi:
43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy. LIPIcs 55, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2016, ISBN 978-3-95977-013-2 - Front Matter, Table of Contents, Preface, Organization, List of Authors. 0:i-0:xliv
Invited Talks
- Devavrat Shah:
Compute Choice. 1:1-1:1 - Xavier Leroy:
Formally Verifying a Compiler: What Does It Mean, Exactly? 2:1-2:1 - Subhash Khot:
Hardness of Approximation. 3:1-3:1 - Marta Z. Kwiatkowska:
Model Checking and Strategy Synthesis for Stochastic Games: From Theory to Practice. 4:1-4:18
Track A: Algorithms, Complexity and Games
- Mark de Berg, Kevin Buchin
, Bart M. P. Jansen, Gerhard J. Woeginger:
Fine-Grained Complexity Analysis of Two Classic TSP Variants. 5:1-5:14 - Amey Bhangale, Rajiv Gandhi, Mohammad Taghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz:
Bicovering: Covering Edges With Two Small Subsets of Vertices. 6:1-6:12 - Chandra Chekuri, Alina Ene, Marcin Pilipczuk:
Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs. 7:1-7:14 - Martin Grohe:
Quasi-4-Connected Components. 8:1-8:13 - Hans L. Bodlaender
Subexponential Time Algorithms for Embedding H-Minor Free Graphs. 9:1-9:14 - Stephane Durocher, Debajyoti Mondal:
Relating Graph Thickness to Planar Layers and Bend Complexity. 10:1-10:13 - Michael B. Cohen
Optimal Approximate Matrix Product in Terms of Stable Rank. 11:1-11:14 - Tsuyoshi Ito, Stacey Jeffery:
Approximate Span Programs. 12:1-12:14 - Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura
Power of Quantum Computation with Few Clean Qubits. 13:1-13:14 - Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin, Tomoyuki Morimae, Harumichi Nishimura
Space-Efficient Error Reduction for Unitary Quantum Computations. 14:1-14:14 - Itai Arad, Miklos Santha, Aarthi Sundaram, Shengyu Zhang:
Linear Time Algorithm for Quantum 2SAT. 15:1-15:14 - Andrew M. Childs
Optimal Quantum Algorithm for Polynomial Interpolation. 16:1-16:13 - Justin Thaler:
Lower Bounds for the Approximate Degree of Block-Composed Functions. 17:1-17:15 - Zengfeng Huang
Dynamic Graph Stream Algorithms in o(n) Space. 18:1-18:16 - Vincent Cohen-Addad, Chris Schwiegelshohn, Christian Sohler
Diameter and k-Center in Sliding Windows. 19:1-19:12 - Raphaël Clifford, Tatiana Starikovskaya:
Approximate Hamming Distance in a Stream. 20:1-20:14 - Sina Dehghani, Mohammad Taghi Hajiaghayi, Hamid Mahini, Saeed Seddighin:
Price of Competition and Dueling Games. 21:1-21:14 - Telikepalli Kavitha:
Popular Half-Integral Matchings. 22:1-22:13 - Meena Boppana, Rani Hod
Voronoi Choice Games. 23:1-23:13 - Aviv Adler, Constantinos Daskalakis, Erik D. Demaine:
The Complexity of Hex and the Jordan Curve Theorem. 24:1-24:14 - Till Fluschnik, Danny Hermelin, André Nichterlein, Rolf Niedermeier:
Fractals for Kernelization Lower Bounds, With an Application to Length-Bounded Cut Problems. 25:1-25:14 - Akanksha Agrawal
Kernelization of Cycle Packing with Relaxed Disjointness Constraints. 26:1-26:14 - Andreas Emil Feldmann
The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems. 27:1-27:14 - Dániel Marx, Valia Mitsou:
Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth. 28:1-28:15 - Vipul Goyal, Dakshita Khurana, Ilya Mironov
Do Distributed Differentially-Private Protocols Require Oblivious Transfer?. 29:1-29:15 - Benoît Libert, Somindu C. Ramanna, Moti Yung:
Functional Commitment Schemes: From Polynomial Commitments to Pairing-Based Accumulators from Simple Assumptions. 30:1-30:14 - Nishanth Chandran, Vipul Goyal, Pratyay Mukherjee, Omkant Pandey, Jalaj Upadhyay:
Block-Wise Non-Malleable Codes. 31:1-31:14 - Richard J. Lipton, Rafail Ostrovsky, Vassilis Zikas:
Provably Secure Virus Detection: Using The Observer Effect Against Malware. 32:1-32:14 - Neeraj Kayal, Chandan Saha, Sébastien Tavenas:
An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits. 33:1-33:15 - Joshua A. Grochow, Ketan D. Mulmuley, Youming Qiao
Boundaries of VP and VNP. 34:1-34:14 - Mahdi Cheraghchi
AC^0 o MOD_2 Lower Bounds for the Boolean Inner Product. 35:1-35:14 - Stephen A. Cook, Jeff Edmonds, Venkatesh Medabalimi, Toniann Pitassi:
Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs. 36:1-36:13 - Mark Bun, Justin Thaler:
Improved Bounds on the Sign-Rank of AC^0. 37:1-37:14 - Avishay Tal:
On the Sensitivity Conjecture. 38:1-38:13 - Jesper W. Mikkelsen
Randomization Can Be as Helpful as a Glimpse of the Future in Online Computation. 39:1-39:14 - Noa Elad, Satyen Kale, Joseph (Seffi) Naor:
Online Semidefinite Programming. 40:1-40:13 - Sandy Heydrich
Beating the Harmonic Lower Bound for Online Bin Packing. 41:1-41:14 - Sina Dehghani, Soheil Ehsani, Mohammad Taghi Hajiaghayi, Vahid Liaghat, Harald Räcke, Saeed Seddighin:
Online Weighted Degree-Bounded Steiner Networks via Novel Online Mixed Packing/Covering. 42:1-42:14 - Amos Fiat, Anna R. Karlin, Elias Koutsoupias, Claire Mathieu, Rotem Zach:
Carpooling in Social Networks. 43:1-43:13 - Jaroslaw Blasiok
An Improved Analysis of the ER-SpUD Dictionary Learning Algorithm. 44:1-44:14 - Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Daniel Stefankovic
Approximation via Correlation Decay When Strong Spatial Mixing Fails. 45:1-45:13 - Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum:
A Complexity Trichotomy for Approximately Counting List H-Colourings. 46:1-46:13 - Radu Curticapean:
Parity Separation: A Scientifically Proven Method for Permanent Weight Loss. 47:1-47:14 - Søren Dahlgaard:
On the Hardness of Partially Dynamic Graph Problems and Connections to Diameter. 48:1-48:14 - Loukas Georgiadis
Incremental 2-Edge-Connectivity in Directed Graphs. 49:1-49:15 - Di Wang, Satish Rao, Michael W. Mahoney:
Unified Acceleration Method for Packing and Covering Problems via Diameter Reduction. 50:1-50:13 - Thomas Dueholm Hansen, Uri Zwick:
Random-Edge Is Slower Than Random-Facet on Abstract Cubes. 51:1-51:14 - Michael W. Mahoney, Satish Rao, Di Wang, Peng Zhang:
Approximating the Solution to Mixed Packing and Covering LPs in Parallel O˜(epsilon^{-3}) Time. 52:1-52:14 - Zeyuan Allen Zhu, Zhenyu Liao, Yang Yuan:
Optimization Algorithms for Faster Computational Geometry. 53:1-53:6 - Jelena Marasevic, Clifford Stein, Gil Zussman:
A Fast Distributed Stateless Algorithm for alpha-Fair Packing Problems. 54:1-54:15 - Christian Sommer:
All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing. 55:1-55:13 - Ilario Bonacina
Total Space in Resolution Is at Least Width Squared. 56:1-56:13 - Christoph Berkholz, Jakob Nordström
Supercritical Space-Width Trade-Offs for Resolution. 57:1-57:14 - Andrea Lincoln
Deterministic Time-Space Trade-Offs for k-SUM. 58:1-58:14 - Justin Thaler:
Semi-Streaming Algorithms for Annotated Graph Streams. 59:1-59:14 - Shalev Ben-David, Robin Kothari
Randomized Query Complexity of Sabotaged and Composed Functions. 60:1-60:14 - Mark Braverman, Ran Gelles, Jieming Mao, Rafail Ostrovsky:
Coding for Interactive Communication Correcting Insertions and Deletions. 61:1-61:14 - Andreas Galanis, Andreas Göbel, Leslie Ann Goldberg, John Lapinskas
Amplifiers for the Moran Process. 62:1-62:13 - Ioannis Panageas, Nisheeth K. Vishnoi:
Mixing Time of Markov Chains, Dynamical Systems and Evolution. 63:1-63:14 - Jun Wan, Yu Xia, Liang Li, Thomas Moscibroda:
Information Cascades on Arbitrary Topologies. 64:1-64:14 - Samuel Hetterich:
Analysing Survey Propagation Guided Decimationon Random Formulas. 65:1-65:12 - Anupam Gupta, Guru Guruganesh, Melanie Schmidt
Approximation Algorithms for Aversion k-Clustering via Local k-Median. 66:1-66:13 - Deeparnab Chakrabarty, Prachi Goyal, Ravishankar Krishnaswamy:
The Non-Uniform k-Center Problem. 67:1-67:15 - Maria-Florina Balcan, Nika Haghtalab, Colin White:
k-Center Clustering Under Perturbation Resilience. 68:1-68:14 - Sara Ahmadian, Chaitanya Swamy:
Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers. 69:1-69:15 - Frans Schalekamp, Anke van Zuylen, Suzanne van der Ster:
A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest. 70:1-70:14 - David Adjiashvili, Viktor Bindewald
Robust Assignments via Ear Decompositions and Randomized Rounding. 71:1-71:14 - Klaus Jansen, Kim-Manuel Klein, José Verschae:
Closing the Gap for Makespan Scheduling via Sparsification Techniques. 72:1-72:13 - H. Gökalp Demirci, Shi Li:
Constant Approximation for Capacitated k-Median with (1+epsilon)-Capacity Violation. 73:1-73:14 - Bundit Laekhanukit
Approximating Directed Steiner Problems via Tree Embedding. 74:1-74:13 - Zachary Friggstad, Yifeng Zhang:
Tight Analysis of a Multiple-Swap Heurstic for Budgeted Red-Blue Median. 75:1-75:13 - Shi Bai, Damien Stehlé, Weiqiang Wen
Improved Reduction from the Bounded Distance Decoding Problem to the Unique Shortest Vector Problem in Lattices. 76:1-76:12 - Henry Yuen:
A Parallel Repetition Theorem for All Entangled Games. 77:1-77:13 - Adam Kurpisz
Tight Sum-Of-Squares Lower Bounds for Binary Polynomial Optimization Problems. 78:1-78:14 - Jonah Brown-Cohen, Prasad Raghavendra:
Correlation Decay and Tractability of CSPs. 79:1-79:13 - Huck Bennett, Daniel Reichman, Igor Shinkar:
On Percolation and NP-Hardness. 80:1-80:14 - Arturs Backurs, Nishanth Dikkala, Christos Tzamos
Tight Hardness Results for Maximum Weight Rectangles. 81:1-81:13 - Kasper Green Larsen, Jelani Nelson:
The Johnson-Lindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction. 82:1-82:11 - Alexandr Andoni, Assaf Naor, Ofer Neiman:
Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost. 83:1-83:14 - Yitong Yin:
Simple Average-Case Lower Bounds for Approximate Near-Neighbor from Isoperimetric Inequalities. 84:1-84:13 - Facundo Mémoli, Anastasios Sidiropoulos, Vijay Sridhar:
Quasimetric Embeddings and Their Applications. 85:1-85:14 - Mika Göös, Toniann Pitassi, Thomas Watson:
The Landscape of Communication Complexity Classes. 86:1-86:15 - Mark Braverman, Jon Schneider:
Information Complexity Is Computable. 87:1-87:10 - Manoj M. Prabhakaran, Vinod M. Prabhakaran:
Rényi Information Complexity and an Information Theoretic Characterization of the Partition Bound. 88:1-88:14 - Pavel Hrubes, Amir Yehudayoff:
On Isoperimetric Profiles and Computational Complexity. 89:1-89:12 - Piotr Berman, Meiram Murzabulatov
Tolerant Testers of Image Properties. 90:1-90:14 - Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, Nithin Varma
Erasure-Resilient Property Testing. 91:1-91:15 - Allan Grønlund, Kasper Green Larsen:
Towards Tight Lower Bounds for Range Reporting on the RAM. 92:1-92:12 - Peyman Afshani, Jesper Sindahl Nielsen:
Data Structure Lower Bounds for Document Indexing Problems. 93:1-93:15
Track B: Logic, Semantics, Automata and Theory of Programming
- Hubie Chen:
Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness. 94:1-94:14 - Thomas Wilke:
Past, Present, and Infinite Future. 95:1-95:14 - Mikolaj Bojanczyk:
Thin MSO with a Probabilistic Path Quantifier. 96:1-96:13 - Jean Goubault-Larrecq, Sylvain Schmitz
Deciding Piecewise Testable Separability for Regular Tree Languages. 97:1-97:15 - Krishnendu Chatterjee, Laurent Doyen:
Computation Tree Logic for Synchronization Properties. 98:1-98:14 - Michal Skrzypczak, Igor Walukiewicz:
Deciding the Topological Complexity of Büchi Languages. 99:1-99:13 - Ventsislav Chonev, Joël Ouaknine, James Worrell
On the Skolem Problem for Continuous Linear Dynamical Systems. 100:1-100:13 - Nathalie Bertrand
Analysing Decisive Stochastic Processes. 101:1-101:14 - Daniel Gburek, Christel Baier
Composition of Stochastic Transition Systems Based on Spans and Couplings. 102:1-102:15 - Dmitry Chistikov
On Restricted Nonnegative Matrix Factorization. 103:1-103:14 - Maria Bruna
Proving the Herman-Protocol Conjecture. 104:1-104:12 - Stefan Göller, Christoph Haase
A Polynomial-Time Algorithm for Reachability in Branching VASS in Dimension One. 105:1-105:13 - Patricia Bouyer, Nicolas Markey, Mickael Randour, Arnaud Sangnier
Reachability in Networks of Register Protocols under Stochastic Schedulers. 106:1-106:14 - Gilles Barthe
A Program Logic for Union Bounds. 107:1-107:15 - Mathieu Hoyrup:
The Decidable Properties of Subrecursive Functions. 108:1-108:13 - Olivier Bournez, Daniel Silva Graça
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. 109:1-109:15 - Mathieu Sablik, Michael Schraudner:
Algorithmic Complexity for the Realization of an Effective Subshift By a Sofic. 110:1-110:14 - Kazuyuki Asada, Naoki Kobayashi
On Word and Frontier Languages of Unsafe Higher-Order Grammars. 111:1-111:13 - Mai Gehrke, Daniela Petrisan, Luca Reggio
The Schützenberger Product for Syntactic Spaces. 112:1-112:14 - Kohei Kishida
Logic of Local Inference for Contextuality in Quantum Physics and Beyond. 113:1-113:14 - Félix Baschenis, Olivier Gauwin, Anca Muscholl, Gabriele Puppis
Minimizing Resources of Sweeping and Streaming String Transducers. 114:1-114:14 - Anaël Grandjean, Victor Poupet:
A Linear Acceleration Theorem for 2D Cellular Automata on All Complete Neighborhoods. 115:1-115:12 - Hellis Tamm
New Interpretation and Generalization of the Kameda-Weiner Method. 116:1-116:12 - M. Praveen, B. Srivathsan
Nesting Depth of Operators in Graph Database Queries: Expressiveness vs. Evaluation Complexity. 117:1-117:14 - Laurent Feuilloley
A Hierarchy of Local Decision. 118:1-118:15 - Manuel Bodirsky, Barnaby Martin
Constraint Satisfaction Problems for Reducts of Homogeneous Graphs. 119:1-119:14 - Myrto Arapinis, Diego Figueira, Marco Gaboardi
Sensitivity of Counting Queries. 120:1-120:13 - Rodica Condurache, Emmanuel Filiot
The Complexity of Rational Synthesis. 121:1-121:15 - Katrin Casel, Henning Fernau
On the Complexity of Grammar-Based Compression over Fixed Alphabets. 122:1-122:14 - Georg Zetzsche
The Complexity of Downward Closure Comparisons. 123:1-123:14 - Gabriele Fici
Anti-Powers in Infinite Words. 124:1-124:9 - Emmanuel Filiot
On Equivalence and Uniformisation Problems for Finite Transducers. 125:1-125:14 - Thomas Colcombet
The Bridge Between Regular Cost Functions and Omega-Regular Languages. 126:1-126:13 - Volker Diekert, Artur Jez
Solutions of Word Equations Over Partially Commutative Structures. 127:1-127:14
Track C: Foundations of Networked Computation: Models, Algorithms and Information Management
- Dmitry Chistikov
The Taming of the Semi-Linear Set. 128:1-128:13 - Volker Diekert, Tobias Walter:
Characterizing Classes of Regular Languages Using Prefix Codes of Bounded Synchronization Delay. 129:1-129:14 - Keerti Choudhary
An Optimal Dual Fault Tolerant Reachability Oracle. 130:1-130:13 - Yun Kuen Cheung, Gramoz Goranci, Monika Henzinger:
Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds. 131:1-131:14 - Stephen Alstrup, Inge Li Gørtz
Distance Labeling Schemes for Trees. 132:1-132:16 - Casper Petersen, Noy Rotbart, Jakob Grue Simonsen, Christian Wulff-Nilsen:
Near Optimal Adjacency Labeling Schemes for Power-Law Graphs. 133:1-133:15 - Marco Chiesa
On the Resiliency of Randomized Routing Against Multiple Edge Failures. 134:1-134:15 - Prahladh Harsha
Partition Bound Is Quadratically Tight for Product Distributions. 135:1-135:13 - Petra Berenbrink, Tom Friedetzky
Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time. 136:1-136:14 - Bernadette Charron-Bost, Matthias Függer, Thomas Nowak
Fast, Robust, Quantizable Approximate Consensus. 137:1-137:14 - Mohsen Ghaffari, Calvin C. Newport:
Leader Election in Unreliable Radio Networks. 138:1-138:14 - Artur Czumaj, Peter Davies
Faster Deterministic Communication in Radio Networks. 139:1-139:14 - Moshe Babaioff, Liad Blumrosen, Noam Nisan:
Networks of Complements. 140:1-140:14 - Piotr Krysta, Jinshan Zhang:
House Markets with Matroid and Knapsack Constraints. 141:1-141:14 - Gagan Goel, Stefano Leonardi, Vahab S. Mirrokni, Afshin Nikzad, Renato Paes Leme:
Reservation Exchange Markets for Internet Advertising. 142:1-142:13 - Sungjin Im, Janardhan Kulkarni, Kamesh Munagala:
Competitive Analysis of Constrained Queueing Systems. 143:1-143:13 - Colin Cooper, Nicolas Rivera:
The Linear Voting Model. 144:1-144:12 - Colin Cooper, Martin E. Dyer
Discordant Voting Processes on Finite Graphs. 145:1-145:13 - Petra Berenbrink, George Giakkoupis, Anne-Marie Kermarrec, Frederik Mallmann-Trenn:
Bounds on the Voter Model in Dynamic Networks. 146:1-146:15 - Christoph Koch, Johannes Lengler
Bootstrap Percolation on Geometric Inhomogeneous Random Graphs. 147:1-147:15 - Alessio Conte, Roberto Grossi, Andrea Marino
Sublinear-Space Bounded-Delay Enumeration for Massive Network Analytics: Maximal Cliques. 148:1-148:15 - Kyriakos Axiotis, Dimitris Fotakis:
On the Size and the Approximability of Minimum Temporally Connected Subgraphs. 149:1-149:14 - Benjamin Doerr, Marvin Künnemann:
Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem. 150:1-150:13
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-11-22 19:48 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: