Portal - ICALP 2016

ICALP 2016	July 11-15, 2016 - Rome, Italy
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi (Eds.)
ISBN 978-3-95977-013-2, LIPICS Vol. 55	ISSN 1868-8969

Additional Information

License
Conference Website
Complete volume (PDF, 73 MB)
Search Publication Server

Authors

Balcan, Maria-Florina

Chakrabarty, Deeparnab

Chandran, Nishanth

Charron-Bost, Bernadette

Chatterjee, Krishnendu

Chatzigiannakis, Ioannis

Daskalakis, Constantinos

Feldmann, Andreas Emil

Goubault-Larrecq, Jean

Hajiaghayi, Mohammad Taghi

Halvorsen, Esben Bistrup

Hansen, Thomas Dueholm

Italiano, Giuseppe F.

Kermarrec, Anne-Marie

Krishnaswamy, Ravishankar

Kwiatkowska, Marta Z.

Mallmann-Trenn, Frederik

Medabalimi, Venkatesh

Mitzenmacher, Michael

Nielsen, Jesper Sindahl

Prabhakaran, Manoj M.

Prabhakaran, Vinod M.

Radhakrishnan, Jaikumar

Raskin, Jean-François

Schwiegelshohn, Chris

Sidiropoulos, Anastasios

Starikovskaya, Tatiana

van der Ster, Suzanne

van der Zanden, Tom C.

van Stee, Rob

van Zuylen, Anke

Varma, Nithin

Vassilevska Williams, Virginia

Wulff-Nilsen, Christian

Front Matter, Table of Contents, Preface, Organization, List of Authors

Authors: Chatzigiannakis, Ioannis ; Mitzenmacher, Michael ; Rabani, Yuval ; Sangiorgi, Davide

Abstract | Document (472 KB) | BibTeX

Compute Choice (Invited Talk)

Authors: Shah, Devavrat

Abstract | Document (200 KB) | BibTeX

Formally Verifying a Compiler: What Does It Mean, Exactly? (Invited Talk)

Authors: Leroy, Xavier

Abstract | Document (202 KB) | BibTeX

Hardness of Approximation (Invited Talk)

Authors: Khot, Subhash

Abstract | Document (203 KB) | BibTeX

Model Checking and Strategy Synthesis for Stochastic Games: From Theory to Practice (Invited Talk)

Authors: Kwiatkowska, Marta Z.

Abstract | Document (615 KB) | BibTeX

Fine-Grained Complexity Analysis of Two Classic TSP Variants

Authors: de Berg, Mark ; Buchin, Kevin ; Jansen, Bart M. P. ; Woeginger, Gerhard

Abstract | Document (599 KB) | BibTeX

Bicovering: Covering Edges With Two Small Subsets of Vertices

Authors: Bhangale, Amey ; Gandhi, Rajiv ; Hajiaghayi, Mohammad Taghi ; Khandekar, Rohit ; Kortsarz, Guy

Abstract | Document (537 KB) | BibTeX

Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs

Authors: Chekuri, Chandra ; Ene, Alina ; Pilipczuk, Marcin

Abstract | Document (617 KB) | BibTeX

Quasi-4-Connected Components

Authors: Grohe, Martin

Abstract | Document (515 KB) | BibTeX

Subexponential Time Algorithms for Embedding H-Minor Free Graphs

Authors: Bodlaender, Hans L. ; Nederlof, Jesper ; van der Zanden, Tom C.

Abstract | Document (526 KB) | BibTeX

Relating Graph Thickness to Planar Layers and Bend Complexity

Authors: Durocher, Stephane ; Mondal, Debajyoti

Abstract | Document (549 KB) | BibTeX

Optimal Approximate Matrix Product in Terms of Stable Rank

Authors: Cohen, Michael B. ; Nelson, Jelani ; Woodruff, David P.

Abstract | Document (546 KB) | BibTeX

Approximate Span Programs

Authors: Ito, Tsuyoshi ; Jeffery, Stacey

