9 citations · 72 across the 25 of their papers we have counts for
9 papers · 1 filter
Restructuring Tree Decision Diagrams
Christoph Berkholz, Matthäus Micun, Igor Razgon
Tree Decision Diagrams (TDDs) are a data structure recently introduced by Capelli et al. (SAT 2026). They are structured along a vtree and the size of their canonical form lies bet…
Complexity Analysis of Generalized and Fractional Hypertree Decompositions
Georg Gottlob, Matthias Lanzinger, Reinhard Pichler +1
Hypertree decompositions (HDs), as well as the more powerful generalized hypertree decompositions (GHDs), and the yet more general fractional hypertree decompositions (FHDs) are hy…
Regular resolution for CNFs with almost bounded one-sided treewidth
Andrea Cali, Igor Razgon
We introduce a one-sided incidence tree decomposition of a CNF . This is a tree decomposition of the incidence graph of where the underlying tree is rooted and the set of ba…
Partial matching width and its application to lower bounds for branching programs
Igor Razgon
We introduce a new structural graph parameter called \emph{partial matching width}. For each (sufficiently large) integer , we introduce a class of graphs…
Non-deterministic branching programs with logarithmic repetition cannot efficiently compute small monotone CNFs
Oded Lachish, Igor Razgon
In this paper we establish an exponential lower bound on the size of syntactic non-deterministic read -times branching programs for computing a class of mo…
On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth
Igor Razgon
In this paper we study complexity of an extension of ordered binary decision diagrams (OBDDs) called -OBDDs on CNFs of bounded (primal graph) treewidth. In particular, we show t…