Buchumschlag

New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Fischer, Nick, Jin, Ce, Xu, Yinzhan
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
von: Jin, Ce, et al.
Veröffentlicht: (2024)

Sumsets, 3SUM, Subset Sum: Now for Real!
von: Fischer, Nick
Veröffentlicht: (2024)

Faster Algorithms for Text-to-Pattern Hamming Distances
von: Chan, Timothy M., et al.
Veröffentlicht: (2023)

Deterministic Monotone Min-Plus Product and Convolution
von: Jin, Ce, et al.
Veröffentlicht: (2026)

Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses
von: Fischer, Nick
Veröffentlicht: (2026)

Near-Optimal Property Testers for Pattern Matching
von: Jin, Ce, et al.
Veröffentlicht: (2025)

New Separations and Reductions for Directed Preservers and Hopsets
von: Hoppenworth, Gary, et al.
Veröffentlicht: (2024)

Approximately Counting Knapsack Solutions in Subquadratic Time
von: Feng, Weiming, et al.
Veröffentlicht: (2024)

The Fine-Grained Complexity of Episode Matching
von: Bille, Philip, et al.
Veröffentlicht: (2021)

3SUM in Preprocessed Universes: Faster and Simpler
von: Kasliwal, Shashwat, et al.
Veröffentlicht: (2024)

Improved Time-Space Tradeoffs for 3SUM-Indexing
von: Dinur, Itai, et al.
Veröffentlicht: (2025)

Preprocessed 3SUM for Unknown Universes with Subquadratic Space
von: Kirkpatrick, Yael, et al.
Veröffentlicht: (2026)

All-Pairs Shortest Paths with Few Weights per Node
von: Abboud, Amir, et al.
Veröffentlicht: (2025)

Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
von: Black, Hadley, et al.
Veröffentlicht: (2025)

The Communication Complexity of Pattern Matching with Edits Revisited
von: Kociumaka, Tomasz, et al.
Veröffentlicht: (2026)

All-Hops Shortest Paths
von: Williams, Virginia Vassilevska, et al.
Veröffentlicht: (2024)

Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
von: Dalirrooyfard, Mina, et al.
Veröffentlicht: (2023)

Internal Pattern Matching in Small Space and Applications
von: Bathie, Gabriel, et al.
Veröffentlicht: (2024)

Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection
von: Dudek, Bartłomiej, et al.
Veröffentlicht: (2026)

Fine-Grained Complexity of Multiple Domination and Dominating Patterns in Sparse Graphs
von: Künnemann, Marvin, et al.
Veröffentlicht: (2024)

0-1 Knapsack in Nearly Quadratic Time
von: Jin, Ce
Veröffentlicht: (2023)

Memory Reallocation with Polylogarithmic Overhead
von: Jin, Ce
Veröffentlicht: (2026)

Inapproximability of Counting Permutation Patterns
von: Opler, Michal
Veröffentlicht: (2026)

Greedy Dynamic Matching
von: Arnosti, Nick, et al.
Veröffentlicht: (2025)

Data Structures Meet Cryptography: 3SUM with Preprocessing
von: Golovnev, Alexander, et al.
Veröffentlicht: (2019)

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
von: Saha, Barna, et al.
Veröffentlicht: (2024)

On the Communication Complexity of Approximate Pattern Matching
von: Kociumaka, Tomasz, et al.
Veröffentlicht: (2024)

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
von: Nogler, Jakob, et al.
Veröffentlicht: (2024)

Counting Patterns in Degenerate Graphs in Constant Space
von: Komarath, Balagopal, et al.
Veröffentlicht: (2025)

A Faster Algorithm for Pigeonhole Equal Sums
von: Jin, Ce, et al.
Veröffentlicht: (2024)

Fine-Grained Classification Of Detecting Dominating Patterns
von: Dransfeld, Jonathan, et al.
Veröffentlicht: (2025)

Pattern Matching with Mismatches and Wildcards
von: Bathie, Gabriel, et al.
Veröffentlicht: (2024)

Enhanced Graph Pattern Matching
von: Cotumaccio, Nicola
Veröffentlicht: (2024)

Approximate Circular Pattern Matching
von: Charalampopoulos, Panagiotis, et al.
Veröffentlicht: (2022)

Dynamic Pattern Matching with Wildcards
von: Naeini, Arshia Ataee, et al.
Veröffentlicht: (2026)

Pattern Masking for Dictionary Matching
von: Charalampopoulos, Panagiotis, et al.
Veröffentlicht: (2020)

Quantum Pattern Matching with Wildcards
von: Seddighin, Masoud, et al.
Veröffentlicht: (2025)

Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
von: Fischer, Nick, et al.
Veröffentlicht: (2024)

$\ell_2/\ell_2$ Sparse Recovery via Weighted Hypergraph Peeling
von: Fischer, Nick, et al.
Veröffentlicht: (2025)

Contextual Pattern Mining and Counting
von: Li, Ling, et al.
Veröffentlicht: (2025)