Buchumschlag

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

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Nakamura, Kengo, Nishino, Masaaki, Denzumi, Shuhei
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

On the sizes of BDDs and ZDDs representing matroids
von: Emoto, Hiromi, et al.
Veröffentlicht: (2024)

Linear-Time Exact Computation of Influence Spread on Bounded-Pathwidth Graphs
von: Nakamura, Kengo, et al.
Veröffentlicht: (2026)

Scalable Neighborhood Local Search for Single-Machine Scheduling with Family Setup Times
von: Balzereit, Kaja, et al.
Veröffentlicht: (2024)

Treedepth Inapproximability and Exponential ETH Lower Bound
von: Bonnet, Édouard, et al.
Veröffentlicht: (2025)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

Can You Link Up With Treewidth?
von: Curticapean, Radu, et al.
Veröffentlicht: (2024)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
von: Buhrman, Harry, et al.
Veröffentlicht: (2025)

A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
von: Jansen, Klaus, et al.
Veröffentlicht: (2025)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
von: Esmer, Barış Can, et al.
Veröffentlicht: (2022)

Tensor Decomposition Meets Knowledge Compilation: A Study Comparing Tensor Trains with OBDDs
von: Onaka, Ryoma, et al.
Veröffentlicht: (2025)

Variance Computation for Weighted Model Counting with Knowledge Compilation Approach
von: Nakamura, Kengo, et al.
Veröffentlicht: (2026)

Near-Optimality for Single-Source Personalized PageRank
von: Jiang, Xinpeng, et al.
Veröffentlicht: (2025)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
von: Singer, Noah G., et al.
Veröffentlicht: (2026)

Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
von: Chakraborty, Dipayan, et al.
Veröffentlicht: (2024)

Identity Testing for Circuits with Exponentiation Gates
von: Li, Jiatu, et al.
Veröffentlicht: (2025)

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
von: Foucaud, Florent, et al.
Veröffentlicht: (2023)

Lower Bounds for Linear Operators
von: Ko, Young Kun
Veröffentlicht: (2025)

Single-copy stabilizer testing
von: Hinsche, Marcel, et al.
Veröffentlicht: (2024)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
von: Wang, Yichuan
Veröffentlicht: (2024)

Simple approximation algorithms for Polyamorous Scheduling
von: Biktairov, Yuriy, et al.
Veröffentlicht: (2024)

Size Minimization For Multi-Output AND-Functions
von: Armbruster, Susanne
Veröffentlicht: (2024)

TSP Escapes the $O(2^n n^2)$ Curse
von: Stoian, Mihail
Veröffentlicht: (2024)

Cluster Editing on Cographs and Related Classes
von: Lafond, Manuel, et al.
Veröffentlicht: (2024)

Improved Hardness-of-Approximation for Token Swapping
von: Hiken, Sam, et al.
Veröffentlicht: (2024)

Near-Optimal Averaging Samplers and Matrix Samplers
von: Xun, Zhiyang, et al.
Veröffentlicht: (2024)

On the complexity and approximability of Bounded access Lempel Ziv coding
von: Cicalese, Ferdinando, et al.
Veröffentlicht: (2024)

Parameterized Vertex Integrity Revisited
von: Hanaka, Tesshu, et al.
Veröffentlicht: (2024)

On approximability of the Permanent of PSD matrices
von: Ebrahimnejad, Farzam, et al.
Veröffentlicht: (2024)

Further Explanations on "SAT Requires Exhaustive Search"
von: Dong, Qingxiu, et al.
Veröffentlicht: (2024)

PCF Learned Sort: a Learning Augmented Sort Algorithm with $O(n \log\log n)$ Expected Complexity
von: Sato, Atsuki, et al.
Veröffentlicht: (2024)

Randomized query composition and product distributions
von: Sanyal, Swagato
Veröffentlicht: (2024)

Minimizing the Weighted Number of Tardy Jobs is W[1]-hard
von: Heeger, Klaus, et al.
Veröffentlicht: (2024)

The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
von: Stoian, Mihail
Veröffentlicht: (2024)

On Permutation Selectors and their Applications in Ad-Hoc Radio Networks Protocols
von: Kuschner, Jordan, et al.
Veröffentlicht: (2024)

A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients
von: Yang, Yang
Veröffentlicht: (2024)

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
von: Kumar, Mrinal, et al.
Veröffentlicht: (2024)

Solving Polynomial Equations Over Finite Fields
von: Dell, Holger, et al.
Veröffentlicht: (2024)

The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
von: Bentert, Matthias, et al.
Veröffentlicht: (2024)

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
von: Chakraborty, Dibyayan, et al.
Veröffentlicht: (2024)