Image de couverture de livre

Enumerating models of DNF faster: breaking the dependency on the formula size

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Capelli, Florent, Strozecki, Yann
Format:	Preprint
Publié:	2018
Sujets:	Computational Complexity Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

From Amortized to Worst Case Delay in Enumeration Algorithms
par: Capelli, Florent, et autres
Publié: (2021)

Complexity of Finding and Enumerating Interconnection Trees
par: Demange, Noé, et autres
Publié: (2026)

DNF formulas are efficiently testable with relative error
par: Chen, Xi, et autres
Publié: (2026)

Gray Codes With Constant Delay and Constant Auxiliary Space
par: Amarilli, Antoine, et autres
Publié: (2026)

Local Enumeration: The Not-All-Equal Case
par: Gurumukhani, Mohit, et autres
Publié: (2025)

The Complexity of Maximal Common Subsequence Enumeration
par: Buzzega, Giovanni, et autres
Publié: (2025)

On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs
par: Kurita, Kazuhiro, et autres
Publié: (2025)

Emit As You Go: Enumerating Edges of a Spanning Tree
par: Casel, Katrin, et autres
Publié: (2025)

Self-referential instances of the dominating set problem are irreducible
par: Zhou, Guangyan
Publié: (2026)

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
par: Chakraborty, Dibyayan, et autres
Publié: (2024)

Isometric path complexity of graphs
par: Chakraborty, Dibyayan, et autres
Publié: (2022)

Sequence graphs realizations and ambiguity in language models
par: Khalife, Sammy, et autres
Publié: (2024)

A number-theoretic conjecture implying faster algorithms for polynomial factorization and integer factorization
par: Umans, Chris, et autres
Publié: (2025)

A faster FPRAS for #NFA
par: Meel, Kuldeep S., et autres
Publié: (2023)

Enumeration of minimal transversals of hypergraphs of bounded VC-dimension
par: Mary, Arnaud
Publié: (2024)

Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
par: Chakraborty, Dipayan, et autres
Publié: (2024)

Enumeration and updates for conjunctive linear algebra queries through expressibility
par: Muñoz, Thomas, et autres
Publié: (2023)

An unconditional lower bound for the active-set method on the hypercube
par: Disser, Yann, et autres
Publié: (2025)

Ranked Enumeration for MSO on Trees via Knowledge Compilation
par: Amarilli, Antoine, et autres
Publié: (2023)

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
par: Foucaud, Florent, et autres
Publié: (2023)

Metric Dimension and Geodetic Set Parameterized by Vertex Cover
par: Foucaud, Florent, et autres
Publié: (2024)

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
par: Huang, Neng, et autres
Publié: (2024)

Small Hazard-free Transducers
par: Bund, Johannes, et autres
Publié: (2018)

Colouring $(P_r+P_s)$-Free Graphs
par: Klimošová, Tereza, et autres
Publié: (2018)

On graphs coverable by k shortest paths
par: Dumas, Maël, et autres
Publié: (2022)

Neighborhood-Aware Graph Labeling Problem
par: Shahverdikondori, Mohammad, et autres
Publié: (2026)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
par: Greilhuber, Jakob, et autres
Publié: (2025)

Lazy Kronecker Product
par: Song, Zhao
Publié: (2026)

The Trichotomy of Regular Property Testing
par: Bathie, Gabriel, et autres
Publié: (2025)

Complexity of Local Search for Euclidean Clustering Problems
par: Manthey, Bodo, et autres
Publié: (2023)

Can You Link Up With Treewidth?
par: Curticapean, Radu, et autres
Publié: (2024)

Downward self-reducibility in the total function polynomial hierarchy
par: Gajulapalli, Karthik, et autres
Publié: (2025)

Tight Additive Sensitivity on LZ-style Compressors and String Attractors
par: Fujie, Yuto, et autres
Publié: (2025)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
par: Moroie, Gregory
Publié: (2025)

Precoloring extension with demands on paths
par: Das, Arun Kumar, et autres
Publié: (2025)

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
par: Gholizadeh, Hossein, et autres
Publié: (2025)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
par: Herrmann, Anton, et autres
Publié: (2025)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
par: Assadi, Sepehr, et autres
Publié: (2025)

Exact Matching and Top-k Perfect Matching Parameterized by Neighborhood Diversity or Bandwidth
par: Maalouly, Nicolas El, et autres
Publié: (2025)

k-SUM Hardness Implies Treewidth-SETH
par: Lampis, Michael
Publié: (2025)