Cover Image

Towards practical FPRAS for #NFA: Exploiting the Power of Dependence

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Meel, Kuldeep S., de Colnet, Alexis
Format:	Preprint
Published:	2025
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)

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)

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

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

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)

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

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

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

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

The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds
by: Bringmann, Karl, et al.
Published: (2023)

Accelerating Maximum Common Subgraph Computation by Exploiting Symmetries
by: Kothalawala, Buddhi, et al.
Published: (2026)

Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous
by: Dogeas, Konstantinos, et al.
Published: (2023)

Exploiting New Properties of String Net Frequency for Efficient Computation
by: Guo, Peaker, et al.
Published: (2024)

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

With a Little Help From My Friends: Exploiting Probability Distribution Advice in Algorithm Design
by: Canonne, Clément L., et al.
Published: (2025)

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

Dependency-Aware Online Caching
by: Dallot, Julien, et al.
Published: (2024)

A practical algorithm for 3-admissibility
by: Awofeso, Christine, et al.
Published: (2025)

Learning Dependency Models for Subset Repair
by: Li, Haoda, et al.
Published: (2025)

Arboricity-Dependent Algorithms for Edge Coloring
by: Bhattacharya, Sayan, et al.
Published: (2023)

Cost Preserving Dependent Rounding for Allocation Problems
by: Rohwedder, Lars, et al.
Published: (2025)

Data-Dependent LSH for the Earth Mover's Distance
by: Jayaram, Rajesh, et al.
Published: (2024)

Density-Dependent Graph Orientation and Coloring in Scalable MPC
by: Ghaffari, Mohsen, et al.
Published: (2026)

Online Dependent Rounding Schemes for Bipartite Matchings, with Applications
by: Joseph, et al.
Published: (2023)

Computing the LZ-End parsing: Easy to implement and practically efficient
by: Dinklage, Patrick
Published: (2024)

Dependent randomized rounding for clustering and partition systems with knapsack constraints
by: Harris, David G., et al.
Published: (2017)

Vehicle Routing with Time-Dependent Travel Times: Theory, Practice, and Benchmarks
by: Blauth, Jannis, et al.
Published: (2022)

Concentration of Submodular Functions and Read-k Families Under Negative Dependence
by: Duppala, Sharmila, et al.
Published: (2023)

On the Inversion Modulo a Power of an Integer
by: Xu, Guangwu, et al.
Published: (2025)

The Power of Migrations in Dynamic Bin Packing
by: Mellou, Konstantina, et al.
Published: (2024)

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

Dependent rounding with strong negative-correlation, and scheduling on unrelated machines to minimize completion time
by: Harris, David G.
Published: (2023)

The Power of Greedy for Online Minimum Cost Matching on the Line
by: Balkanski, Eric, et al.
Published: (2022)

New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries
by: Bhaskara, Aditya, et al.
Published: (2024)

Decremental $(1+ε)$-Approximate Maximum Eigenvector: Dynamic Power Method
by: Adil, Deeksha, et al.
Published: (2024)