Portal - STACS 2021

STACS 2021	March 16-19, 2021, Saarbrücken, Germany (Virtual Conference)
38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) Markus Bläser and Benjamin Monmege (Eds.)
ISBN 978-3-95977-180-1, LIPICS Vol. 187	ISSN 1868-8969

Additional Information

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

Authors

Berlinkov, Mikhail V.

Böckenhauer, Hans-Joachim

de Lima, Murilo Santos

Komusiewicz, Christian

Myrisiotis, Dimitrios

Ossona de Mendez, Patrice

Panagiotou, Konstantinos

Polosukhin, Volodymyr

Rao B. V., Raghavendra

Thankachan, Sharma V.

Theyssier, Guillaume

Tóth, Csaba D.

Venkateswaran, Ramgopal

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Bläser, Markus ; Monmege, Benjamin

Abstract | Document (626 KB) | BibTeX

Optimization, Complexity and Invariant Theory (Invited Talk)

Authors: Bürgisser, Peter

Abstract | Document (804 KB) | BibTeX

First-Order Transductions of Graphs (Invited Talk)

Authors: Ossona de Mendez, Patrice

Abstract | Document (681 KB) | BibTeX

On the Fluted Fragment (Invited Talk)

Authors: Tendera, Lidia

Abstract | Document (341 KB) | BibTeX

Improved (Provable) Algorithms for the Shortest Vector Problem via Bounded Distance Decoding

Authors: Aggarwal, Divesh ; Chen, Yanlin ; Kumar, Rajendra ; Shen, Yixin

Abstract | Document (964 KB) | BibTeX

An FPT Algorithm for Elimination Distance to Bounded Degree Graphs

Authors: Agrawal, Akanksha ; Kanesh, Lawqueen ; Panolan, Fahad ; Ramanujan, M. S. ; Saurabh, Saket

Abstract | Document (761 KB) | BibTeX

A Unified Framework of Quantum Walk Search

Authors: Apers, Simon ; Gilyén, András ; Jeffery, Stacey

Abstract | Document (665 KB) | BibTeX

Achieving Anonymity via Weak Lower Bound Constraints for k-Median and k-Means

Authors: Arutyunova, Anna ; Schmidt, Melanie

Abstract | Document (721 KB) | BibTeX

Bidimensional Linear Recursive Sequences and Universality of Unambiguous Register Automata

Authors: Barloy, Corentin ; Clemente, Lorenzo

Abstract | Document (1,006 KB) | BibTeX

Tight Approximation Guarantees for Concave Coverage Problems

Authors: Barman, Siddharth ; Fawzi, Omar ; Fermé, Paul

Abstract | Document (791 KB) | BibTeX

Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case

Authors: Barto, Libor ; Battistelli, Diego ; Berg, Kevin M.

Abstract | Document (2,805 KB) | BibTeX

A Characterization of Wreath Products Where Knapsack Is Decidable

Authors: Bergsträßer, Pascal ; Ganardi, Moses ; Zetzsche, Georg

Abstract | Document (797 KB) | BibTeX

Synchronizing Strongly Connected Partial DFAs

Authors: Berlinkov, Mikhail V. ; Ferens, Robert ; Ryzhikov, Andrew ; Szykuła, Marek

Abstract | Document (695 KB) | BibTeX

On Euclidean Steiner (1+ε)-Spanners

Authors: Bhore, Sujoy ; Tóth, Csaba D.

Abstract | Document (926 KB) | BibTeX

A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location

Authors: Bienkowski, Marcin ; Feldkord, Björn ; Schmidt, Paweł

Abstract | Document (793 KB) | BibTeX

An Asymptotically Fast Polynomial Space Algorithm for Hamiltonicity Detection in Sparse Directed Graphs

Authors: Björklund, Andreas

Abstract | Document (706 KB) | BibTeX

Online Simple Knapsack with Reservation Costs

Authors: Böckenhauer, Hans-Joachim ; Burjons, Elisabet ; Hromkovič, Juraj ; Lotze, Henri ; Rossmanith, Peter

Abstract | Document (904 KB) | BibTeX

Inapproximability of Diameter in Super-Linear Time: Beyond the 5/3 Ratio

Authors: Bonnet, Édouard

Abstract | Document (752 KB) | BibTeX

