Imagen de Portada

Small Hazard-free Transducers

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Bund, Johannes, Lenzen, Christoph, Medina, Moti
Formato:	Preprint
Publicado:	2018
Materias:	Data Structures and Algorithms Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

Model-Agnostic Approximation of Constrained Forest Problems
por: Coupette, Corinna, et al.
Publicado: (2024)

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

Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial
por: Curticapean, Radu, et al.
Publicado: (2025)

PLS-complete problems with lexicographic cost functions: Max-$k$-SAT and Abelian Permutation Orbit Minimization
por: Scheder, Dominik, et al.
Publicado: (2025)

Counting Small Induced Subgraphs: Hardness via Fourier Analysis
por: Curticapean, Radu, et al.
Publicado: (2024)

Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields
por: Wang, Chengu
Publicado: (2026)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
por: Döring, Simon, et al.
Publicado: (2024)

On Detecting $H$-Induced Minors for Small $H$
por: Eagling-Vose, Tala, et al.
Publicado: (2026)

Enumerating models of DNF faster: breaking the dependency on the formula size
por: Capelli, Florent, et al.
Publicado: (2018)

Colouring $(P_r+P_s)$-Free Graphs
por: Klimošová, Tereza, et al.
Publicado: (2018)

Neighborhood-Aware Graph Labeling Problem
por: Shahverdikondori, Mohammad, et al.
Publicado: (2026)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
por: Greilhuber, Jakob, et al.
Publicado: (2025)

Lazy Kronecker Product
por: Song, Zhao
Publicado: (2026)

The Trichotomy of Regular Property Testing
por: Bathie, Gabriel, et al.
Publicado: (2025)

Complexity of Local Search for Euclidean Clustering Problems
por: Manthey, Bodo, et al.
Publicado: (2023)

Can You Link Up With Treewidth?
por: Curticapean, Radu, et al.
Publicado: (2024)

Downward self-reducibility in the total function polynomial hierarchy
por: Gajulapalli, Karthik, et al.
Publicado: (2025)

Tight Additive Sensitivity on LZ-style Compressors and String Attractors
por: Fujie, Yuto, et al.
Publicado: (2025)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
por: Moroie, Gregory
Publicado: (2025)

Precoloring extension with demands on paths
por: Das, Arun Kumar, et al.
Publicado: (2025)

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
por: Gholizadeh, Hossein, et al.
Publicado: (2025)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
por: Herrmann, Anton, et al.
Publicado: (2025)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
por: Assadi, Sepehr, et al.
Publicado: (2025)

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

k-SUM Hardness Implies Treewidth-SETH
por: Lampis, Michael
Publicado: (2025)

Efficient Catalytic Graph Algorithms
por: Cook, James, et al.
Publicado: (2025)

The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
por: Enright, Jessica, et al.
Publicado: (2020)

Minimizing Envy and Maximizing Happiness in Graphical House Allocation
por: Dhar, Anubhav, et al.
Publicado: (2025)

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

Scheduling Problems with Constrained Rejections
por: Davies, Sami, et al.
Publicado: (2025)

Graded Projection Recursion (GPR): Corrections, Obstructions, and Conservative Approximate Matrix Multiplication
por: Uhlmann, Jeffrey
Publicado: (2025)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
por: Jiang, Cheng, et al.
Publicado: (2026)

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

A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
por: Ducoffe, Guillaume
Publicado: (2026)

Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling
por: Asadi, Vahid R., et al.
Publicado: (2026)

Geometric Interpretation of 3-SAT and Phase Transition
por: Gillet, Frederic
Publicado: (2025)

NP-Hardness and a PTAS for the Pinwheel Problem
por: Kleinberg, Robert, et al.
Publicado: (2026)

Streaming Zero-Knowledge Proofs
por: Cormode, Graham, et al.
Publicado: (2023)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
por: Wang, Yichuan
Publicado: (2024)