Cover Image

The Fine-Grained Complexity of Episode Matching

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bille, Philip, Gørtz, Inge Li, Mozes, Shay, Steiner, Teresa Anna, Weimann, Oren
Format:	Preprint
Published:	2021
Subjects:	Data Structures and Algorithms Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

String Indexing with Compressed Patterns
by: Bille, Philip, et al.
Published: (2019)

Improved Extended Regular Expression Matching
by: Bille, Philip, et al.
Published: (2025)

Differentially Private Substring and Document Counting with Near-Optimal Error
by: Bernardini, Giulia, et al.
Published: (2024)

Faster Construction of a Planar Distance Oracle with Õ(1) Query Time
by: Boneh, Itai, et al.
Published: (2025)

String Indexing for Top-$k$ Close Consecutive Occurrences
by: Bille, Philip, et al.
Published: (2020)

Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs
by: Boneh, Itai, et al.
Published: (2025)

Compressed Dictionary Matching on Run-Length Encoded Strings
by: Bille, Philip, et al.
Published: (2025)

Gapped String Indexing in Subquadratic Space and Sublinear Query Time
by: Bille, Philip, et al.
Published: (2022)

Succinct Data Structures for Segments
by: Bille, Philip, et al.
Published: (2024)

Fast Practical Compression of Deterministic Finite Automata
by: Bille, Philip, et al.
Published: (2023)

Fine-Grained Complexity of Continuous Euclidean k-Center
by: Blank, Lotte, et al.
Published: (2026)

Fine-Grained Classification Of Detecting Dominating Patterns
by: Dransfeld, Jonathan, et al.
Published: (2025)

Fine-Grained Equivalence for Problems Related to Integer Linear Programming
by: Rohwedder, Lars, et al.
Published: (2024)

Dynamic Range Minimum Queries on the Ultra-Wide Word RAM
by: Bille, Philip, et al.
Published: (2024)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
by: Assadi, Sepehr, et al.
Published: (2024)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
by: Nederlof, Jesper
Published: (2026)

On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut
by: Huang, Jeremy Ahrens, et al.
Published: (2024)

The Complexity of Finding and Counting Subtournaments
by: Döring, Simon, et al.
Published: (2025)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

The Complexity of Counting Small Sub-Hypergraphs
by: Bressan, Marco, et al.
Published: (2025)

Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions
by: Chia, Nai-Hui, et al.
Published: (2026)

Exact Matching and Top-k Perfect Matching Parameterized by Neighborhood Diversity or Bandwidth
by: Maalouly, Nicolas El, et al.
Published: (2025)

Bipartite Matching is in Catalytic Logspace
by: Agarwala, Aryan, et al.
Published: (2025)

Matching and Edge Cover in Temporal Graphs
by: Cioni, Lapo, et al.
Published: (2025)

Structural Parameterizations for Induced and Acyclic Matching
by: Lampis, Michael, et al.
Published: (2025)

The Query Complexity of Local Search and Brouwer in Rounds
by: Brânzei, Simina, et al.
Published: (2020)

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
by: Focke, Jacob, et al.
Published: (2022)

The Mystery Deepens: On the Query Complexity of Tarski Fixed Points
by: Chen, Xi, et al.
Published: (2026)

The Fine-Grained Complexity of Gradient Computation for Training Large Language Models
by: Alman, Josh, et al.
Published: (2024)

Low-Sensitivity Matching via Sampling from Gibbs Distributions
by: Yoshida, Yuichi, et al.
Published: (2025)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
by: Focke, Jacob, et al.
Published: (2023)

Parameterized Complexity of Vehicle Routing
by: Döring, Michelle, et al.
Published: (2025)

On the Parameterized Complexity of Odd Coloring
by: Bhyravarapu, Sriram, et al.
Published: (2025)

On the Complexity of Signed Roman Domination
by: Reddy, Sangam Balchandar
Published: (2025)

On the Space Complexity of Online Convolution
by: Andersson, Joel Daniel, et al.
Published: (2025)

Computational Complexity in Property Testing
by: Pinto Jr., Renato Ferreira, et al.
Published: (2025)

A New Information Complexity Measure for Multi-pass Streaming with Applications
by: Braverman, Mark, et al.
Published: (2024)

The Parameterized Complexity of Independent Set and More when Excluding a Half-Graph, Co-Matching, or Matching
by: Dreier, Jan, et al.
Published: (2026)

On the Parameterized Complexity of Min-Sum-Radii
by: Kumar, Pankaj, et al.
Published: (2026)

The Complexity of Maximal Common Subsequence Enumeration
by: Buzzega, Giovanni, et al.
Published: (2025)