Image de couverture de livre

Single Family Algebra Operation on BDDs and ZDDs Leads To Exponential Blow-Up

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Nakamura, Kengo, Nishino, Masaaki, Denzumi, Shuhei
Format:	Preprint
Publié:	2024
Sujets:	Data Structures and Algorithms Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

On the sizes of BDDs and ZDDs representing matroids
par: Emoto, Hiromi, et autres
Publié: (2024)

Linear-Time Exact Computation of Influence Spread on Bounded-Pathwidth Graphs
par: Nakamura, Kengo, et autres
Publié: (2026)

Scalable Neighborhood Local Search for Single-Machine Scheduling with Family Setup Times
par: Balzereit, Kaja, et autres
Publié: (2024)

Treedepth Inapproximability and Exponential ETH Lower Bound
par: Bonnet, Édouard, et autres
Publié: (2025)

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

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

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
par: Buhrman, Harry, et autres
Publié: (2025)

A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
par: Jansen, Klaus, et autres
Publié: (2025)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
par: Esmer, Barış Can, et autres
Publié: (2022)

Tensor Decomposition Meets Knowledge Compilation: A Study Comparing Tensor Trains with OBDDs
par: Onaka, Ryoma, et autres
Publié: (2025)

Variance Computation for Weighted Model Counting with Knowledge Compilation Approach
par: Nakamura, Kengo, et autres
Publié: (2026)

Near-Optimality for Single-Source Personalized PageRank
par: Jiang, Xinpeng, et autres
Publié: (2025)

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

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
par: Singer, Noah G., et autres
Publié: (2026)

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

Identity Testing for Circuits with Exponentiation Gates
par: Li, Jiatu, et autres
Publié: (2025)

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

Lower Bounds for Linear Operators
par: Ko, Young Kun
Publié: (2025)

Single-copy stabilizer testing
par: Hinsche, Marcel, et autres
Publié: (2024)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
par: Wang, Yichuan
Publié: (2024)

Simple approximation algorithms for Polyamorous Scheduling
par: Biktairov, Yuriy, et autres
Publié: (2024)

Size Minimization For Multi-Output AND-Functions
par: Armbruster, Susanne
Publié: (2024)

TSP Escapes the $O(2^n n^2)$ Curse
par: Stoian, Mihail
Publié: (2024)

Cluster Editing on Cographs and Related Classes
par: Lafond, Manuel, et autres
Publié: (2024)

Improved Hardness-of-Approximation for Token Swapping
par: Hiken, Sam, et autres
Publié: (2024)

Near-Optimal Averaging Samplers and Matrix Samplers
par: Xun, Zhiyang, et autres
Publié: (2024)

On the complexity and approximability of Bounded access Lempel Ziv coding
par: Cicalese, Ferdinando, et autres
Publié: (2024)

Parameterized Vertex Integrity Revisited
par: Hanaka, Tesshu, et autres
Publié: (2024)

On approximability of the Permanent of PSD matrices
par: Ebrahimnejad, Farzam, et autres
Publié: (2024)

Further Explanations on "SAT Requires Exhaustive Search"
par: Dong, Qingxiu, et autres
Publié: (2024)

PCF Learned Sort: a Learning Augmented Sort Algorithm with $O(n \log\log n)$ Expected Complexity
par: Sato, Atsuki, et autres
Publié: (2024)

Randomized query composition and product distributions
par: Sanyal, Swagato
Publié: (2024)

Minimizing the Weighted Number of Tardy Jobs is W[1]-hard
par: Heeger, Klaus, et autres
Publié: (2024)

The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
par: Stoian, Mihail
Publié: (2024)

On Permutation Selectors and their Applications in Ad-Hoc Radio Networks Protocols
par: Kuschner, Jordan, et autres
Publié: (2024)

A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients
par: Yang, Yang
Publié: (2024)

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
par: Kumar, Mrinal, et autres
Publié: (2024)

Solving Polynomial Equations Over Finite Fields
par: Dell, Holger, et autres
Publié: (2024)

The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
par: Bentert, Matthias, et autres
Publié: (2024)

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