1 citations · 1 across the 6 of their papers we have counts for
Showing 2024Show all
3 papers · 1 filter
cs.DS2024
#CFG and #DNNF admit FPRAS
Kuldeep S. Meel, Alexis de Colnet
We provide the first fully polynomial-time randomized approximation scheme for the following two counting problems: 1. Given a Context Free Grammar over alphabet , count the…
cs.DS2024
An FPRAS for Model Counting for Non-Deterministic Read-Once Branching Programs
Kuldeep S. Meel, Alexis de Colnet
Non-deterministic read-once branching programs, also known as non-deterministic free binary decision diagrams (nFBDD), are a fundamental data structure in computer science for repr…
cs.CC2024
Hardness of Random Reordered Encodings of Parity for Resolution and CDCL
Leroy Chew, Alexis de Colnet, Friedrich Slivovsky +1
Parity reasoning is challenging for Conflict-Driven Clause Learning (CDCL) SAT solvers. This has been observed even for simple formulas encoding two contradictory parity constraint…