Portal - STACS 2022

STACS 2022	March 15-18, 2022, Marseille, France (Virtual Conference)
39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) Petra Berenbrink and Benjamin Monmege (Eds.)
ISBN 978-3-95977-222-8, LIPICS Vol. 219	ISSN 1868-8969

Additional Information

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

Authors

Balcan, Maria-Florina

Chattopadhyay, Arkadev

D'Angelo, Gianlorenzo

Delle Rose, Valentino

Haddad-Zaknoon, Catherine A.

Hellouin de Menibus, Benjamin

Kanté, Mamadou Moustapha

Komusiewicz, Christian

Kozachinskiy, Alexander

Madathil, Jayakrishnan

Moradpour, Amir Hossein

Saptharishi, Ramprasad

Swennenhuis, Céline M. F.

Thinniyam, Ramanathan S.

Williamson, Christopher

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Berenbrink, Petra ; Monmege, Benjamin

Abstract | Document (639 KB) | BibTeX

Local Limit of Random Discrete Surface with (Or Without!) a Statistical Physics Model (Invited Talk)

Authors: Albenque, Marie

Abstract | Document (1,091 KB) | BibTeX

Generalization Guarantees for Data-Driven Mechanism Design (Invited Talk)

Authors: Balcan, Maria-Florina

Abstract | Document (251 KB) | BibTeX

Deterministic Distributed Symmetry Breaking at the Example of Distributed Graph Coloring (Invited Talk)

Authors: Kuhn, Fabian

Abstract | Document (273 KB) | BibTeX

Mapping Networks via Parallel kth-Hop Traceroute Queries

Authors: Afshar, Ramtin ; Goodrich, Michael T. ; Matias, Pedro ; Osegueda, Martha C.

Abstract | Document (2,288 KB) | BibTeX

On Robustness for the Skolem and Positivity Problems

Authors: Akshay, S. ; Bazille, Hugo ; Genest, Blaise ; Vahanwala, Mihir

Abstract | Document (1,184 KB) | BibTeX

Approximability of Robust Network Design: The Directed Case

Authors: Al-Najjar, Yacine ; Ben-Ameur, Walid ; Leguay, Jérémie

Abstract | Document (1,370 KB) | BibTeX

Existential Definability over the Subword Ordering

Authors: Baumann, Pascal ; Ganardi, Moses ; Thinniyam, Ramanathan S. ; Zetzsche, Georg

Abstract | Document (745 KB) | BibTeX

Intrinsic Complexity of Recursive Functions on Natural Numbers with Standard Order

Authors: Bazhenov, Nikolay ; Kalociński, Dariusz ; Wrocławski, Michał

Abstract | Document (859 KB) | BibTeX

Subquadratic-Time Algorithm for the Diameter and All Eccentricities on Median Graphs

Authors: Bergé, Pierre ; Ducoffe, Guillaume ; Habib, Michel

Abstract | Document (820 KB) | BibTeX

Faster Counting and Sampling Algorithms Using Colorful Decision Oracle

Authors: Bhattacharya, Anup ; Bishnu, Arijit ; Ghosh, Arijit ; Mishra, Gopinath

Abstract | Document (811 KB) | BibTeX

Probabilistic vs Deterministic Gamblers

Authors: Bienvenu, Laurent ; Delle Rose, Valentino ; Steifer, Tomasz

Abstract | Document (652 KB) | BibTeX

Single-Source Shortest p-Disjoint Paths: Fast Computation and Sparse Preservers

Authors: Bilò, Davide ; D'Angelo, Gianlorenzo ; Gualà, Luciano ; Leucci, Stefano ; Proietti, Guido ; Rossi, Mirko

Abstract | Document (1,308 KB) | BibTeX

A 10-Approximation of the π/2-MST

Authors: Biniaz, Ahmad ; Daliri, Majid ; Moradpour, Amir Hossein

Abstract | Document (1,348 KB) | BibTeX

On Explicit Constructions of Extremely Depth Robust Graphs

Authors: Blocki, Jeremiah ; Cinkoske, Mike ; Lee, Seunghoon ; Son, Jin Young

Abstract | Document (901 KB) | BibTeX

Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint

Authors: Bousquet, Nicolas ; Ito, Takehiro ; Kobayashi, Yusuke ; Mizuta, Haruka ; Ouvrard, Paul ; Suzuki, Akira ; Wasa, Kunihiro

Abstract | Document (946 KB) | BibTeX

Characterizing Omega-Regularity Through Finite-Memory Determinacy of Games on Infinite Graphs

Authors: Bouyer, Patricia ; Randour, Mickael ; Vandenhove, Pierre