Abstract | Document (525 KB) | BibTeX

Power of Quantum Computation with Few Clean Qubits

Authors: Fujii, Keisuke ; Kobayashi, Hirotada ; Morimae, Tomoyuki ; Nishimura, Harumichi ; Tamate, Shuhei ; Tani, Seiichiro

Abstract | Document (468 KB) | BibTeX

Space-Efficient Error Reduction for Unitary Quantum Computations

Authors: Fefferman, Bill ; Kobayashi, Hirotada ; Yen-Yu Lin, Cedric ; Morimae, Tomoyuki ; Nishimura, Harumichi

Abstract | Document (593 KB) | BibTeX

Linear Time Algorithm for Quantum 2SAT

Authors: Arad, Itai ; Santha, Miklos ; Sundaram, Aarthi ; Zhang, Shengyu

Abstract | Document (537 KB) | BibTeX

Optimal Quantum Algorithm for Polynomial Interpolation

Authors: Childs, Andrew M. ; van Dam, Wim ; Hung, Shih-Han ; Shparlinski, Igor E.

Abstract | Document (494 KB) | BibTeX

Lower Bounds for the Approximate Degree of Block-Composed Functions

Authors: Thaler, Justin

Abstract | Document (589 KB) | BibTeX

Dynamic Graph Stream Algorithms in o(n) Space

Authors: Huang, Zengfeng ; Peng, Pan

Abstract | Document (601 KB) | BibTeX

Diameter and k-Center in Sliding Windows

Authors: Cohen-Addad, Vincent ; Schwiegelshohn, Chris ; Sohler, Christian

Abstract | Document (531 KB) | BibTeX

Approximate Hamming Distance in a Stream

Authors: Clifford, Raphaël ; Starikovskaya, Tatiana

Abstract | Document (477 KB) | BibTeX

Price of Competition and Dueling Games

Authors: Dehghani, Sina ; Hajiaghayi, Mohammad Taghi ; Mahini, Hamid ; Seddighin, Saeed

Abstract | Document (510 KB) | BibTeX

Popular Half-Integral Matchings

Authors: Kavitha, Telikepalli

Abstract | Document (506 KB) | BibTeX

Voronoi Choice Games

Authors: Boppana, Meena ; Hod, Rani ; Mitzenmacher, Michael ; Morgan, Tom

Abstract | Document (491 KB) | BibTeX

The Complexity of Hex and the Jordan Curve Theorem

Authors: Adler, Aviv ; Daskalakis, Constantinos ; Demaine, Erik D.

Abstract | Document (1,183 KB) | BibTeX

Fractals for Kernelization Lower Bounds, With an Application to Length-Bounded Cut Problems

Authors: Fluschnik, Till ; Hermelin, Danny ; Nichterlein, André ; Niedermeier, Rolf

Abstract | Document (567 KB) | BibTeX

Kernelization of Cycle Packing with Relaxed Disjointness Constraints

Authors: Agrawal, Akanksha ; Lokshtanov, Daniel ; Majumdar, Diptapriyo ; Mouawad, Amer E. ; Saurabh, Saket

Abstract | Document (707 KB) | BibTeX

The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems

Authors: Feldmann, Andreas Emil ; Marx, Dániel

Abstract | Document (522 KB) | BibTeX

Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth

Authors: Marx, Dániel ; Mitsou, Valia

Abstract | Document (1,016 KB) | BibTeX

Do Distributed Differentially-Private Protocols Require Oblivious Transfer?

Authors: Goyal, Vipul ; Khurana, Dakshita ; Mironov, Ilya ; Pandey, Omkant ; Sahai, Amit

Abstract | Document (584 KB) | BibTeX

Functional Commitment Schemes: From Polynomial Commitments to Pairing-Based Accumulators from Simple Assumptions

Authors: Libert, Benoît ; Ramanna, Somindu C. ; Yung, Moti

Abstract | Document (528 KB) | BibTeX

