Cover Image

A faster FPRAS for #NFA

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Meel, Kuldeep S., Chakraborty, Sourav, Mathur, Umang
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms Computational Complexity Logic in Computer Science Programming Languages
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)

Efficient Decrease-and-Conquer Linearizability Monitoring
by: Han, Lee Zheng, et al.
Published: (2024)

Counting and Sampling Traces in Regular Languages
by: de Colnet, Alexis, et al.
Published: (2025)

A Tree Clock Data Structure for Causal Orderings in Concurrent Executions
by: Mathur, Umang, et al.
Published: (2022)

First Order Logic on Pathwidth Revisited Again
by: Lampis, Michael
Published: (2022)

Toward a Uniform Algorithm and Uniform Reduction for Constraint Problems
by: Barto, Libor, et al.
Published: (2026)

Fine-grained Meta-Theorems for Vertex Integrity
by: Lampis, Michael, et al.
Published: (2021)

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
by: Brakensiek, Joshua, et al.
Published: (2026)

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

Enumeration and updates for conjunctive linear algebra queries through expressibility
by: Muñoz, Thomas, et al.
Published: (2023)

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

A bargain for mergesorts -- How to prove your mergesort correct and stable, almost for free
by: Cohen, Cyril, et al.
Published: (2024)

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

Automated Expected Amortised Cost Analysis of Probabilistic Data Structures
by: Leutgeb, Lorenz, et al.
Published: (2022)

Verified Purely Functional Catenable Real-Time Deques
by: Viennot, Jules, et al.
Published: (2025)

Polynomial Logical Zonotope: A Set Representation for Reachability Analysis of Logical Systems
by: Alanwar, Amr, et al.
Published: (2023)

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)

Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing
by: Černý, Marek, et al.
Published: (2025)

Transductive Learning Is Compact
by: Asilis, Julian, et al.
Published: (2024)

On Numbers of Simplicial Walks and Equivalent Canonizations for Graph Recognition
by: Černý, Marek
Published: (2026)

Smaller Circuits for Bit Addition
by: Goncharov, Mikhail, et al.
Published: (2025)

The Existential Theory of the Reals as a Complexity Class: A Compendium
by: Schaefer, Marcus, et al.
Published: (2024)

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

Finding hardness reductions automatically using SAT solvers
by: Bergold, Helena, et al.
Published: (2024)

Attractors Is All You Need: Parity Games In Polynomial Time
by: van der Heijden, Rick
Published: (2025)

Enumerating models of DNF faster: breaking the dependency on the formula size
by: Capelli, Florent, et al.
Published: (2018)

The Ideal Membership Problem and Abelian Groups
by: Bulatov, Andrei A., et al.
Published: (2022)

Fair Vertex Problems Parameterized by Cluster Vertex Deletion
by: Masařík, Tomáš, et al.
Published: (2025)

Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
by: Larrauri, Alberto
Published: (2025)

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

On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem
by: Bhaskar, Umang, et al.
Published: (2025)

On the Length of Strongly Monotone Descending Chains over $\mathbb{N}^d$
by: Schmitz, Sylvain, et al.
Published: (2023)

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
by: Chakraborty, Dibyayan, et al.
Published: (2024)

Sequence graphs realizations and ambiguity in language models
by: Khalife, Sammy, et al.
Published: (2024)

Discovering Expert-Level Nash Equilibrium Algorithms with Large Language Models
by: Li, Hanyu, et al.
Published: (2025)

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

A number-theoretic conjecture implying faster algorithms for polynomial factorization and integer factorization
by: Umans, Chris, et al.
Published: (2025)

On the formalization of the notion of an algorithm
by: Middelburg, C. A.
Published: (2024)

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