5 papers
On Knowledge Compilation Languages for QBFs
Sravanthi Chede, Vaibhav Krishan, Anil Shukla
In this work, we design knowledge compilation languages for quantified Boolean formulas (QBFs), with a particular focus on model counting. We introduce various languages in increas…
Degree Lower Bounds for Torus Polynomials and vs
Vaibhav Krishan, Sundar Vishwanathan
The class consists of Boolean functions that can be computed by constant-depth circuits of polynomial size with and gates, where is a natural number.…
On Lower Bounds for AND via Torus Polynomials
Vaibhav Krishan, Jayalal Sarma
We explore a torus polynomial approximation based approach towards a long-standing question: whether can be computed by circuits - the class of constant-depth polynomi…
On Proof Systems for #QBF
Sravanthi Chede, Leroy Chew, Vaibhav Krishan +1
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…
A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates
Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush +2
We show that there is a randomized algorithm that, when given a small constant-depth Boolean circuit made up of gates that compute constant-degree Polynomial Threshold function…