Block-Wise Non-Malleable Codes

Authors: Chandran, Nishanth ; Goyal, Vipul ; Mukherjee, Pratyay ; Pandey, Omkant ; Upadhyay, Jalaj

Abstract | Document (608 KB) | BibTeX

Provably Secure Virus Detection: Using The Observer Effect Against Malware

Authors: Lipton, Richard J. ; Ostrovsky, Rafail ; Zikas, Vassilis

Abstract | Document (613 KB) | BibTeX

An Almost Cubic Lower Bound for Depth Three Arithmetic Circuits

Authors: Kayal, Neeraj ; Saha, Chandan ; Tavenas, Sébastien

Abstract | Document (597 KB) | BibTeX

Boundaries of VP and VNP

Authors: Grochow, Joshua A. ; Mulmuley, Ketan D. ; Qiao, Youming

Abstract | Document (592 KB) | BibTeX

AC^0 o MOD_2 Lower Bounds for the Boolean Inner Product

Authors: Cheraghchi, Mahdi ; Grigorescu, Elena ; Juba, Brendan ; Wimmer, Karl ; Xie, Ning

Abstract | Document (567 KB) | BibTeX

Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs

Authors: Cook, Stephen ; Edmonds, Jeff ; Medabalimi, Venkatesh ; Pitassi, Toniann

Abstract | Document (474 KB) | BibTeX

Improved Bounds on the Sign-Rank of AC^0

Authors: Bun, Mark ; Thaler, Justin

Abstract | Document (614 KB) | BibTeX

On the Sensitivity Conjecture

Authors: Tal, Avishay

Abstract | Document (506 KB) | BibTeX

Randomization Can Be as Helpful as a Glimpse of the Future in Online Computation

Authors: Mikkelsen, Jesper W.

Abstract | Document (577 KB) | BibTeX

Online Semidefinite Programming

Authors: Elad, Noa ; Kale, Satyen ; Naor, Joseph (Seffi)

Abstract | Document (459 KB) | BibTeX

Beating the Harmonic Lower Bound for Online Bin Packing

Authors: Heydrich, Sandy ; van Stee, Rob

Abstract | Document (633 KB) | BibTeX

Online Weighted Degree-Bounded Steiner Networks via Novel Online Mixed Packing/Covering

Authors: Dehghani, Sina ; Ehsani, Soheil ; Hajiaghayi, Mohammad Taghi ; Liaghat, Vahid ; Räcke, Harald ; Seddighin, Saeed

Abstract | Document (719 KB) | BibTeX

Carpooling in Social Networks

Authors: Fiat, Amos ; Karlin, Anna R. ; Koutsoupias, Elias ; Mathieu, Claire ; Zach, Rotem

Abstract | Document (529 KB) | BibTeX

An Improved Analysis of the ER-SpUD Dictionary Learning Algorithm

Authors: Blasiok, Jaroslaw ; Nelson, Jelani

Abstract | Document (608 KB) | BibTeX

Approximation via Correlation Decay When Strong Spatial Mixing Fails

Authors: Bezáková, Ivona ; Galanis, Andreas ; Goldberg, Leslie Ann ; Guo, Heng ; Stefankovic, Daniel

Abstract | Document (542 KB) | BibTeX

A Complexity Trichotomy for Approximately Counting List H-Colourings

Authors: Galanis, Andreas ; Goldberg, Leslie Ann ; Jerrum, Mark

Abstract | Document (518 KB) | BibTeX

Parity Separation: A Scientifically Proven Method for Permanent Weight Loss

Authors: Curticapean, Radu

Abstract | Document (610 KB) | BibTeX

On the Hardness of Partially Dynamic Graph Problems and Connections to Diameter

Authors: Dahlgaard, Søren

Abstract | Document (483 KB) | BibTeX

Incremental 2-Edge-Connectivity in Directed Graphs

Authors: Georgiadis, Loukas ; Italiano, Giuseppe F. ; Parotsidis, Nikos

