We give a \#SAT algorithm for boolean formulas over arbitrary finite bases. Let B_k be the basis composed of all boolean functions on at most k inputs. For B_k-formulas on n inputs of size cn, our algorithm runs in time 2^{n(1-\delta_{c,k})} for \delta_{c,k} = c^{-O(c^2k2^k)}. We also show the average-case ... more >>>

In a recent work, Gryaznov, Pudlák and Talebanfard (CCC '22) introduced a linear variant of read-once
branching programs, with motivations from circuit and proof complexity. Such a read-once linear branching program is
a branching program where each node is allowed to make \mathbb{F}_2-linear queries, and are read-once in the ... more >>>