Cover Image

An FPRAS for Model Counting for Non-Deterministic Read-Once Branching Programs

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

#CFG and #DNNF admit FPRAS
by: Meel, Kuldeep S., et al.
Published: (2024)

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

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)

Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions
by: Cheng, Kuan, et al.
Published: (2025)

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)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
by: Wang, Yichuan
Published: (2024)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
by: Grossman, Ofer, et al.
Published: (2023)

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

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

Deterministic Dynamic Edge Colouring
by: Christiansen, Aleksander B. G.
Published: (2024)

Deterministic Cache-Oblivious Funnelselect
by: Brodal, Gerth Stølting, et al.
Published: (2024)

Packed Acyclic Deterministic Finite Automata
by: Shibata, Hiroki, et al.
Published: (2024)

Deterministic Online Bipartite Edge Coloring
by: Blikstad, Joakim, et al.
Published: (2024)

Faster Pseudo-Deterministic Minimum Cut
by: Kenneth-Mordoch, Yotam
Published: (2026)

Deterministic Mincut in Almost-Linear Time
by: Li, Jason
Published: (2021)

Faster Deterministic Streaming Vertex Coloring
by: Chechik, Shiri, et al.
Published: (2026)

A Note on Deterministic FPTAS for Partition
by: Chen, Lin, et al.
Published: (2025)

Vizing's Theorem in Deterministic Almost-Linear Time
by: Assadi, Sepehr, et al.
Published: (2025)

Fast Practical Compression of Deterministic Finite Automata
by: Bille, Philip, et al.
Published: (2023)

Deterministic Monotone Min-Plus Product and Convolution
by: Jin, Ce, et al.
Published: (2026)

Efficient Deterministic Algorithms for Maximizing Symmetric Submodular Functions
by: Wan, Zongqi, et al.
Published: (2024)

Deterministic Almost-Linear-Time Gomory-Hu Trees
by: Abboud, Amir, et al.
Published: (2025)

Deterministic $k$-Median Clustering in Near-Optimal Time
by: Costa, Martín, et al.
Published: (2025)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
by: Bernstein, Aaron, et al.
Published: (2025)

Deterministic Padded Decompositions and Negative-Weight Shortest Paths
by: Li, Jason
Published: (2025)

A Deterministic Polylogarithmic Competitive Algorithm for Matching with Delays
by: Dufay, Marc, et al.
Published: (2025)

Multi-dimensional Approximate Counting
by: Wang, Dingyu
Published: (2024)

Fast Approximate Counting of Cycles
by: Censor-Hillel, Keren, et al.
Published: (2024)

Inapproximability of Counting Permutation Patterns
by: Opler, Michal
Published: (2026)

The General Expiration Streaming Model: Diameter, $k$-Center, Counting, Sampling, and Friends
by: Blank, Lotte, et al.
Published: (2025)

A Fast Counting-Free Algorithm for Computing Atomic Sets in Feature Models
by: Heß, Tobias, et al.
Published: (2025)

Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture
by: Björklund, Andreas, et al.
Published: (2024)