Abstract | Document (1,175 KB) | BibTeX

Unified Acceleration Method for Packing and Covering Problems via Diameter Reduction

Authors: Wang, Di ; Rao, Satish ; Mahoney, Michael W.

Abstract | Document (534 KB) | BibTeX

Random-Edge Is Slower Than Random-Facet on Abstract Cubes

Authors: Hansen, Thomas Dueholm ; Zwick, Uri

Abstract | Document (610 KB) | BibTeX

Approximating the Solution to Mixed Packing and Covering LPs in Parallel O˜(epsilon^{-3}) Time

Authors: Mahoney, Michael W. ; Rao, Satish ; Wang, Di ; Zhang, Peng

Abstract | Document (513 KB) | BibTeX

Optimization Algorithms for Faster Computational Geometry

Authors: Allen-Zhu, Zeyuan ; Liao, Zhenyu ; Yuan, Yang

Abstract | Document (425 KB) | BibTeX

A Fast Distributed Stateless Algorithm for alpha-Fair Packing Problems

Authors: Marasevic, Jelena ; Stein, Clifford ; Zussman, Gil

Abstract | Document (622 KB) | BibTeX

All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing

Authors: Sommer, Christian

Abstract | Document (479 KB) | BibTeX

Total Space in Resolution Is at Least Width Squared

Authors: Bonacina, Ilario

Abstract | Document (525 KB) | BibTeX

Supercritical Space-Width Trade-Offs for Resolution

Authors: Berkholz, Christoph ; Nordström, Jakob

Abstract | Document (500 KB) | BibTeX

Deterministic Time-Space Trade-Offs for k-SUM

Authors: Lincoln, Andrea ; Vassilevska Williams, Virginia ; Wang, Joshua R. ; Williams, R. Ryan

Abstract | Document (517 KB) | BibTeX

Semi-Streaming Algorithms for Annotated Graph Streams

Authors: Thaler, Justin

Abstract | Document (547 KB) | BibTeX

Randomized Query Complexity of Sabotaged and Composed Functions

Authors: Shalev, Ben-David ; Kothari, Robin

Abstract | Document (490 KB) | BibTeX

Coding for Interactive Communication Correcting Insertions and Deletions

Authors: Braverman, Mark ; Gelles, Ran ; Mao, Jieming ; Ostrovsky, Rafail

Abstract | Document (597 KB) | BibTeX

Amplifiers for the Moran Process

Authors: Galanis, Andreas ; Göbel, Andreas ; Goldberg, Leslie Ann ; Lapinskas, John ; Richerby, David

Abstract | Document (501 KB) | BibTeX

Mixing Time of Markov Chains, Dynamical Systems and Evolution

Authors: Panageas, Ioannis ; Vishnoi, Nisheeth K.

Abstract | Document (553 KB) | BibTeX

Information Cascades on Arbitrary Topologies

Authors: Wan, Jun ; Xia, Yu ; Li, Liang ; Moscibroda, Thomas

Abstract | Document (796 KB) | BibTeX

Analysing Survey Propagation Guided Decimationon Random Formulas

Authors: Hetterich, Samuel

Abstract | Document (534 KB) | BibTeX

Approximation Algorithms for Aversion k-Clustering via Local k-Median

Authors: Gupta, Anupam ; Guruganesh, Guru ; Schmidt, Melanie

Abstract | Document (513 KB) | BibTeX

The Non-Uniform k-Center Problem

Authors: Chakrabarty, Deeparnab ; Goyal, Prachi ; Krishnaswamy, Ravishankar

Abstract | Document (536 KB) | BibTeX

k-Center Clustering Under Perturbation Resilience

Authors: Balcan, Maria-Florina ; Haghtalab, Nika ; White, Colin

Abstract | Document (553 KB) | BibTeX

Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers

Authors: Ahmadian, Sara ; Swamy, Chaitanya

Abstract | Document (751 KB) | BibTeX

A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest

