Cover Image

#CFG and #DNNF admit FPRAS

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Meel, Kuldeep S., de Colnet, Alexis
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Towards practical FPRAS for #NFA: Exploiting the Power of Dependence
by: Meel, Kuldeep S., et al.
Published: (2025)

An FPRAS for Model Counting for Non-Deterministic Read-Once Branching Programs
by: Meel, Kuldeep S., et al.
Published: (2024)

A faster FPRAS for #NFA
by: Meel, Kuldeep S., et al.
Published: (2023)

Distance Estimation for High-Dimensional Discrete Distributions
by: Kumar, Gunjan, et al.
Published: (2023)

Equivalence Testing: The Power of Bounded Adaptivity
by: Chakraborty, Diptarka, et al.
Published: (2024)

An FPRAS for two terminal reliability in directed acyclic graphs
by: Feng, Weiming, et al.
Published: (2023)

RIP Linked List
by: Sonntag, Benoît, et al.
Published: (2023)

Approximating Queries on Probabilistic Graphs
by: Amarilli, Antoine, et al.
Published: (2023)

Engineering an Efficient Approximate DNF-Counter
by: Soos, Mate, et al.
Published: (2024)

The Compilability Thresholds of 2-CNF to OBDD
by: de Colnet, Alexis, et al.
Published: (2026)

Computational Explorations of Total Variation Distance
by: Bhattacharyya, Arnab, et al.
Published: (2024)

Algorithms and Hardness for Estimating Statistical Similarity
by: Bhattacharyya, Arnab, et al.
Published: (2025)

CNFs and DNFs with Exactly $k$ Solutions
by: Chandran, L. Sunil, et al.
Published: (2025)

From Tensor Networks to Tractable Circuits, and back
by: Quist, Arend-Jan, et al.
Published: (2026)

Quadratic Sums-of-Powers for Fixed-Parameter Tractable Quantum-Circuit Simulation
by: de Colnet, Alexis, et al.
Published: (2026)

Total Variation Distance Meets Probabilistic Inference
by: Bhattacharyya, Arnab, et al.
Published: (2023)

On the number of $k$-mers admitting a given lexicographical minimizer
by: Ingels, Florian, et al.
Published: (2024)

Algorithms for the local and the global postage stamp problem
by: Palais, Léo Colisson, et al.
Published: (2026)

Dynamic Matroids: Base Packing and Covering
by: de Vos, Tijn, et al.
Published: (2025)

Improving polynomial bounds for the Graphical Traveling Salesman Problem with release dates on paths
by: Clementino, Thailsson, et al.
Published: (2025)

Testing frequency distributions in a stream
by: Mathieu, Claire, et al.
Published: (2023)

Distributed Sparsest Cut via Eigenvalue Estimation
by: Maus, Yannic, et al.
Published: (2025)

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

Exploring Monotone Priority Queues for Dijkstra Optimization
by: Costa, Jonas, et al.
Published: (2024)

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity
by: de Vos, Tijn, et al.
Published: (2024)

Implementation and Brief Experimental Analysis of the Duan et al. (2025) Algorithm for Single-Source Shortest Paths
by: Castro, Lucas, et al.
Published: (2025)

Towards Constant Time Multi-Call Rumor Spreading on Small-Set Expanders
by: Cruciani, Emilio, et al.
Published: (2025)

Deterministic Edge Coloring with few Colors in CONGEST
by: Blikstad, Joakim, et al.
Published: (2026)

Disjoint Tours and the Price of Diversity
by: de Berg, Mark, et al.
Published: (2025)

Optimal Extended Formulations from Optimal Dynamic Programming Algorithms
by: Oliveira, Mateus de Oliveira, et al.
Published: (2026)

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
by: Dory, Michal, et al.
Published: (2022)

On the power of standard DFS and BFS
by: Bui-Xuan, Binh-Minh, et al.
Published: (2026)

Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances
by: Brand, Jan van den, et al.
Published: (2025)

Space/time-efficient RDF stores based on circular suffix sorting
by: Brisaboa, Nieves R., et al.
Published: (2020)

Edge-Minimum Walk of Modular Length in Polynomial Time
by: Amarilli, Antoine, et al.
Published: (2024)

Concurrent Composition for Differentially Private Continual Mechanisms
by: Henzinger, Monika, et al.
Published: (2024)

Weighted Reservoir Sampling With Replacement from Data Streams
by: Meligrana, Adriano, et al.
Published: (2024)

A Comprehensive Survey of Data Reduction Rules for the Maximum Weighted Independent Set Problem
by: Großmann, Ernestine, et al.
Published: (2024)

Single-Source Regular Path Querying in Terms of Linear Algebra
by: Belyanin, Georgiy, et al.
Published: (2024)

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
by: Nogler, Jakob, et al.
Published: (2024)