6 papers
Quadratic Sums-of-Powers for Fixed-Parameter Tractable Quantum-Circuit Simulation
Alexis de Colnet, Floris Geerts, Rihan Hai +4
Strongly simulating a quantum circuit, that is, computing an output amplitude, can be done by summing the circuit's Feynman paths: a weighted count over assignments to Boolean path…
The Compilability Thresholds of 2-CNF to OBDD
Alexis de Colnet, Alfons Laarman, Joon Hyung Lee
We prove the existence of two thresholds regarding the compilability of random 2-CNF formulas to OBDDs. The formulas are drawn from , the uniform distribution…
#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 th…
From Tensor Networks to Tractable Circuits, and back
Arend-Jan Quist, Marc Farreras Bartra, Alexis de Colnet +2
Tensor networks and circuits are widely used data structures to represent pseudo-Boolean functions. These two formalisms have been studied primarily in separate communities, and th…
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…
Compilation and Fast Model Counting beyond CNF
Alexis de Colnet, Stefan Szeider, Tianwei Zhang
Circuits in deterministic decomposable negation normal form (d-DNNF) are representations of Boolean functions that enable linear-time model counting. This paper strengthens our the…