Authors: Schalekamp, Frans ; van Zuylen, Anke ; van der Ster, Suzanne

Abstract | Document (627 KB) | BibTeX

Robust Assignments via Ear Decompositions and Randomized Rounding

Authors: Adjiashvili, David ; Bindewald, Viktor ; Michaels, Dennis

Abstract | Document (471 KB) | BibTeX

Closing the Gap for Makespan Scheduling via Sparsification Techniques

Authors: Jansen, Klaus ; Klein, Kim-Manuel ; Verschae, José

Abstract | Document (549 KB) | BibTeX

Constant Approximation for Capacitated k-Median with (1+epsilon)-Capacity Violation

Authors: Demirci, Gökalp ; Li, Shi

Abstract | Document (656 KB) | BibTeX

Approximating Directed Steiner Problems via Tree Embedding

Authors: Laekhanukit, Bundit

Abstract | Document (463 KB) | BibTeX

Tight Analysis of a Multiple-Swap Heurstic for Budgeted Red-Blue Median

Authors: Friggstad, Zachary ; Zhang, Yifeng

Abstract | Document (639 KB) | BibTeX

Improved Reduction from the Bounded Distance Decoding Problem to the Unique Shortest Vector Problem in Lattices

Authors: Bai, Shi ; Stehlé, Damien ; Wen, Weiqiang

Abstract | Document (759 KB) | BibTeX

A Parallel Repetition Theorem for All Entangled Games

Authors: Yuen, Henry

Abstract | Document (536 KB) | BibTeX

Tight Sum-Of-Squares Lower Bounds for Binary Polynomial Optimization Problems

Authors: Kurpisz, Adam ; Leppänen, Samuli ; Mastrolilli, Monaldo

Abstract | Document (534 KB) | BibTeX

Correlation Decay and Tractability of CSPs

Authors: Brown-Cohen, Jonah ; Raghavendra, Prasad

Abstract | Document (510 KB) | BibTeX

On Percolation and NP-Hardness

Authors: Bennett, Huck ; Reichman, Daniel ; Shinkar, Igor

Abstract | Document (590 KB) | BibTeX

Tight Hardness Results for Maximum Weight Rectangles

Authors: Backurs, Arturs ; Dikkala, Nishanth ; Tzamos, Christos

Abstract | Document (577 KB) | BibTeX

The Johnson-Lindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction

Authors: Larsen, Kasper Green ; Nelson, Jelani

Abstract | Document (461 KB) | BibTeX

Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost

Authors: Andoni, Alexandr ; Naor, Assaf ; Neiman, Ofer

Abstract | Document (657 KB) | BibTeX

Simple Average-Case Lower Bounds for Approximate Near-Neighbor from Isoperimetric Inequalities

Authors: Yin, Yitong

Abstract | Document (496 KB) | BibTeX

Quasimetric Embeddings and Their Applications

Authors: Mémoli, Facundo ; Sidiropoulos, Anastasios ; Sridhar, Vijay

Abstract | Document (520 KB) | BibTeX

The Landscape of Communication Complexity Classes

Authors: Göös, Mika ; Pitassi, Toniann ; Watson, Thomas

Abstract | Document (622 KB) | BibTeX

Information Complexity Is Computable

Authors: Braverman, Mark ; Schneider, Jon

Abstract | Document (462 KB) | BibTeX

Rényi Information Complexity and an Information Theoretic Characterization of the Partition Bound

Authors: Prabhakaran, Manoj M. ; Prabhakaran, Vinod M.

Abstract | Document (662 KB) | BibTeX

On Isoperimetric Profiles and Computational Complexity

Authors: Hrubes, Pavel ; Yehudayoff, Amir

Abstract | Document (471 KB) | BibTeX

Tolerant Testers of Image Properties

Authors: Berman, Piotr ; Murzabulatov, Meiram ; Raskhodnikova, Sofya

Abstract | Document (1,162 KB) | BibTeX

Erasure-Resilient Property Testing