Abstract | Document (797 KB) | BibTeX

On Testing Decision Tree

Authors: Bshouty, Nader H. ; Haddad-Zaknoon, Catherine A.

Abstract | Document (747 KB) | BibTeX

The Ideal Membership Problem and Abelian Groups

Authors: Bulatov, Andrei A. ; Rafiey, Akbar

Abstract | Document (899 KB) | BibTeX

The Aperiodic Domino Problem in Higher Dimension

Authors: Callard, Antonin ; Hellouin de Menibus, Benjamin

Abstract | Document (907 KB) | BibTeX

Symmetry and Quantum Query-To-Communication Simulation

Authors: Chakraborty, Sourav ; Chattopadhyay, Arkadev ; Høyer, Peter ; Mande, Nikhil S. ; Paraashar, Manaswi ; de Wolf, Ronald

Abstract | Document (822 KB) | BibTeX

Near-Optimal Algorithms for Point-Line Covering Problems

Authors: Chen, Jianer ; Huang, Qin ; Kanj, Iyad ; Xia, Ge

Abstract | Document (856 KB) | BibTeX

Towards Uniform Certification in QBF

Authors: Chew, Leroy ; Slivovsky, Friedrich

Abstract | Document (932 KB) | BibTeX

Blazing a Trail via Matrix Multiplications: A Faster Algorithm for Non-Shortest Induced Paths

Authors: Chiu, Yung-Chung ; Lu, Hsueh-I

Abstract | Document (875 KB) | BibTeX

Depth Lower Bounds in Stabbing Planes for Combinatorial Principles

Authors: Dantchev, Stefan ; Galesi, Nicola ; Ghani, Abdul ; Martin, Barnaby

Abstract | Document (788 KB) | BibTeX

Linear Space Data Structures for Finite Groups with Constant Query-Time

Authors: Das, Bireswar ; Kumar, Anant ; Sharma, Shivdutt ; Thakkar, Dhara

Abstract | Document (722 KB) | BibTeX

The Isomorphism Problem for Plain Groups Is in Σ₃^{𝖯}

Authors: Dietrich, Heiko ; Elder, Murray ; Piggott, Adam ; Qiao, Youming ; Weiß, Armin

Abstract | Document (805 KB) | BibTeX

Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication

Authors: Elkin, Michael ; Neiman, Ofer

Abstract | Document (802 KB) | BibTeX

Cardinality Constrained Scheduling in Online Models

Authors: Epstein, Leah ; Lassota, Alexandra ; Levin, Asaf ; Maack, Marten ; Rohwedder, Lars

Abstract | Document (739 KB) | BibTeX

Detours in Directed Graphs

Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Lochet, William ; Sagunov, Danil ; Simonov, Kirill ; Saurabh, Saket

Abstract | Document (875 KB) | BibTeX

Delay-Robust Routes in Temporal Graphs

Authors: Füchsle, Eugen ; Molter, Hendrik ; Niedermeier, Rolf ; Renken, Malte

Abstract | Document (777 KB) | BibTeX

Maximally Satisfying Lower Quotas in the Hospitals/Residents Problem with Ties

Authors: Goko, Hiromichi ; Makino, Kazuhisa ; Miyazaki, Shuichi ; Yokoi, Yu

Abstract | Document (867 KB) | BibTeX

Online Scheduling on Identical Machines with a Metric State Space

Authors: Goko, Hiromichi ; Kawamura, Akitoshi ; Kawase, Yasushi ; Makino, Kazuhisa ; Sumita, Hanna

Abstract | Document (727 KB) | BibTeX

A Simplicial Model for KB4_n: Epistemic Logic with Agents That May Die

Authors: Goubault, Éric ; Ledent, Jérémy ; Rajsbaum, Sergio

Abstract | Document (1,016 KB) | BibTeX

Star Transposition Gray Codes for Multiset Permutations

Authors: Gregor, Petr ; Mütze, Torsten ; Merino, Arturo

Abstract | Document (2,348 KB) | BibTeX

Improved Quantum Lower and Upper Bounds for Matrix Scaling

Authors: Gribling, Sander ; Nieuwboer, Harold

Abstract | Document (891 KB) | BibTeX

Tight Bounds for Counting Colorings and Connected Edge Sets Parameterized by Cutwidth

Authors: Groenland, Carla ; Mannens, Isja ; Nederlof, Jesper ; Szilágyi, Krisztina

Abstract | Document (943 KB) | BibTeX

Satisfiability of Circuits and Equations over Finite Malcev Algebras

Authors: Idziak, Paweł M. ; Kawałek, Piotr ; Krzaczkowski, Jacek