The Approximation Ratio of the 2-Opt Heuristic for the Euclidean Traveling Salesman Problem

Authors: Brodowsky, Ulrich A. ; Hougardy, Stefan

Abstract | Document (770 KB) | BibTeX

A Framework of Quantum Strong Exponential-Time Hypotheses

Authors: Buhrman, Harry ; Patro, Subhasree ; Speelman, Florian

Abstract | Document (825 KB) | BibTeX

The Complexity of the Distributed Constraint Satisfaction Problem

Authors: Butti, Silvia ; Dalmau, Victor

Abstract | Document (807 KB) | BibTeX

Distance Computations in the Hybrid Network Model via Oracle Simulations

Authors: Censor-Hillel, Keren ; Leitersdorf, Dean ; Polosukhin, Volodymyr

Abstract | Document (964 KB) | BibTeX

Simple Multi-Pass Streaming Algorithms for Skyline Points and Extreme Points

Authors: Chan, Timothy M. ; Rahul, Saladi

Abstract | Document (710 KB) | BibTeX

One-Tape Turing Machine and Branching Program Lower Bounds for MCSP

Authors: Cheraghchi, Mahdi ; Hirahara, Shuichi ; Myrisiotis, Dimitrios ; Yoshida, Yuichi

Abstract | Document (775 KB) | BibTeX

Inference and Mutual Information on Random Factor Graphs

Authors: Coja-Oghlan, Amin ; Hahn-Klimroth, Max ; Loick, Philipp ; Müller, Noela ; Panagiotou, Konstantinos ; Pasch, Matija

Abstract | Document (736 KB) | BibTeX

The Edit Distance to k-Subsequence Universality

Authors: Day, Joel D. ; Fleischmann, Pamela ; Kosche, Maria ; Koß, Tore ; Manea, Florin ; Siemer, Stefan

Abstract | Document (784 KB) | BibTeX

Barrington Plays Cards: The Complexity of Card-Based Protocols

Authors: Dvořák, Pavel ; Koucký, Michal

Abstract | Document (635 KB) | BibTeX

Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries

Authors: Erlebach, Thomas ; Hoffmann, Michael ; de Lima, Murilo Santos

Abstract | Document (857 KB) | BibTeX

Church Synthesis on Register Automata over Linearly Ordered Data Domains

Authors: Exibard, Léo ; Filiot, Emmanuel ; Khalimov, Ayrat

Abstract | Document (756 KB) | BibTeX

A Faster Algorithm for Finding Tarski Fixed Points

Authors: Fearnley, John ; Savani, Rahul

Abstract | Document (805 KB) | BibTeX

Solving One Variable Word Equations in the Free Group in Cubic Time

Authors: Ferens, Robert ; Jeż, Artur

Abstract | Document (767 KB) | BibTeX

Diverse Collections in Matroids and Graphs

Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Panolan, Fahad ; Philip, Geevarghese ; Saurabh, Saket

Abstract | Document (881 KB) | BibTeX

Rice-Like Theorems for Automata Networks

Authors: Gamard, Guilhem ; Guillon, Pierre ; Perrot, Kevin ; Theyssier, Guillaume

Abstract | Document (736 KB) | BibTeX

Auction Algorithms for Market Equilibrium with Weak Gross Substitute Demands and Their Applications

Authors: Garg, Jugal ; Husić, Edin ; Végh, László A.

Abstract | Document (879 KB) | BibTeX

Efficiently Testing Simon’s Congruence

Authors: Gawrychowski, Paweł ; Kosche, Maria ; Koß, Tore ; Manea, Florin ; Siemer, Stefan

Abstract | Document (993 KB) | BibTeX

Finding an Optimal Alphabet Ordering for Lyndon Factorization Is Hard

Authors: Gibney, Daniel ; Thankachan, Sharma V.

Abstract | Document (743 KB) | BibTeX

Reachability in Two-Parametric Timed Automata with One Parameter Is EXPSPACE-Complete

Authors: Göller, Stefan ; Hilaire, Mathieu

Abstract | Document (880 KB) | BibTeX

Refined Notions of Parameterized Enumeration Kernels with Applications to Matching Cut Enumeration

Authors: Golovach, Petr A. ; Komusiewicz, Christian ; Kratsch, Dieter ; Le, Van Bang