Authors: Dixit, Kashyap ; Raskhodnikova, Sofya ; Thakurta, Abhradeep ; Varma, Nithin

Abstract | Document (576 KB) | BibTeX

Towards Tight Lower Bounds for Range Reporting on the RAM

Authors: Grønlund, Allan ; Larsen, Kasper Green

Abstract | Document (484 KB) | BibTeX

Data Structure Lower Bounds for Document Indexing Problems

Authors: Afshani, Peyman ; Nielsen, Jesper Sindahl

Abstract | Document (551 KB) | BibTeX

Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness

Authors: Chen, Hubie

Abstract | Document (444 KB) | BibTeX

Past, Present, and Infinite Future

Authors: Wilke, Thomas

Abstract | Document (449 KB) | BibTeX

Thin MSO with a Probabilistic Path Quantifier

Authors: Bojanczyk, Mikolaj

Abstract | Document (424 KB) | BibTeX

Deciding Piecewise Testable Separability for Regular Tree Languages

Authors: Goubault-Larrecq, Jean ; Schmitz, Sylvain

Abstract | Document (544 KB) | BibTeX

Computation Tree Logic for Synchronization Properties

Authors: Chatterjee, Krishnendu ; Doyen, Laurent

Abstract | Document (533 KB) | BibTeX

Deciding the Topological Complexity of Büchi Languages

Authors: Skrzypczak, Michal ; Walukiewicz, Igor

Abstract | Document (550 KB) | BibTeX

On the Skolem Problem for Continuous Linear Dynamical Systems

Authors: Chonev, Ventsislav ; Ouaknine, Joël ; Worrell, James

Abstract | Document (509 KB) | BibTeX

Analysing Decisive Stochastic Processes

Authors: Bertrand, Nathalie ; Bouyer, Patricia ; Brihaye, Thomas ; Carlier, Pierre

Abstract | Document (463 KB) | BibTeX

Composition of Stochastic Transition Systems Based on Spans and Couplings

Authors: Gburek, Daniel ; Baier, Christel ; Klüppelholz, Sascha

Abstract | Document (531 KB) | BibTeX

On Restricted Nonnegative Matrix Factorization

Authors: Chistikov, Dmitry ; Kiefer, Stefan ; Marusic, Ines ; Shirmohammadi, Mahsa ; Worrell, James

Abstract | Document (606 KB) | BibTeX

Proving the Herman-Protocol Conjecture

Authors: Bruna, Maria ; Grigore, Radu ; Kiefer, Stefan ; Ouaknine, Joël ; Worrell, James

Abstract | Document (503 KB) | BibTeX

A Polynomial-Time Algorithm for Reachability in Branching VASS in Dimension One

Authors: Göller, Stefan ; Haase, Christoph ; Lazic, Ranko ; Totzke, Patrick

Abstract | Document (624 KB) | BibTeX

Reachability in Networks of Register Protocols under Stochastic Schedulers

Authors: Bouyer, Patricia ; Markey, Nicolas ; Randour, Mickael ; Sangnier, Arnaud ; Stan, Daniel

Abstract | Document (558 KB) | BibTeX

A Program Logic for Union Bounds

Authors: Barthe, Gilles ; Gaboardi, Marco ; Grégoire, Benjamin ; Hsu, Justin ; Strub, Pierre-Yves

Abstract | Document (500 KB) | BibTeX

The Decidable Properties of Subrecursive Functions

Authors: Hoyrup, Mathieu

Abstract | Document (414 KB) | BibTeX

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

Authors: Bournez, Olivier ; Graça, Daniel S. ; Pouly, Amaury

Abstract | Document (519 KB) | BibTeX

Algorithmic Complexity for the Realization of an Effective Subshift By a Sofic

Authors: Sablik, Mathieu ; Schraudner, Michael

Abstract | Document (749 KB) | BibTeX

On Word and Frontier Languages of Unsafe Higher-Order Grammars

Authors: Asada, Kazuyuki ; Kobayashi, Naoki

