ICALP 2016 July 11-15, 2016 - Rome, Italy

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



Ioannis Chatzigiannakis, Michael Mitzenmacher, 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
  • Adjiashvili, David
  • Adler, Aviv
  • Afshani, Peyman
  • Agrawal, Akanksha
  • Ahmadian, Sara
  • Allen-Zhu, Zeyuan
  • Alstrup, Stephen
  • Andoni, Alexandr
  • Arad, Itai
  • Arapinis, Myrto
  • Asada, Kazuyuki
  • Axiotis, Kyriakos
  • Babaioff, Moshe
  • Backurs, Arturs
  • Bai, Shi
  • Baier, Christel
  • Balcan, Maria-Florina
  • Barthe, Gilles
  • Baschenis, Félix
  • Bennett, Huck
  • Berenbrink, Petra
  • Berkholz, Christoph
  • Berman, Piotr
  • Bertrand, Nathalie
  • Bezáková, Ivona
  • Bhangale, Amey
  • Bindewald, Viktor
  • Blasiok, Jaroslaw
  • Blumrosen, Liad
  • Bodirsky, Manuel
  • Bodlaender, Hans L.
  • Bojanczyk, Mikolaj
  • Bonacina, Ilario
  • Boppana, Meena
  • Bournez, Olivier
  • Bouyer, Patricia
  • Braverman, Mark
  • Brihaye, Thomas
  • Brown-Cohen, Jonah
  • Bruna, Maria
  • Buchin, Kevin
  • Bun, Mark
  • Carlier, Pierre
  • Casel, Katrin
  • Chakrabarty, Deeparnab
  • Chandran, Nishanth
  • Charron-Bost, Bernadette
  • Chatterjee, Krishnendu
  • Chatzigiannakis, Ioannis
  • Chekuri, Chandra
  • Chen, Hubie
  • Cheraghchi, Mahdi
  • Cheung, Yun Kuen
  • Chiesa, Marco
  • Childs, Andrew M.
  • Chistikov, Dmitry
  • Chonev, Ventsislav
  • Choudhary, Keerti
  • Clifford, Raphaël
  • Cohen, Michael B.
  • Cohen-Addad, Vincent
  • Colcombet, Thomas
  • Condurache, Rodica
  • Conte, Alessio
  • Cook, Stephen
  • Cooper, Colin
  • Curticapean, Radu
  • Czumaj, Artur
  • Dahlgaard, Sřren
  • Daskalakis, Constantinos
  • Davies, Peter
  • de Berg, Mark
  • Dehghani, Sina
  • Demaine, Erik D.
  • Demirci, Gökalp
  • Diekert, Volker
  • Dikkala, Nishanth
  • Dixit, Kashyap
  • Doerr, Benjamin
  • Doyen, Laurent
  • Durocher, Stephane
  • Dyer, Martin
  • Edmonds, Jeff
  • Ehsani, Soheil
  • Elad, Noa
  • Ene, Alina
  • Függer, Matthias
  • Fefferman, Bill
  • Feldmann, Andreas Emil
  • Fernau, Henning
  • Feuilloley, Laurent
  • Fiat, Amos
  • Fici, Gabriele
  • Figueira, Diego
  • Fijalkow, Nathanaël
  • Filiot, Emmanuel
  • Fluschnik, Till
  • Fotakis, Dimitris
  • Fraigniaud, Pierre
  • Friedetzky, Tom
  • Frieze, Alan
  • Friggstad, Zachary
  • Fujii, Keisuke
  • Göös, Mika
  • Göbel, Andreas
  • Göller, Stefan
  • Gřrtz, Inge Li
  • Gaboardi, Marco
  • Galanis, Andreas
  • Gandhi, Rajiv
  • Gaspers, Serge
  • Gauwin, Olivier
  • Gburek, Daniel
  • Gehrke, Mai
  • Gelles, Ran
  • Gentilini, Raffaella
  • Georgiadis, Loukas
  • Ghaffari, Mohsen
  • Giakkoupis, George
  • Goel, Gagan
  • Goldberg, Leslie Ann
  • Goranci, Gramoz
  • Goubault-Larrecq, Jean
  • Goyal, Prachi
  • Goyal, Vipul
  • Grégoire, Benjamin
  • Grřnlund, Allan
  • Graça, Daniel S.
  • Grandjean, Anaël
  • Gras, Benjamin
  • Grigore, Radu
  • Grigorescu, Elena
  • Grochow, Joshua A.
  • Grohe, Martin
  • Grossi, Roberto
  • Guo, Heng
  • Gupta, Anupam
  • Gurtov, Andrei
  • Guruganesh, Guru
  • Haase, Christoph
  • Haghtalab, Nika
  • Hajiaghayi, Mohammad Taghi
  • Halvorsen, Esben Bistrup
  • Hansen, Thomas Dueholm
  • Harsha, Prahladh
  • Henzinger, Monika
  • Hermelin, Danny
  • Hetterich, Samuel
  • Heydrich, Sandy
  • Hirvonen, Juho
  • Hod, Rani
  • Hoyrup, Mathieu
  • Hrubes, Pavel
  • Hsu, Justin
  • Huang, Zengfeng
  • Hung, Shih-Han
  • Im, Sungjin
  • Italiano, Giuseppe F.
  • Ito, Tsuyoshi
  • Jain, Rahul
  • Jansen, Bart M. P.
  • Jansen, Klaus
  • Jecker, Ismaël
  • Jeffery, Stacey
  • Jerrum, Mark
  • Jez, Artur
  • Juba, Brendan
  • Künnemann, Marvin
  • Kale, Satyen
  • Karlin, Anna R.
  • Kavitha, Telikepalli
  • Kayal, Neeraj
  • Kermarrec, Anne-Marie
  • Khandekar, Rohit
  • Khot, Subhash
  • Khurana, Dakshita
  • Kiefer, Stefan
  • Kishida, Kohei
  • Klüppelholz, Sascha
  • Klein, Kim-Manuel
  • Kling, Peter
  • Kobayashi, Hirotada
  • Kobayashi, Naoki
  • Koch, Christoph
  • Kortsarz, Guy
  • Kothari, Robin
  • Koutsoupias, Elias
  • Krishnaswamy, Ravishankar
  • Krysta, Piotr
  • Kufleitner, Manfred
  • Kulkarni, Janardhan
  • Kurpisz, Adam
  • Kwiatkowska, Marta Z.
  • Löding, Christof
  • Laekhanukit, Bundit
  • Lapinskas, John
  • Larsen, Kasper Green
  • Lazic, Ranko
  • Lengler, Johannes
  • Leonardi, Stefano
  • Leppänen, Samuli
  • Leroy, Xavier
  • Li, Liang
  • Li, Shi
  • Liaghat, Vahid
  • Liao, Zhenyu
  • Libert, Benoît
  • Lincoln, Andrea
  • Lipton, Richard J.
  • Lokshtanov, Daniel
  • Mémoli, Facundo
  • Madry, Aleksander
  • Mahini, Hamid
  • Mahoney, Michael W.
  • Majumdar, Diptapriyo
  • Mallmann-Trenn, Frederik
  • Mao, Jieming
  • Marasevic, Jelena
  • Marino, Andrea
  • Markey, Nicolas
  • Martin, Barnaby
  • Marusic, Ines
  • Marx, Dániel
  • Mastrolilli, Monaldo
  • Mathieu, Claire
  • Medabalimi, Venkatesh
  • Michaels, Dennis
  • Mikkelsen, Jesper W.
  • Mironov, Ilya
  • Mirrokni, Vahab
  • Mitrovic, Slobodan
  • Mitsou, Valia
  • Mitzenmacher, Michael
  • Mondal, Debajyoti
  • Morgan, Tom
  • Morimae, Tomoyuki
  • Moscibroda, Thomas
  • Mouawad, Amer E.
  • Mukherjee, Pratyay
  • Mulmuley, Ketan D.
  • Munagala, Kamesh
  • Murzabulatov, Meiram
  • Muscholl, Anca
  • Naor, Assaf
  • Naor, Joseph (Seffi)
  • Nederlof, Jesper
  • Neiman, Ofer
  • Nelson, Jelani
  • Newport, Calvin
  • Nichterlein, André
  • Niedermeier, Rolf
  • Nielsen, Jesper Sindahl
  • Nikolaevskiy, Ilya
  • Nikzad, Afshin
  • Nisan, Noam
  • Nishimura, Harumichi
  • Nordström, Jakob
  • Nowak, Thomas
  • Ostrovsky, Rafail
  • Ouaknine, Joël
  • Paes-Leme, Renato
  • Panageas, Ioannis
  • Pandey, Omkant
  • Parotsidis, Nikos
  • Peng, Pan
  • Petersen, Casper
  • Petrisan, Daniela
  • Pilipczuk, Marcin
  • Pinsker, Michael
  • Pitassi, Toniann
  • Pongrácz, András
  • Porat, Ely
  • Pouly, Amaury
  • Poupet, Victor
  • Prabhakaran, Manoj M.
  • Prabhakaran, Vinod M.
  • Praveen, M.
  • Puppis, Gabriele
  • Qiao, Youming
  • Räcke, Harald
  • Rabani, Yuval
  • Radhakrishnan, Jaikumar
  • Raghavendra, Prasad
  • Ramanna, Somindu C.
  • Randour, Mickael
  • Rao, Satish
  • Raskhodnikova, Sofya
  • Raskin, Jean-François
  • Reggio, Luca
  • Reichman, Daniel
  • Restivo, Antonio
  • Richerby, David
  • Rivera, Nicolás
  • Rotbart, Noy
  • Sablik, Mathieu
  • Saha, Chandan
  • Sahai, Amit
  • Sangiorgi, Davide
  • Sangnier, Arnaud
  • Santha, Miklos
  • Saurabh, Saket
  • Schalekamp, Frans
  • Schmid, Markus L.
  • Schmidt, Melanie
  • Schmitz, Sylvain
  • Schneider, Jon
  • Schraudner, Michael
  • Schwiegelshohn, Chris
  • Seddighin, Saeed
  • Shah, Devavrat
  • Shalev, Ben-David
  • Shapira, Michael
  • Shenker, Scott
  • Shinkar, Igor
  • Shirmohammadi, Mahsa
  • Shparlinski, Igor E.
  • Sidiropoulos, Anastasios
  • Silva, Manuel
  • Simonsen, Jakob Grue
  • Skrzypczak, Michal
  • Sohler, Christian
  • Sommer, Christian
  • Sridhar, Vijay
  • Srivathsan, B.
  • Stan, Daniel
  • Starikovskaya, Tatiana
  • Stefankovic, Daniel
  • Stehlé, Damien
  • Stein, Clifford
  • Strub, Pierre-Yves
  • Sundaram, Aarthi
  • Swamy, Chaitanya
  • Tal, Avishay
  • Tamate, Shuhei
  • Tamm, Hellis
  • Tani, Seiichiro
  • Tavenas, Sébastien
  • Thakurta, Abhradeep
  • Thaler, Justin
  • Totzke, Patrick
  • Tzamos, Christos
  • Upadhyay, Jalaj
  • van Dam, Wim
  • van der Ster, Suzanne
  • van der Zanden, Tom C.
  • van Stee, Rob
  • van Zuylen, Anke
  • Varma, Nithin
  • Vassilevska Williams, Virginia
  • Versari, Luca
  • Verschae, José
  • Vishnoi, Nisheeth K.
  • Walter, Tobias
  • Walukiewicz, Igor
  • Wan, Jun
  • Wang, Di
  • Wang, Joshua R.
  • Watson, Thomas
  • Wen, Weiqiang
  • White, Colin
  • Wilke, Thomas
  • Williams, R. Ryan
  • Wimmer, Karl
  • Winter, Sarah
  • Woeginger, Gerhard
  • Woodruff, David P.
  • Worrell, James
  • Wulff-Nilsen, Christian
  • Xia, Yu
  • Xie, Ning
  • Yehudayoff, Amir
  • Yen-Yu Lin, Cedric
  • Yin, Yitong
  • Yuan, Yang
  • Yuen, Henry
  • Yung, Moti
  • Zach, Rotem
  • Zamboni, Luca Q.
  • Zetzsche, Georg
  • Zhang, Jinshan
  • Zhang, Peng
  • Zhang, Shengyu
  • Zhang, Yifeng
  • Zikas, Vassilis
  • Zussman, Gil
  • Zwick, Uri

  •   
    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 Published by LZI