The Complexity of Translationally Invariant Problems Beyond Ground State Energies (Englisch)
Freier Zugriff
- Neue Suche nach: Watson, James D.
- Weitere Informationen zu Watson, James D.:
- https://orcid.org/0000-0002-6077-4898
- Neue Suche nach: Bausch, Johannes
- Weitere Informationen zu Bausch, Johannes:
- https://orcid.org/0000-0003-3189-9162
- Neue Suche nach: Gharibian, Sevag
- Weitere Informationen zu Gharibian, Sevag:
- https://orcid.org/0000-0002-9992-3379
- Neue Suche nach: Watson, James D.
- Weitere Informationen zu Watson, James D.:
- https://orcid.org/0000-0002-6077-4898
- Neue Suche nach: Bausch, Johannes
- Weitere Informationen zu Bausch, Johannes:
- https://orcid.org/0000-0003-3189-9162
- Neue Suche nach: Gharibian, Sevag
- Weitere Informationen zu Gharibian, Sevag:
- https://orcid.org/0000-0002-9992-3379
- Neue Suche nach: Berenbrink, Petra
- Neue Suche nach: Bouyer, Patricia
- Weitere Informationen zu Bouyer, Patricia:
- https://orcid.org/0000-0002-2823-0911
- Neue Suche nach: Dawar, Anuj
- Weitere Informationen zu Dawar, Anuj:
- https://orcid.org/0000-0003-4014-8248
- Neue Suche nach: Kanté, Mamadou Moustapha
- Weitere Informationen zu Kanté, Mamadou Moustapha:
- https://orcid.org/0000-0003-1838-7744
In:
LIPIcs, Volume 254, STACS 2023
: 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
;
254
;
54:1-54:21
;
2023
-
ISBN:
-
ISSN:
- Aufsatz (Konferenz) / Elektronische Ressource
-
Titel:The Complexity of Translationally Invariant Problems Beyond Ground State Energies
-
Beteiligte:Watson, James D. ( Autor:in ) / Bausch, Johannes ( Autor:in ) / Gharibian, Sevag ( Autor:in ) / Berenbrink, Petra ( Herausgeber:in ) / Bouyer, Patricia ( Herausgeber:in ) / Dawar, Anuj ( Herausgeber:in ) / Kanté, Mamadou Moustapha ( Herausgeber:in )
-
Erschienen in:LIPIcs, Volume 254, STACS 2023 : 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) ; 254 ; 54:1-54:21Leibniz International Proceedings in Informatics (LIPIcs) ; 254 ; 54:1-54:21
-
Verlag:
- Neue Suche nach: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
-
Erscheinungsdatum:03.03.2023
-
Format / Umfang:21 pages , 969634 byte
-
Anmerkungen:LIPIcs, Vol. 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), pages 54:1-54:21
-
ISBN:
-
ISSN:
-
DOI:
-
Medientyp:Aufsatz (Konferenz)
-
Format:Elektronische Ressource
-
Sprache:Englisch
-
Schlagwörter:
-
Lizenzbestimmungen:
-
Datenquelle:
Inhaltsverzeichnis Konferenzband
Die Inhaltsverzeichnisse werden automatisch erzeugt und basieren auf den im Index des TIB-Portals verfügbaren Einzelnachweisen der enthaltenen Beiträge. Die Anzeige der Inhaltsverzeichnisse kann daher unvollständig oder lückenhaft sein.
- 1
-
A Brief History of History-Determinism (Invited Talk)Lehtinen, Karoliina et al. | 2023
- 2
-
Amortised Analysis of Dynamic Data Structures (Invited Talk)Rotenberg, Eva et al. | 2023
- 3
-
Logical Algorithmics: From Theory to Practice (Invited Talk)Vardi, Moshe Y. et al. | 2023
- 4
-
The Complexity of Checking Quasi-Identities over Finite Algebras with a Mal'cev TermAichinger, Erhard / Grünbacher, Simon et al. | 2023
- 5
-
Packing Odd Walks and Trails in Multiterminal NetworksAkhmedov, Maxim / Babenko, Maxim et al. | 2023
- 6
-
Improved Weighted Matching in the Sliding Window ModelAlexandru, Cezar-Mihail / Dvořák, Pavel / Konrad, Christian / Naidu, Kheeran K. et al. | 2023
- 7
-
Approximate Sampling and Counting of Graphs with Near-Regular Degree IntervalsAmanatidis, Georgios / Kleer, Pieter et al. | 2023
- 8
-
Enumerating Regular Languages with Bounded DelayAmarilli, Antoine / Monet, Mikaël et al. | 2023
- 9
-
Regular Separability in Büchi VASSBaumann, Pascal / Meyer, Roland / Zetzsche, Georg et al. | 2023
- 10
-
Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-WidthBergé, Pierre / Bonnet, Édouard / Déprés, Hugues / Watrigant, Rémi et al. | 2023
- 11
-
Tight Lower Bounds for Problems Parameterized by Rank-WidthBergougnoux, Benjamin / Korhonen, Tuukka / Nederlof, Jesper et al. | 2023
- 12
-
On the Multilinear Complexity of Associative AlgebrasBläser, Markus / Mayer, Hendrik / Shringi, Devansh et al. | 2023
- 13
-
Strongly Hyperbolic Unit Disk GraphsBläsius, Thomas / Friedrich, Tobias / Katzmann, Maximilian / Stephan, Daniel et al. | 2023
- 14
-
Tight Bounds for Connectivity Problems Parameterized by CutwidthBojikian, Narek / Chekan, Vera / Hegerfeld, Falko / Kratsch, Stefan et al. | 2023
- 15
-
Twin-Width V: Linear Minors, Modular Counting, and Matrix MultiplicationBonnet, Édouard / Giocanti, Ugo / Ossona de Mendez, Patrice / Thomassé, Stéphan et al. | 2023
- 16
-
Non-Adaptive Proper Learning PolynomialsBshouty, Nader H. et al. | 2023
- 17
-
Cut Paths and Their Remainder Structure, with ApplicationsCairo, Massimo / Khan, Shahbaz / Rizzi, Romeo / Schmidt, Sebastian / Tomescu, Alexandru I. / Zirondelli, Elia C. et al. | 2023
- 18
-
Geometric Amortization of Enumeration AlgorithmsCapelli, Florent / Strozecki, Yann et al. | 2023
- 19
-
One Drop of Non-Determinism in a Random Deterministic AutomatonCarayol, Arnaud / Duchon, Philippe / Koechlin, Florent / Nicaud, Cyril et al. | 2023
- 20
-
Improved NP-Hardness of Approximation for Orthogonality Dimension and MinrankChawin, Dror / Haviv, Ishay et al. | 2023
- 21
-
Extending Merge Resolution to a Family of QBF-Proof SystemsChede, Sravanthi / Shukla, Anil et al. | 2023
- 22
-
On Hardness of Testing Equivalence to Sparse Polynomials Under ShiftsChillara, Suryajith / Grichener, Coral / Shpilka, Amir et al. | 2023
- 23
-
Online Paging with Heterogeneous Cache SlotsChrobak, Marek / Haney, Samuel / Liaee, Mehraneh / Panigrahi, Debmalya / Rajaraman, Rajmohan / Sundaram, Ravi / Young, Neal E. et al. | 2023
- 24
-
On Rational Recursive SequencesClemente, Lorenzo / Donten-Bury, Maria / Mazowiecki, Filip / Pilipczuk, Michał et al. | 2023
- 25
-
Semigroup Intersection Problems in the Heisenberg GroupsDong, Ruiwen et al. | 2023
- 26
-
Solving Homogeneous Linear Equations over Polynomial SemiringsDong, Ruiwen et al. | 2023
- 27
-
An Approximation Algorithm for Distance-Constrained Vehicle Routing on TreesDufay, Marc / Mathieu, Claire / Zhou, Hang et al. | 2023
- 28
-
Representation of Short Distances in Structurally Sparse GraphsDvořák, Zdeněk et al. | 2023
- 29
-
Exact Matching: Algorithms and Related ProblemsEl Maalouly, Nicolas et al. | 2023
- 30
-
Counting Temporal PathsEnright, Jessica / Meeks, Kitty / Molter, Hendrik et al. | 2023
- 31
-
Barriers for Faster Dimensionality ReductionNova Fandina, Ora / Møller Høgsgaard, Mikael / Green Larsen, Kasper et al. | 2023
- 32
-
A Regular and Complete Notion of Delay for Streaming String TransducersFiliot, Emmanuel / Jecker, Ismaël / Löding, Christof / Winter, Sarah et al. | 2023
- 33
-
New Clocks, Optimal Line Formation and Self-Replication Population ProtocolsGąsieniec, Leszek / Spirakis, Paul G. / Stachowiak, Grzegorz et al. | 2023
- 34
-
Avoidance Games Are PSPACE-CompleteGledel, Valentin / Oijid, Nacim et al. | 2023
- 35
-
Parameterized Lower Bounds for Problems in P via Fine-Grained Cross-CompositionsHeeger, Klaus / Nichterlein, André / Niedermeier, Rolf et al. | 2023
- 36
-
Dynamic Maintenance of Monotone Dynamic Programs and ApplicationsHenzinger, Monika / Neumann, Stefan / Räcke, Harald / Schmid, Stefan et al. | 2023
- 37
-
Approximate Selection with Unreliable Comparisons in Optimal Expected TimeHuang, Shengyu / Liu, Chih-Hung / Rutschmann, Daniel et al. | 2023
- 38
-
Relating Description Complexity to EntropyJaakkola, Reijo / Kuusisto, Antti / Vilander, Miikka et al. | 2023
- 39
-
Induced Matching Below Guarantees: Average Paves the Way for Fixed-Parameter TractabilityKoana, Tomohiro et al. | 2023
- 40
-
Finding and Counting Patterns in Sparse GraphsKomarath, Balagopal / Kumar, Anant / Mishra, Suchismita / Sethia, Aditi et al. | 2023
- 41
-
Maximum Matching via Maximal Matching QueriesKonrad, Christian / Naidu, Kheeran K. / Steward, Arun et al. | 2023
- 42
-
Distributed Quantum Interactive ProofsLe Gall, François / Miyamoto, Masayuki / Nishimura, Harumichi et al. | 2023
- 43
-
Reconfiguration of Digraph HomomorphismsLévêque, Benjamin / Mühlenthaler, Moritz / Suzan, Thomas et al. | 2023
- 44
-
An 𝒪(3.82^k) Time FPT Algorithm for Convex Flip DistanceLi, Haohong / Xia, Ge et al. | 2023
- 45
-
Tight Bounds for Repeated Balls-Into-BinsLos, Dimitrios / Sauerwald, Thomas et al. | 2023
- 46
-
Maintaining CMSO₂ Properties on Dynamic Structures with Bounded Feedback Vertex NumberMajewski, Konrad / Pilipczuk, Michał / Sokołowski, Marek et al. | 2023
- 47
-
Sublinear-Time Probabilistic Cellular AutomataModanese, Augusto et al. | 2023
- 48
-
Real Numbers Equally Compressible in Every BaseNandakumar, Satyadev / Pulari, Subin et al. | 2023
- 49
-
Gap Preserving Reductions Between Reconfiguration ProblemsOhsaka, Naoto et al. | 2023
- 50
-
Dynamic Data Structures for Parameterized String ProblemsOlkowski, Jędrzej / Pilipczuk, Michał / Rychlicki, Mateusz / Węgrzycki, Karol / Zych-Pawlewicz, Anna et al. | 2023
- 51
-
An Algebraic Approach to Vectorial ProgramsPaperman, Charles / Salvati, Sylvain / Soyez-Martin, Claire et al. | 2023
- 52
-
Reconstructing Words Using Queries on Subwords or FactorsRichomme, Gwenaël / Rosenfeld, Matthieu et al. | 2023
- 53
-
Dynamic Binary Search Trees: Improved Lower Bounds for the Greedy-Future AlgorithmSadeh, Yaniv / Kaplan, Haim et al. | 2023
- 54
-
The Complexity of Translationally Invariant Problems Beyond Ground State EnergiesWatson, James D. / Bausch, Johannes / Gharibian, Sevag et al. | 2023
- 55
-
Restless Temporal Path Parameterized Above Lower BoundsZschoche, Philipp et al. | 2023