Abstract | Document (564 KB) | BibTeX

The Schützenberger Product for Syntactic Spaces

Authors: Gehrke, Mai ; Petrisan, Daniela ; Reggio, Luca

Abstract | Document (564 KB) | BibTeX

Logic of Local Inference for Contextuality in Quantum Physics and Beyond

Authors: Kishida, Kohei

Abstract | Document (516 KB) | BibTeX

Minimizing Resources of Sweeping and Streaming String Transducers

Authors: Baschenis, Félix ; Gauwin, Olivier ; Muscholl, Anca ; Puppis, Gabriele

Abstract | Document (534 KB) | BibTeX

A Linear Acceleration Theorem for 2D Cellular Automata on All Complete Neighborhoods

Authors: Grandjean, Anaël ; Poupet, Victor

Abstract | Document (3,097 KB) | BibTeX

New Interpretation and Generalization of the Kameda-Weiner Method

Authors: Tamm, Hellis

Abstract | Document (429 KB) | BibTeX

Nesting Depth of Operators in Graph Database Queries: Expressiveness vs. Evaluation Complexity

Authors: Praveen, M. ; Srivathsan, B.

Abstract | Document (545 KB) | BibTeX

A Hierarchy of Local Decision

Authors: Feuilloley, Laurent ; Fraigniaud, Pierre ; Hirvonen, Juho

Abstract | Document (663 KB) | BibTeX

Constraint Satisfaction Problems for Reducts of Homogeneous Graphs

Authors: Bodirsky, Manuel ; Martin, Barnaby ; Pinsker, Michael ; Pongrácz, András

Abstract | Document (444 KB) | BibTeX

Sensitivity of Counting Queries

Authors: Arapinis, Myrto ; Figueira, Diego ; Gaboardi, Marco

Abstract | Document (1,227 KB) | BibTeX

The Complexity of Rational Synthesis

Authors: Condurache, Rodica ; Filiot, Emmanuel ; Gentilini, Raffaella ; Raskin, Jean-François

Abstract | Document (618 KB) | BibTeX

On the Complexity of Grammar-Based Compression over Fixed Alphabets

Authors: Casel, Katrin ; Fernau, Henning ; Gaspers, Serge ; Gras, Benjamin ; Schmid, Markus L.

Abstract | Document (609 KB) | BibTeX

The Complexity of Downward Closure Comparisons

Authors: Zetzsche, Georg

Abstract | Document (528 KB) | BibTeX

Anti-Powers in Infinite Words

Authors: Fici, Gabriele ; Restivo, Antonio ; Silva, Manuel ; Zamboni, Luca Q.

Abstract | Document (592 KB) | BibTeX

On Equivalence and Uniformisation Problems for Finite Transducers

Authors: Filiot, Emmanuel ; Jecker, Ismaël ; Löding, Christof ; Winter, Sarah

Abstract | Document (552 KB) | BibTeX

The Bridge Between Regular Cost Functions and Omega-Regular Languages

Authors: Colcombet, Thomas ; Fijalkow, Nathanaël

Abstract | Document (506 KB) | BibTeX

Solutions of Word Equations Over Partially Commutative Structures

Authors: Diekert, Volker ; Jez, Artur ; Kufleitner, Manfred

Abstract | Document (457 KB) | BibTeX

The Taming of the Semi-Linear Set

Authors: Chistikov, Dmitry ; Haase, Christoph

Abstract | Document (578 KB) | BibTeX

Characterizing Classes of Regular Languages Using Prefix Codes of Bounded Synchronization Delay

Authors: Diekert, Volker ; Walter, Tobias

Abstract | Document (576 KB) | BibTeX

An Optimal Dual Fault Tolerant Reachability Oracle

Authors: Choudhary, Keerti

Abstract | Document (827 KB) | BibTeX

Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds

Authors: Cheung, Yun Kuen ; Goranci, Gramoz ; Henzinger, Monika