Abstract | Document (846 KB) | BibTeX

Classes of Intersection Digraphs with Good Algorithmic Properties

Authors: Jaffke, Lars ; Kwon, O-joung ; Telle, Jan Arne

Abstract | Document (928 KB) | BibTeX

Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems

Authors: Kanesh, Lawqueen ; Madathil, Jayakrishnan ; Roy, Sanjukta ; Sahu, Abhishek ; Saurabh, Saket

Abstract | Document (837 KB) | BibTeX

Obstructions for Matroids of Path-Width at most k and Graphs of Linear Rank-Width at most k

Authors: Kanté, Mamadou Moustapha ; Kim, Eun Jung ; Kwon, O-joung ; Oum, Sang-il

Abstract | Document (736 KB) | BibTeX

Fairly Popular Matchings and Optimality

Authors: Kavitha, Telikepalli

Abstract | Document (818 KB) | BibTeX

Covering Many (Or Few) Edges with k Vertices in Sparse Graphs

Authors: Koana, Tomohiro ; Komusiewicz, Christian ; Nichterlein, André ; Sommer, Frank

Abstract | Document (860 KB) | BibTeX

One-To-Two-Player Lifting for Mildly Growing Memory

Authors: Kozachinskiy, Alexander

Abstract | Document (859 KB) | BibTeX

If VNP Is Hard, Then so Are Equations for It

Authors: Kumar, Mrinal ; Ramya, C. ; Saptharishi, Ramprasad ; Tengse, Anamay

Abstract | Document (803 KB) | BibTeX

Determining a Slater Winner Is Complete for Parallel Access to NP

Authors: Lampis, Michael

Abstract | Document (686 KB) | BibTeX

Improved Ackermannian Lower Bound for the Petri Nets Reachability Problem

Authors: Lasota, Sławomir

Abstract | Document (809 KB) | BibTeX

Scheduling with Communication Delay in Near-Linear Time

Authors: Liu, Quanquan C. ; Purohit, Manish ; Svitkina, Zoya ; Vee, Erik ; Wang, Joshua R.

Abstract | Document (1,001 KB) | BibTeX

Extending the Reach of the Point-To-Set Principle

Authors: Lutz, Jack H. ; Lutz, Neil ; Mayordomo, Elvira

Abstract | Document (718 KB) | BibTeX

One-Way Communication Complexity and Non-Adaptive Decision Trees

Authors: Mande, Nikhil S. ; Sanyal, Swagato ; Sherif, Suhail

Abstract | Document (848 KB) | BibTeX

Isolation Schemes for Problems on Decomposable Graphs

Authors: Nederlof, Jesper ; Pilipczuk, Michał ; Swennenhuis, Céline M. F. ; Węgrzycki, Karol

Abstract | Document (1,025 KB) | BibTeX

Oritatami Systems Assemble Shapes No Less Complex Than Tile Assembly Model (ATAM)

Authors: Pchelina, Daria ; Schabanel, Nicolas ; Seki, Shinnosuke ; Theyssier, Guillaume

Abstract | Document (19,458 KB) | BibTeX

Compact Representation for Matrices of Bounded Twin-Width

Authors: Pilipczuk, Michał ; Sokołowski, Marek ; Zych-Pawlewicz, Anna

Abstract | Document (759 KB) | BibTeX

On Finer Separations Between Subclasses of Read-Once Oblivious ABPs

Authors: Ramya, C. ; Tengse, Anamay

Abstract | Document (891 KB) | BibTeX

A Relativization Perspective on Meta-Complexity

Authors: Ren, Hanlin ; Santhanam, Rahul

Abstract | Document (829 KB) | BibTeX

Superlinear Lower Bounds Based on ETH

Authors: Salamon, András Z. ; Wehar, Michael

Abstract | Document (728 KB) | BibTeX

NP-Completeness of Perfect Matching Index of Cubic Graphs

Authors: Škoviera, Martin ; Varša, Peter

Abstract | Document (798 KB) | BibTeX

Optimal Oracles for Point-To-Set Principles

Authors: Stull, D. M.

Abstract | Document (660 KB) | BibTeX

High Quality Consistent Digital Curved Rays via Vector Field Rounding

Authors: Tokuyama, Takeshi ; Yoshimura, Ryo

Abstract | Document (1,104 KB) | BibTeX

Sharp Indistinguishability Bounds from Non-Uniform Approximations

Authors: Williamson, Christopher

Abstract | Document (675 KB) | BibTeX

Analyzing XOR-Forrelation Through Stochastic Calculus

Authors: Wu, Xinyu

Abstract | Document (770 KB) | BibTeX

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

39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)