Abstract | Document (840 KB) | BibTeX

Average-Case Algorithms for Testing Isomorphism of Polynomials, Algebras, and Multilinear Forms

Authors: Grochow, Joshua A. ; Qiao, Youming ; Tang, Gang

Abstract | Document (827 KB) | BibTeX

Geometric Cover with Outliers Removal

Authors: Guo, Zhengyang ; Li, Yi

Abstract | Document (814 KB) | BibTeX

Parameterised Counting in Logspace

Authors: Haak, Anselm ; Meier, Arne ; Prakash, Om ; Rao B. V., Raghavendra

Abstract | Document (888 KB) | BibTeX

Digraph Coloring and Distance to Acyclicity

Authors: Harutyunyan, Ararat ; Lampis, Michael ; Melissinos, Nikolaos

Abstract | Document (768 KB) | BibTeX

Good r-Divisions Imply Optimal Amortized Decremental Biconnectivity

Authors: Holm, Jacob ; Rotenberg, Eva

Abstract | Document (846 KB) | BibTeX

b-Coloring Parameterized by Clique-Width

Authors: Jaffke, Lars ; Lima, Paloma T. ; Lokshtanov, Daniel

Abstract | Document (825 KB) | BibTeX

A Ramsey Theorem for Finite Monoids

Authors: Jecker, Ismaël

Abstract | Document (703 KB) | BibTeX

An Improved Sketching Algorithm for Edit Distance

Authors: Jin, Ce ; Nelson, Jelani ; Wu, Kewen

Abstract | Document (866 KB) | BibTeX

Locality Sensitive Hashing for Efficient Similar Polygon Retrieval

Authors: Kaplan, Haim ; Tenenbaum, Jay

Abstract | Document (946 KB) | BibTeX

Binary Matrix Completion Under Diameter Constraints

Authors: Koana, Tomohiro ; Froese, Vincent ; Niedermeier, Rolf

Abstract | Document (800 KB) | BibTeX

Absorbing Patterns in BST-Like Expression-Trees

Authors: Koechlin, Florent ; Rotondo, Pablo

Abstract | Document (1,111 KB) | BibTeX

Cluster Editing Parameterized Above Modification-Disjoint P₃-Packings

Authors: Li, Shaohua ; Pilipczuk, Marcin ; Sorge, Manuel

Abstract | Document (1,067 KB) | BibTeX

Exploiting Dense Structures in Parameterized Complexity

Authors: Lochet, William ; Lokshtanov, Daniel ; Saurabh, Saket ; Zehavi, Meirav

Abstract | Document (858 KB) | BibTeX

Subgroup Membership in GL(2,Z)

Authors: Lohrey, Markus

Abstract | Document (826 KB) | BibTeX

Lower Bounds for Graph-Walking Automata

Authors: Martynova, Olga ; Okhotin, Alexander

Abstract | Document (965 KB) | BibTeX

An Improved Approximation Algorithm for the Maximum Weight Independent Set Problem in d-Claw Free Graphs

Authors: Neuwohner, Meike

Abstract | Document (812 KB) | BibTeX

Complexity of the List Homomorphism Problem in Hereditary Graph Classes

Authors: Okrasa, Karolina ; Rzążewski, Paweł

Abstract | Document (880 KB) | BibTeX

Spectrum Preserving Short Cycle Removal on Regular Graphs

Authors: Paredes, Pedro

Abstract | Document (799 KB) | BibTeX

Fine-Grained Complexity of the List Homomorphism Problem: Feedback Vertex Set and Cutwidth

Authors: Piecyk, Marta ; Rzążewski, Paweł

Abstract | Document (871 KB) | BibTeX

6-Uniform Maker-Breaker Game Is PSPACE-Complete

Authors: Rahman, Md Lutfar ; Watson, Thomas

Abstract | Document (677 KB) | BibTeX

Resolution with Symmetry Rule Applied to Linear Equations

Authors: Schweitzer, Pascal ; Seebach, Constantin

Abstract | Document (774 KB) | BibTeX

Quantum Approximate Counting with Nonadaptive Grover Iterations

Authors: Venkateswaran, Ramgopal ; O'Donnell, Ryan

Abstract | Document (627 KB) | BibTeX

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

38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)