Abstract | Document (571 KB) | BibTeX

Distance Labeling Schemes for Trees

Authors: Alstrup, Stephen ; Gørtz, Inge Li ; Halvorsen, Esben Bistrup ; Porat, Ely

Abstract | Document (556 KB) | BibTeX

Near Optimal Adjacency Labeling Schemes for Power-Law Graphs

Authors: Petersen, Casper ; Rotbart, Noy ; Simonsen, Jakob Grue ; Wulff-Nilsen, Christian

Abstract | Document (577 KB) | BibTeX

On the Resiliency of Randomized Routing Against Multiple Edge Failures

Authors: Chiesa, Marco ; Gurtov, Andrei ; Madry, Aleksander ; Mitrovic, Slobodan ; Nikolaevskiy, Ilya ; Shapira, Michael ; Shenker, Scott

Abstract | Document (533 KB) | BibTeX

Partition Bound Is Quadratically Tight for Product Distributions

Authors: Harsha, Prahladh ; Jain, Rahul ; Radhakrishnan, Jaikumar

Abstract | Document (577 KB) | BibTeX

Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time

Authors: Berenbrink, Petra ; Friedetzky, Tom ; Giakkoupis, George ; Kling, Peter

Abstract | Document (629 KB) | BibTeX

Fast, Robust, Quantizable Approximate Consensus

Authors: Charron-Bost, Bernadette ; Függer, Matthias ; Nowak, Thomas

Abstract | Document (537 KB) | BibTeX

Leader Election in Unreliable Radio Networks

Authors: Ghaffari, Mohsen ; Newport, Calvin

Abstract | Document (657 KB) | BibTeX

Faster Deterministic Communication in Radio Networks

Authors: Czumaj, Artur ; Davies, Peter

Abstract | Document (499 KB) | BibTeX

Networks of Complements

Authors: Babaioff, Moshe ; Blumrosen, Liad ; Nisan, Noam

Abstract | Document (659 KB) | BibTeX

House Markets with Matroid and Knapsack Constraints

Authors: Krysta, Piotr ; Zhang, Jinshan

Abstract | Document (536 KB) | BibTeX

Reservation Exchange Markets for Internet Advertising

Authors: Goel, Gagan ; Leonardi, Stefano ; Mirrokni, Vahab ; Nikzad, Afshin ; Paes-Leme, Renato

Abstract | Document (464 KB) | BibTeX

Competitive Analysis of Constrained Queueing Systems

Authors: Im, Sungjin ; Kulkarni, Janardhan ; Munagala, Kamesh

Abstract | Document (511 KB) | BibTeX

The Linear Voting Model

Authors: Cooper, Colin ; Rivera, Nicolás

Abstract | Document (443 KB) | BibTeX

Discordant Voting Processes on Finite Graphs

Authors: Cooper, Colin ; Dyer, Martin ; Frieze, Alan ; Rivera, Nicolás

Abstract | Document (570 KB) | BibTeX

Bounds on the Voter Model in Dynamic Networks

Authors: Berenbrink, Petra ; Giakkoupis, George ; Kermarrec, Anne-Marie ; Mallmann-Trenn, Frederik

Abstract | Document (558 KB) | BibTeX

Bootstrap Percolation on Geometric Inhomogeneous Random Graphs

Authors: Koch, Christoph ; Lengler, Johannes

Abstract | Document (548 KB) | BibTeX

Sublinear-Space Bounded-Delay Enumeration for Massive Network Analytics: Maximal Cliques

Authors: Conte, Alessio ; Grossi, Roberto ; Marino, Andrea ; Versari, Luca

Abstract | Document (633 KB) | BibTeX

On the Size and the Approximability of Minimum Temporally Connected Subgraphs

Authors: Axiotis, Kyriakos ; Fotakis, Dimitris

Abstract | Document (546 KB) | BibTeX

Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem

Authors: Doerr, Benjamin ; Künnemann, Marvin

Abstract | Document (576 KB) | BibTeX

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)