For a quantified Boolean formula (QBF), the problem of computing the number of winning strategies is known as the #QBF problem. This problem is considered harder than the analogous #SAT problem. Recently, important proof systems for QBFs and #SAT have been studied. By extending the ideas from both fields, we ... more >>>

We show that the bipartite matching problem is in NC. We extend the result to weighted bipartite matching and the computation of the noncommutative rank of a symbolic matrix. In particular, this implies that the decision version of linear matroid intersection is in NC as well. The techniques are based ... more >>>

We prove that level-$\ell$ Kikuchi graphs of random $2r$-uniform hypergraphs spectrally approximate Kikuchi graph of the complete $2r$-uniform hypergraph at a sampling rate that is sharp up to a logarithmic factor, in the regime $r\leq \ell \leq n/2$. Our proof is based on the matrix Bernstein inequality, but, unlike prior ... more >>>