ICALP 2022 July 4-8, 2022, Paris, France

49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)



Mikołaj Bojańczyk and Emanuela Merelli and David P. Woodruff (Eds.)
ISBN 978-3-95977-235-8, LIPICS Vol. 229 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 52 MB)
Search Publication Server


Authors
  • Abboud, Amir
  • Agrawal, Shweta
  • Allamigeon, Xavier
  • Alman, Josh
  • Alrabiah, Omar
  • Amir, Djamel Eddine
  • Assadi, Sepehr
  • Atserias, Albert
  • Ayyadevara, Nikhil ^*
  • Azar, Yossi
  • Baier, Christel
  • Bansal, Nikhil
  • Barozzini, David
  • Baswana, Surender
  • Beideman, Calvin
  • Ben-Eliezer, Omri
  • Berger, Aaron
  • Bergé, Pierre
  • Bernstein, Aaron
  • Bertrand, Nathalie
  • Bezáková, Ivona
  • Bhanja, Koustav
  • Bilò, Davide
  • Black, Mitchell
  • Blanc, Guy
  • Blikstad, Joakim
  • Blocki, Jeremiah
  • Boehmer, Niclas
  • Bohn, León
  • Bojańczyk, Mikołaj
  • Bonnet, Édouard
  • Bordais, Benjamin
  • Brakerski, Zvika
  • Briański, Marcin
  • Brice, Léonard
  • Bringmann, Karl
  • Brosse, Caroline
  • Busatto-Gaston, Damien
  • Caballero, David
  • Casares, Antonio
  • Cassis, Alejandro
  • Chakraborty, Diptarka
  • Chakraborty, Sourav
  • Chalermsook, Parinya
  • Chandrasekaran, Karthekeyan
  • Charikar, Moses
  • Chatterjee, Kushagra
  • Chattopadhyay, Eshan
  • Chen, Lin
  • Chen, Qingyun
  • Chen, Ryder
  • Chou, Chi-Ning
  • Choudhary, Keerti
  • Christiansen, Aleksander B. G.
  • Cohen, Gil
  • Cohen, Sarel
  • Cohen-Addad, Vincent
  • Coja-Oghlan, Amin
  • Colcombet, Thomas
  • Conradi, Jacobus
  • Czumaj, Artur
  • Dabas, Rajni
  • Dani, Varsha
  • Das, Debarati
  • Daskalakis, Constantinos
  • Datta, Samir
  • de Beaudrap, Niel
  • de Keijzer, Bart
  • de Vos, Tijn
  • Deng, Mingyang
  • Deshpande, Amit
  • Dhamapurkar, Shyam S.
  • Ding, Ming
  • Doron, Dean
  • Doumane, Amina
  • Douéneau-Tabot, Gaëtan
  • Driemel, Anne
  • Dudeja, Aditi
  • Déprés, Hugues
  • Díaz, Josep
  • Döttling, Nico
  • Eden, Talya
  • Efthymiou, Charilaos
  • Esperet, Louis
  • Exibard, Léo
  • Feldman, Moran
  • Filiot, Emmanuel
  • Fischer, Nick
  • Fomin, Fedor V.
  • Forster, Sebastian
  • Friedrich, Tobias
  • Gajarský, Jakub
  • Galanis, Andreas
  • Gan, Luyining
  • Ganardi, Moses
  • Ganguly, Arnab
  • Ganian, Robert
  • Garg, Sanjam
  • Gaubert, Stéphane
  • Gawendowicz, Hans
  • Gawrychowski, Paweł
  • Ghasemi, Elahe
  • Ghosh, Arijit
  • Gimbert, Hugo
  • Goldberg, Leslie Ann
  • Golovach, Petr A.
  • Gomez, Timothy
  • Goodman, Jesse
  • Grigorescu, Elena
  • Grohe, Martin
  • Guha, Shibashis
  • Gupta, Chetan
  • Gutenberg, Maximilian Probst
  • Göös, Mika
  • Hamm, Thekla
  • Han, Jie
  • Harms, Nathaniel
  • Haviv, Ishay
  • Hayes, Thomas P.
  • Hirsch, Dean
  • Holmgren, Justin
  • Houen, Jakob Bæk Tejs
  • Hoyrup, Mathieu
  • Huang, Chien-Chung
  • Huang, Ziyun
  • Idziak, Paweł M.
  • Inamdar, Tanmay
  • Ioannidis, Stavros D.
  • Jain, Rahul
  • Jambulapati, Arun
  • Jansen, Klaus
  • Jiang, Haotian
  • Jiang, Shaofeng H.-C.
  • Jiang, Shunhua
  • Jin, Yujia
  • Jugé, Vincent
  • Kanda, Shunsuke
  • Katz, Ricardo D.
  • Kawałek, Piotr
  • Kayal, Chandrima
  • Khalighinejad, Ghazal
  • Khalimov, Ayrat
  • Khan, Arindam
  • Khatkar, Jahanvi
  • Kiefer, Sandra
  • Kiefer, Stefan
  • Kirkpatrick, Yael
  • Kissinger, Aleks
  • Koana, Tomohiro
  • Kociumaka, Tomasz
  • Kogan, Shimon
  • Komarath, Balagopal
  • Korchemna, Viktoriia
  • Koutecký, Martin
  • Krauthgamer, Robert
  • Krzaczkowski, Jacek
  • Král', Daniel
  • Kumar, Akash
  • Kuszmaul, William
  • Kyng, Rasmus
  • Künnemann, Marvin
  • Laekhanukit, Bundit
  • Lange, Jane
  • Lassota, Alexandra
  • Lee, Euiwoong
  • Lee, Yin Tat
  • Legrand-Duchesne, Clément
  • Lehtinen, Karoliina
  • Lenzner, Pascal
  • Letzter, Shoham
  • Li, Xin
  • Liao, Chao
  • Limouzy, Vincent
  • Lin, Bingkai
  • Lincoln, Andrea
  • Lira, Marvin
  • Liu, Paul
  • Lokshtanov, Daniel
  • Lonkar, Aditya
  • Louis, Anand
  • Love, Peter J.
  • Lu, Zhenjian
  • Löding, Christof
  • Machluf, Chay
  • Maiti, Arnab
  • Majewski, Konrad
  • Majumdar, Rupak
  • Malavolta, Giulio
  • Manurangsi, Pasin
  • Markey, Nicolas
  • Mary, Arnaud
  • Masařík, Tomáš
  • Mascle, Corto
  • Mathialagan, Surya
  • Mathieu, Claire
  • McGregor, Andrew
  • Meka, Raghu
  • Melnichenko, Anna
  • Merelli, Emanuela
  • Minzer, Dor
  • Mishra, Gopinath
  • Moore, Cristopher
  • Mukherjee, Anish
  • Mukherjee, Tamalika
  • Muscholl, Anca
  • Musipatla, Amulya
  • Nakajima, Tamio-Vesa
  • Nakos, Vasileios
  • Nanongkai, Danupon
  • Narayanan, Shyam
  • Natura, Bento
  • Nayyeri, Amir
  • Nazari, Yasamin
  • Neuen, Daniel
  • Newman, Ilan
  • Nishimoto, Takaaki
  • Norin, Sergey
  • Norouzi-Fard, Ashkan
  • Novotná, Jana
  • O'Donnell, Ryan
  • Okrasa, Karolina
  • Oliveira, Igor C.
  • Pandey, Abhyuday
  • Pandey, Anurag
  • Panolan, Fahad
  • Papamakarios, Theodoros
  • Paraashar, Manaswi
  • Parter, Merav
  • Parys, Paweł
  • Patt-Shamir, Boaz
  • Paul, Rameesh
  • Pavlogiannis, Andreas
  • Pawar, Shubham Vivek
  • Pekárková, Kristýna
  • Peleg, Shir
  • Pich, Ján
  • Pilipczuk, Marcin
  • Pilipczuk, Michał
  • Piribauer, Jakob
  • Pokorski, Karol
  • Polak, Adam
  • Potechin, Aaron
  • Pratap, Rameshwar
  • Prebet, Enguerrand
  • Probst Gutenberg, Maximilian
  • Przybyszewski, Wojciech
  • Qiu, Guoliang
  • Radhakrishnan, Jaikumar
  • Rahul, Chengot Sankaramenon
  • Rai, Ashutosh
  • Ramanujan, M. S.
  • Raskin, Jean-François
  • Rattan, Gaurav
  • Ravelomanana, Jean Bernoulli
  • Raychaudhury, Rahul
  • Razborov, Alexander
  • Ren, Xuandi
  • Resch, Nicolas
  • Ribeiro, João
  • Ron, Dana
  • Rong, Victor
  • Rosenbaum, Will
  • Rot, Jurriaan
  • Rotenberg, Eva
  • Rothblum, Ron D.
  • Rozowski, Wojciech
  • Rubinstein, Aviad
  • Rubinstein, Ittai
  • Rzążewski, Paweł
  • Saha, Barna
  • Salo, Ville
  • Sandhu, Juspreet Singh
  • Sankur, Ocan
  • Santhanam, Rahul
  • Saranurak, Thatchaphol
  • Schirneck, Martin
  • Schirrmacher, Nicole
  • Schmid, Todd
  • Schramm, Tselil
  • Schröder, Felix
  • Schweller, Robert
  • Schütze, Lia
  • Sen, Sayantan
  • Sengupta, Rik
  • Seppelt, Tim
  • Shah, Rahul
  • Sharma, Amatya
  • Sharma, Vimal Raj
  • Shi, Jonathan
  • Sidford, Aaron
  • Siebertz, Sebastian
  • Silva, Alexandra
  • Simonov, Kirill
  • Singla, Sahil
  • Sinha, Makrand
  • Skomra, Mateusz
  • Sokołowski, Marek
  • Sreenivas, K. V. N.
  • Stehlé, Damien
  • Stull, D. M.
  • Sudan, Madhu
  • Sukprasert, Pattara
  • Sun, He
  • Sun, Yican
  • Svensson, Ola
  • Ta-Shma, Amnon
  • Tabei, Yasuo
  • Tan, Li-Yang
  • Tancer, Martin
  • Tewari, Raghunath
  • Thankachan, Sharma V.
  • Thomassé, Stéphan
  • Thorup, Mikkel
  • Tian, Kevin
  • Tidor, Jonathan
  • Toruńczyk, Szymon
  • Touitou, Noam
  • Törmä, Ilkka
  • Tětek, Jakub
  • Umboh, Seeun William
  • van de Wetering, John
  • van den Bogaard, Marie
  • van den Brand, Jan
  • Varma, Nithin
  • Vassilevska Williams, Virginia
  • Vempala, Santosh S.
  • Ventre, Carmine
  • Veselý, Pavel
  • Vigny, Alexandre
  • Vigoda, Eric
  • Waingarten, Erik
  • Waldburger, Nicolas
  • Walukiewicz, Igor
  • Wang, Weihang
  • Wang, Xiuhan
  • Wang, Yanheng
  • Wein, Nicole
  • Weinstein, Omri
  • Weiß, Armin
  • Wiese, Andreas
  • Woodruff, David P.
  • Wootters, Mary
  • Wróblewski, Jan
  • Wu, Xiaoyu
  • Wu, Xinyu
  • Wylie, Tim
  • Xu, Jinhui
  • Xu, Yinzhan
  • Yadav, Anshu
  • Yankovitz, Tal
  • Yao, Penghui
  • Yin, Yitong
  • Yingchareonthawornchai, Sorrachai
  • Yoshida, Yuichi
  • Yuan, Chen
  • Yuan, Weiqiang
  • Zehavi, Meirav
  • Zenklusen, Rico
  • Zetzsche, Georg
  • Zhang, Chihao
  • Zhang, Guochuan
  • Zhang, Peng
  • Zhang, Tianyi
  • Zhang, Xinyuan
  • Zhang, Yuhao
  • Zhao, Junyao
  • Zhong, Ziqian
  • Zhou, Hang
  • Zimand, Marius
  • Łukasiewicz, Aleksander
  • Łącki, Jakub
  • Štefankovič, Daniel
  • Živný, Stanislav

  •   
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Bojańczyk, Mikołaj ; Merelli, Emanuela ; Woodruff, David P.

    Abstract | Document (744 KB) | BibTeX

    Towards a Theory of Algorithmic Proof Complexity (Invited Talk)
    Authors: Atserias, Albert

    Abstract | Document (347 KB) | BibTeX

    Equilibrium Computation, Deep Learning, and Multi-Agent Reinforcement Learning (Invited Talk)
    Authors: Daskalakis, Constantinos

    Abstract | Document (376 KB) | BibTeX

    Some New (And Old) Results on Contention Resolution (Invited Talk)
    Authors: Goldberg, Leslie Ann

    Abstract | Document (572 KB) | BibTeX

    The Manifold Joys of Sampling (Invited Talk)
    Authors: Lee, Yin Tat ; Vempala, Santosh S.

    Abstract | Document (978 KB) | BibTeX

    Streaming and Sketching Complexity of CSPs: A Survey (Invited Talk)
    Authors: Sudan, Madhu

    Abstract | Document (872 KB) | BibTeX

    A Brief Tour in Twin-Width (Invited Talk)
    Authors: Thomassé, Stéphan

    Abstract | Document (406 KB) | BibTeX

    Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems
    Authors: Abboud, Amir ; Cohen-Addad, Vincent ; Lee, Euiwoong ; Manurangsi, Pasin

    Abstract | Document (806 KB) | BibTeX

    Round-Optimal Lattice-Based Threshold Signatures, Revisited
    Authors: Agrawal, Shweta ; Stehlé, Damien ; Yadav, Anshu

    Abstract | Document (878 KB) | BibTeX

    Parameterized Sensitivity Oracles and Dynamic Algorithms Using Exterior Algebras
    Authors: Alman, Josh ; Hirsch, Dean

    Abstract | Document (843 KB) | BibTeX

    Low-Degree Polynomials Extract From Local Sources
    Authors: Alrabiah, Omar ; Chattopadhyay, Eshan ; Goodman, Jesse ; Li, Xin ; Ribeiro, João

    Abstract | Document (880 KB) | BibTeX

    Decremental Matching in General Graphs
    Authors: Assadi, Sepehr ; Bernstein, Aaron ; Dudeja, Aditi

    Abstract | Document (1,054 KB) | BibTeX

    Near-Optimal Algorithms for Stochastic Online Bin Packing
    Authors: Ayyadevara, Nikhil ^* ; Dabas, Rajni ; Khan, Arindam ; Sreenivas, K. V. N.

    Abstract | Document (892 KB) | BibTeX

    Competitive Vertex Recoloring
    Authors: Azar, Yossi ; Machluf, Chay ; Patt-Shamir, Boaz ; Touitou, Noam

    Abstract | Document (804 KB) | BibTeX

    Smoothed Analysis of the Komlós Conjecture
    Authors: Bansal, Nikhil ; Jiang, Haotian ; Meka, Raghu ; Singla, Sahil ; Sinha, Makrand

    Abstract | Document (659 KB) | BibTeX

    Minimum+1 (s,t)-cuts and Dual Edge Sensitivity Oracle
    Authors: Baswana, Surender ; Bhanja, Koustav ; Pandey, Abhyuday

    Abstract | Document (1,612 KB) | BibTeX

    Counting and Enumerating Optimum Cut Sets for Hypergraph k-Partitioning Problems for Fixed k
    Authors: Beideman, Calvin ; Chandrasekaran, Karthekeyan ; Wang, Weihang

    Abstract | Document (908 KB) | BibTeX

    Finding Monotone Patterns in Sublinear Time, Adaptively
    Authors: Ben-Eliezer, Omri ; Letzter, Shoham ; Waingarten, Erik

    Abstract | Document (900 KB) | BibTeX

    Deciding Twin-Width at Most 4 Is NP-Complete
    Authors: Bergé, Pierre ; Bonnet, Édouard ; Déprés, Hugues

    Abstract | Document (854 KB) | BibTeX

    Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost
    Authors: Berger, Aaron ; Kuszmaul, William ; Polak, Adam ; Tidor, Jonathan ; Wein, Nicole

    Abstract | Document (821 KB) | BibTeX

    Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary
    Authors: Bernstein, Aaron ; van den Brand, Jan ; Probst Gutenberg, Maximilian ; Nanongkai, Danupon ; Saranurak, Thatchaphol ; Sidford, Aaron ; Sun, He

    Abstract | Document (743 KB) | BibTeX

    Fast Sampling via Spectral Independence Beyond Bounded-Degree Graphs
    Authors: Bezáková, Ivona ; Galanis, Andreas ; Goldberg, Leslie Ann ; Štefankovič, Daniel

    Abstract | Document (777 KB) | BibTeX

    Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances
    Authors: Bilò, Davide ; Choudhary, Keerti ; Cohen, Sarel ; Friedrich, Tobias ; Schirneck, Martin

    Abstract | Document (870 KB) | BibTeX

    Hodge Decomposition and General Laplacian Solvers for Embedded Simplicial Complexes
    Authors: Black, Mitchell ; Nayyeri, Amir

    Abstract | Document (741 KB) | BibTeX

    Reconstructing Decision Trees
    Authors: Blanc, Guy ; Lange, Jane ; Tan, Li-Yang

    Abstract | Document (800 KB) | BibTeX

    Sublinear-Round Parallel Matroid Intersection
    Authors: Blikstad, Joakim

    Abstract | Document (799 KB) | BibTeX

    Privately Estimating Graph Parameters in Sublinear Time
    Authors: Blocki, Jeremiah ; Grigorescu, Elena ; Mukherjee, Tamalika

    Abstract | Document (869 KB) | BibTeX

    The Complexity of Finding Fair Many-To-One Matchings
    Authors: Boehmer, Niclas ; Koana, Tomohiro

    Abstract | Document (854 KB) | BibTeX

    Factoring and Pairings Are Not Necessary for IO: Circular-Secure LWE Suffices
    Authors: Brakerski, Zvika ; Döttling, Nico ; Garg, Sanjam ; Malavolta, Giulio

    Abstract | Document (793 KB) | BibTeX

    Characterization of Matrices with Bounded Graver Bases and Depth Parameters and Applications to Integer Programming
    Authors: Briański, Marcin ; Koutecký, Martin ; Král', Daniel ; Pekárková, Kristýna ; Schröder, Felix

    Abstract | Document (668 KB) | BibTeX

    A Structural Investigation of the Approximability of Polynomial-Time Problems
    Authors: Bringmann, Karl ; Cassis, Alejandro ; Fischer, Nick ; Künnemann, Marvin

    Abstract | Document (789 KB) | BibTeX

    Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution
    Authors: Bringmann, Karl ; Cassis, Alejandro

    Abstract | Document (879 KB) | BibTeX

    Improved Sublinear-Time Edit Distance for Preprocessed Strings
    Authors: Bringmann, Karl ; Cassis, Alejandro ; Fischer, Nick ; Nakos, Vasileios

    Abstract | Document (790 KB) | BibTeX

    Polynomial Delay Algorithm for Minimal Chordal Completions
    Authors: Brosse, Caroline ; Limouzy, Vincent ; Mary, Arnaud

    Abstract | Document (766 KB) | BibTeX

    Unique Assembly Verification in Two-Handed Self-Assembly
    Authors: Caballero, David ; Gomez, Timothy ; Schweller, Robert ; Wylie, Tim

    Abstract | Document (1,221 KB) | BibTeX

    Pairwise Reachability Oracles and Preservers Under Failures
    Authors: Chakraborty, Diptarka ; Chatterjee, Kushagra ; Choudhary, Keerti

    Abstract | Document (913 KB) | BibTeX

    Separations Between Combinatorial Measures for Transitive Functions
    Authors: Chakraborty, Sourav ; Kayal, Chandrima ; Paraashar, Manaswi

    Abstract | Document (853 KB) | BibTeX

    Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver
    Authors: Chalermsook, Parinya ; Huang, Chien-Chung ; Nanongkai, Danupon ; Saranurak, Thatchaphol ; Sukprasert, Pattara ; Yingchareonthawornchai, Sorrachai

    Abstract | Document (928 KB) | BibTeX

    Polylogarithmic Sketches for Clustering
    Authors: Charikar, Moses ; Waingarten, Erik

    Abstract | Document (828 KB) | BibTeX

    Approximation Algorithms for Interdiction Problem with Packing Constraints
    Authors: Chen, Lin ; Wu, Xiaoyu ; Zhang, Guochuan

    Abstract | Document (830 KB) | BibTeX

    Online Weighted Cardinality Joint Replenishment Problem with Delay
    Authors: Chen, Ryder ; Khatkar, Jahanvi ; Umboh, Seeun William

    Abstract | Document (762 KB) | BibTeX

    Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond
    Authors: Chou, Chi-Ning ; Love, Peter J. ; Sandhu, Juspreet Singh ; Shi, Jonathan

    Abstract | Document (806 KB) | BibTeX

    Fully-Dynamic α + 2 Arboricity Decompositions and Implicit Colouring
    Authors: Christiansen, Aleksander B. G. ; Rotenberg, Eva

    Abstract | Document (982 KB) | BibTeX

    Expander Random Walks: The General Case and Limitations
    Authors: Cohen, Gil ; Minzer, Dor ; Peleg, Shir ; Potechin, Aaron ; Ta-Shma, Amnon

    Abstract | Document (782 KB) | BibTeX

    LCC and LDC: Tailor-Made Distance Amplification and a Refined Separation
    Authors: Cohen, Gil ; Yankovitz, Tal

    Abstract | Document (788 KB) | BibTeX

    Metastability of the Potts Ferromagnet on Random Regular Graphs
    Authors: Coja-Oghlan, Amin ; Galanis, Andreas ; Goldberg, Leslie Ann ; Ravelomanana, Jean Bernoulli ; Štefankovič, Daniel ; Vigoda, Eric

    Abstract | Document (807 KB) | BibTeX

    On Computing the k-Shortcut Fréchet Distance
    Authors: Conradi, Jacobus ; Driemel, Anne

    Abstract | Document (1,096 KB) | BibTeX

    Streaming Algorithms for Geometric Steiner Forest
    Authors: Czumaj, Artur ; Jiang, Shaofeng H.-C. ; Krauthgamer, Robert ; Veselý, Pavel

    Abstract | Document (912 KB) | BibTeX

    Improved Reconstruction of Random Geometric Graphs
    Authors: Dani, Varsha ; Díaz, Josep ; Hayes, Thomas P. ; Moore, Cristopher

    Abstract | Document (1,319 KB) | BibTeX

    Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding
    Authors: Das, Debarati ; Kociumaka, Tomasz ; Saha, Barna

    Abstract | Document (1,038 KB) | BibTeX

    New Additive Approximations for Shortest Paths and Cycles
    Authors: Deng, Mingyang ; Kirkpatrick, Yael ; Rong, Victor ; Vassilevska Williams, Virginia ; Zhong, Ziqian

    Abstract | Document (678 KB) | BibTeX

    One-Pass Additive-Error Subset Selection for 𝓁_p Subspace Approximation
    Authors: Deshpande, Amit ; Pratap, Rameshwar

    Abstract | Document (729 KB) | BibTeX

    Set Membership with Two Classical and Quantum Bit Probes
    Authors: Dhamapurkar, Shyam S. ; Pawar, Shubham Vivek ; Radhakrishnan, Jaikumar

    Abstract | Document (787 KB) | BibTeX

    Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets
    Authors: Ding, Ming ; Kyng, Rasmus ; Gutenberg, Maximilian Probst ; Zhang, Peng

    Abstract | Document (1,135 KB) | BibTeX

    Two-Commodity Flow Is Equivalent to Linear Programming Under Nearly-Linear Time Reductions
    Authors: Ding, Ming ; Kyng, Rasmus ; Zhang, Peng

    Abstract | Document (1,047 KB) | BibTeX

    High-Probability List-Recovery, and Applications to Heavy Hitters
    Authors: Doron, Dean ; Wootters, Mary

    Abstract | Document (812 KB) | BibTeX

    Almost Optimal Bounds for Sublinear-Time Sampling of k-Cliques in Bounded Arboricity Graphs
    Authors: Eden, Talya ; Ron, Dana ; Rosenbaum, Will

    Abstract | Document (868 KB) | BibTeX

    On Sampling Symmetric Gibbs Distributions on Sparse Random Graphs and Hypergraphs
    Authors: Efthymiou, Charilaos

    Abstract | Document (718 KB) | BibTeX

    Testability and Local Certification of Monotone Properties in Minor-Closed Classes
    Authors: Esperet, Louis ; Norin, Sergey

    Abstract | Document (750 KB) | BibTeX

    Streaming Submodular Maximization Under Matroid Constraints
    Authors: Feldman, Moran ; Liu, Paul ; Norouzi-Fard, Ashkan ; Svensson, Ola ; Zenklusen, Rico

    Abstract | Document (1,159 KB) | BibTeX

    (Re)packing Equal Disks into Rectangle
    Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Inamdar, Tanmay ; Zehavi, Meirav

    Abstract | Document (886 KB) | BibTeX

    Faster Cut Sparsification of Weighted Graphs
    Authors: Forster, Sebastian ; de Vos, Tijn

    Abstract | Document (829 KB) | BibTeX

    Social Distancing Network Creation
    Authors: Friedrich, Tobias ; Gawendowicz, Hans ; Lenzner, Pascal ; Melnichenko, Anna

    Abstract | Document (1,103 KB) | BibTeX

    Approximating Observables Is as Hard as Counting
    Authors: Galanis, Andreas ; Štefankovič, Daniel ; Vigoda, Eric

    Abstract | Document (768 KB) | BibTeX

    The Decision Problem for Perfect Matchings in Dense Hypergraphs
    Authors: Gan, Luyining ; Han, Jie

    Abstract | Document (848 KB) | BibTeX

    Fully Functional Parameterized Suffix Trees in Compact Space
    Authors: Ganguly, Arnab ; Shah, Rahul ; Thankachan, Sharma V.

    Abstract | Document (908 KB) | BibTeX

    The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width
    Authors: Ganian, Robert ; Hamm, Thekla ; Korchemna, Viktoriia ; Okrasa, Karolina ; Simonov, Kirill

    Abstract | Document (919 KB) | BibTeX

    Sublinear Dynamic Interval Scheduling (On One or Multiple Machines)
    Authors: Gawrychowski, Paweł ; Pokorski, Karol

    Abstract | Document (1,000 KB) | BibTeX

    Galloping in Fast-Growth Natural Merge Sorts
    Authors: Ghasemi, Elahe ; Jugé, Vincent ; Khalighinejad, Ghazal

    Abstract | Document (924 KB) | BibTeX

    Tolerant Bipartiteness Testing in Dense Graphs
    Authors: Ghosh, Arijit ; Mishra, Gopinath ; Raychaudhury, Rahul ; Sen, Sayantan

    Abstract | Document (843 KB) | BibTeX

    Homomorphism Tensors and Linear Equations
    Authors: Grohe, Martin ; Rattan, Gaurav ; Seppelt, Tim

    Abstract | Document (877 KB) | BibTeX

    Downsampling for Testing and Learning in Product Distributions
    Authors: Harms, Nathaniel ; Yoshida, Yuichi

    Abstract | Document (862 KB) | BibTeX

    A Fixed-Parameter Algorithm for the Kneser Problem
    Authors: Haviv, Ishay

    Abstract | Document (743 KB) | BibTeX

    Delegation for Search Problems
    Authors: Holmgren, Justin ; Lincoln, Andrea ; Rothblum, Ron D.

    Abstract | Document (800 KB) | BibTeX

    Understanding the Moments of Tabulation Hashing via Chaoses
    Authors: Houen, Jakob Bæk Tejs ; Thorup, Mikkel

    Abstract | Document (764 KB) | BibTeX

    In-Range Farthest Point Queries and Related Problem in High Dimensions
    Authors: Huang, Ziyun ; Xu, Jinhui

    Abstract | Document (1,297 KB) | BibTeX

    Strong Approximations and Irrationality in Financial Networks with Derivatives
    Authors: Ioannidis, Stavros D. ; de Keijzer, Bart ; Ventre, Carmine

    Abstract | Document (843 KB) | BibTeX

    Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching
    Authors: Jambulapati, Arun ; Jin, Yujia ; Sidford, Aaron ; Tian, Kevin

    Abstract | Document (917 KB) | BibTeX

    A PTAS for Packing Hypercubes into a Knapsack
    Authors: Jansen, Klaus ; Khan, Arindam ; Lira, Marvin ; Sreenivas, K. V. N.

    Abstract | Document (835 KB) | BibTeX

    A Faster Interior-Point Method for Sum-Of-Squares Optimization
    Authors: Jiang, Shunhua ; Natura, Bento ; Weinstein, Omri

    Abstract | Document (910 KB) | BibTeX

    Tight Approximation Algorithms for Two-Dimensional Guillotine Strip Packing
    Authors: Khan, Arindam ; Lonkar, Aditya ; Maiti, Arnab ; Sharma, Amatya ; Wiese, Andreas

    Abstract | Document (887 KB) | BibTeX

    A Study of Weisfeiler-Leman Colorings on Planar Graphs
    Authors: Kiefer, Sandra ; Neuen, Daniel

    Abstract | Document (857 KB) | BibTeX

    Beating Matrix Multiplication for n^{1/3}-Directed Shortcuts
    Authors: Kogan, Shimon ; Parter, Merav

    Abstract | Document (1,007 KB) | BibTeX

    Monotone Arithmetic Complexity of Graph Homomorphism Polynomials
    Authors: Komarath, Balagopal ; Pandey, Anurag ; Rahul, Chengot Sankaramenon

    Abstract | Document (716 KB) | BibTeX

    Exact Recovery Algorithm for Planted Bipartite Graph in Semi-Random Graphs
    Authors: Kumar, Akash ; Louis, Anand ; Paul, Rameesh

    Abstract | Document (827 KB) | BibTeX

    Optimal Time-Backlog Tradeoffs for the Variable-Processor Cup Game
    Authors: Kuszmaul, William ; Narayanan, Shyam

    Abstract | Document (706 KB) | BibTeX

    Near-Optimal Decremental Hopsets with Applications
    Authors: Łącki, Jakub ; Nazari, Yasamin

    Abstract | Document (802 KB) | BibTeX

    Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs
    Authors: Lassota, Alexandra ; Łukasiewicz, Aleksander ; Polak, Adam

    Abstract | Document (799 KB) | BibTeX

    Parameterized Complexity of Untangling Knots
    Authors: Legrand-Duchesne, Clément ; Rai, Ashutosh ; Tancer, Martin

    Abstract | Document (1,014 KB) | BibTeX

    Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity
    Authors: Liao, Chao ; Chen, Qingyun ; Laekhanukit, Bundit ; Zhang, Yuhao

    Abstract | Document (803 KB) | BibTeX

    On Lower Bounds of Approximating Parameterized k-Clique
    Authors: Lin, Bingkai ; Ren, Xuandi ; Sun, Yican ; Wang, Xiuhan

    Abstract | Document (838 KB) | BibTeX

    Backdoor Sets on Nowhere Dense SAT
    Authors: Lokshtanov, Daniel ; Panolan, Fahad ; Ramanujan, M. S.

    Abstract | Document (889 KB) | BibTeX

    Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity
    Authors: Lu, Zhenjian ; Oliveira, Igor C. ; Zimand, Marius

    Abstract | Document (748 KB) | BibTeX

    Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument
    Authors: Majewski, Konrad ; Masařík, Tomáš ; Novotná, Jana ; Okrasa, Karolina ; Pilipczuk, Marcin ; Rzążewski, Paweł ; Sokołowski, Marek

    Abstract | Document (1,229 KB) | BibTeX

    Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds
    Authors: Mathialagan, Surya ; Vassilevska Williams, Virginia ; Xu, Yinzhan

    Abstract | Document (803 KB) | BibTeX

    A PTAS for Capacitated Vehicle Routing on Trees
    Authors: Mathieu, Claire ; Zhou, Hang

    Abstract | Document (802 KB) | BibTeX

    Graph Reconstruction from Random Subgraphs
    Authors: McGregor, Andrew ; Sengupta, Rik

    Abstract | Document (749 KB) | BibTeX

    The SDP Value of Random 2CSPs
    Authors: Musipatla, Amulya ; O'Donnell, Ryan ; Schramm, Tselil ; Wu, Xinyu

    Abstract | Document (864 KB) | BibTeX

    Strongly Sublinear Algorithms for Testing Pattern Freeness
    Authors: Newman, Ilan ; Varma, Nithin

    Abstract | Document (770 KB) | BibTeX

    An Optimal-Time RLBWT Construction in BWT-Runs Bounded Space
    Authors: Nishimoto, Takaaki ; Kanda, Shunsuke ; Tabei, Yasuo

    Abstract | Document (1,556 KB) | BibTeX

    Space Characterizations of Complexity Measures and Size-Space Trade-Offs in Propositional Proof Systems
    Authors: Papamakarios, Theodoros ; Razborov, Alexander

    Abstract | Document (715 KB) | BibTeX

    Learning Algorithms Versus Automatability of Frege Systems
    Authors: Pich, Ján ; Santhanam, Rahul

    Abstract | Document (2,437 KB) | BibTeX

    Algorithms and Data Structures for First-Order Logic with Connectivity Under Vertex Failures
    Authors: Pilipczuk, Michał ; Schirrmacher, Nicole ; Siebertz, Sebastian ; Toruńczyk, Szymon ; Vigny, Alexandre

    Abstract | Document (1,020 KB) | BibTeX

    A Perfect Sampler for Hypergraph Independent Sets
    Authors: Qiu, Guoliang ; Wang, Yanheng ; Zhang, Chihao

    Abstract | Document (929 KB) | BibTeX

    Threshold Rates of Code Ensembles: Linear Is Best
    Authors: Resch, Nicolas ; Yuan, Chen

    Abstract | Document (793 KB) | BibTeX

    Explicit and Efficient Construction of Nearly Optimal Rate Codes for the Binary Deletion Channel and the Poisson Repeat Channel
    Authors: Rubinstein, Ittai

    Abstract | Document (965 KB) | BibTeX

    Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond 1/2-Approximation
    Authors: Rubinstein, Aviad ; Zhao, Junyao

    Abstract | Document (797 KB) | BibTeX

    Approximate Triangle Counting via Sampling and Fast Matrix Multiplication
    Authors: Tětek, Jakub

    Abstract | Document (849 KB) | BibTeX

    Polynomial-Time Approximation of Zero-Free Partition Functions
    Authors: Yao, Penghui ; Yin, Yitong ; Zhang, Xinyuan

    Abstract | Document (746 KB) | BibTeX

    Faster Cut-Equivalent Trees in Simple Graphs
    Authors: Zhang, Tianyi

    Abstract | Document (878 KB) | BibTeX

    Universal Complexity Bounds Based on Value Iteration and Application to Entropy Games
    Authors: Allamigeon, Xavier ; Gaubert, Stéphane ; Katz, Ricardo D. ; Skomra, Mateusz

    Abstract | Document (862 KB) | BibTeX

    Computability of Finite Simplicial Complexes
    Authors: Amir, Djamel Eddine ; Hoyrup, Mathieu

    Abstract | Document (671 KB) | BibTeX

    Unboundedness for Recursion Schemes: A Simpler Type System
    Authors: Barozzini, David ; Parys, Paweł ; Wróblewski, Jan

    Abstract | Document (783 KB) | BibTeX

    Parameterized Safety Verification of Round-Based Shared-Memory Systems
    Authors: Bertrand, Nathalie ; Markey, Nicolas ; Sankur, Ocan ; Waldburger, Nicolas

    Abstract | Document (986 KB) | BibTeX

    Passive Learning of Deterministic Büchi Automata by Combinations of DFAs
    Authors: Bohn, León ; Löding, Christof

    Abstract | Document (839 KB) | BibTeX

    Strategy Synthesis for Global Window PCTL
    Authors: Bordais, Benjamin ; Busatto-Gaston, Damien ; Guha, Shibashis ; Raskin, Jean-François

    Abstract | Document (1,197 KB) | BibTeX

    The Complexity of SPEs in Mean-Payoff Games
    Authors: Brice, Léonard ; Raskin, Jean-François ; van den Bogaard, Marie

    Abstract | Document (826 KB) | BibTeX

    On the Size of Good-For-Games Rabin Automata and Its Link with the Memory in Muller Games
    Authors: Casares, Antonio ; Colcombet, Thomas ; Lehtinen, Karoliina

    Abstract | Document (971 KB) | BibTeX

    Dynamic Meta-Theorems for Distance and Matching
    Authors: Datta, Samir ; Gupta, Chetan ; Jain, Rahul ; Mukherjee, Anish ; Sharma, Vimal Raj ; Tewari, Raghunath

    Abstract | Document (838 KB) | BibTeX

    Circuit Extraction for ZX-Diagrams Can Be #P-Hard
    Authors: de Beaudrap, Niel ; Kissinger, Aleks ; van de Wetering, John

    Abstract | Document (905 KB) | BibTeX

    Hiding Pebbles When the Output Alphabet Is Unary
    Authors: Douéneau-Tabot, Gaëtan

    Abstract | Document (775 KB) | BibTeX

    Regular Expressions for Tree-Width 2 Graphs
    Authors: Doumane, Amina

    Abstract | Document (833 KB) | BibTeX

    A Generic Solution to Register-Bounded Synthesis with an Application to Discrete Orders
    Authors: Exibard, Léo ; Filiot, Emmanuel ; Khalimov, Ayrat

    Abstract | Document (846 KB) | BibTeX

    Twin-Width and Types
    Authors: Gajarský, Jakub ; Pilipczuk, Michał ; Przybyszewski, Wojciech ; Toruńczyk, Szymon

    Abstract | Document (1,077 KB) | BibTeX

    Reachability in Bidirected Pushdown VASS
    Authors: Ganardi, Moses ; Majumdar, Rupak ; Pavlogiannis, Andreas ; Schütze, Lia ; Zetzsche, Georg

    Abstract | Document (881 KB) | BibTeX

    Distributed Controller Synthesis for Deadlock Avoidance
    Authors: Gimbert, Hugo ; Mascle, Corto ; Muscholl, Anca ; Walukiewicz, Igor

    Abstract | Document (727 KB) | BibTeX

    Lower Bounds for Unambiguous Automata via Communication Complexity
    Authors: Göös, Mika ; Kiefer, Stefan ; Yuan, Weiqiang

    Abstract | Document (771 KB) | BibTeX

    Satisfiability Problems for Finite Groups
    Authors: Idziak, Paweł M. ; Kawałek, Piotr ; Krzaczkowski, Jacek ; Weiß, Armin

    Abstract | Document (915 KB) | BibTeX

    Linearly Ordered Colourings of Hypergraphs
    Authors: Nakajima, Tamio-Vesa ; Živný, Stanislav

    Abstract | Document (879 KB) | BibTeX

    The Variance-Penalized Stochastic Shortest Path Problem
    Authors: Piribauer, Jakob ; Sankur, Ocan ; Baier, Christel

    Abstract | Document (797 KB) | BibTeX

    Functions and References in the Pi-Calculus: Full Abstraction and Proof Techniques
    Authors: Prebet, Enguerrand

    Abstract | Document (804 KB) | BibTeX

    What Can Oracles Teach Us About the Ultimate Fate of Life?
    Authors: Salo, Ville ; Törmä, Ilkka

    Abstract | Document (1,149 KB) | BibTeX

    Processes Parametrised by an Algebraic Theory
    Authors: Schmid, Todd ; Rozowski, Wojciech ; Silva, Alexandra ; Rot, Jurriaan

    Abstract | Document (914 KB) | BibTeX

    The Dimension Spectrum Conjecture for Planar Lines
    Authors: Stull, D. M.

    Abstract | Document (684 KB) | BibTeX

      




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