All reports by Author Vaibhav Krishan:

__
TR21-031
| 3rd March 2021
__

Vaibhav Krishan#### Upper Bound for Torus Polynomials

__
TR18-162
| 16th September 2018
__

Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan#### A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates

Vaibhav Krishan

We prove that all functions that have low degree torus polynomials approximating them with small error also have $MidBit^+$ circuits computing them. This serves as a partial converse to the result that all $ACC$ functions have low degree torus polynomials approximating them with small error, by Bhrushundi, Hosseini, Lovett and ... more >>>

Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan

We show that there is a randomized algorithm that, when given a small constant-depth Boolean circuit $C$ made up of gates that compute constant-degree Polynomial Threshold functions or PTFs (i.e., Boolean functions that compute signs of constant-degree polynomials), counts the number of satisfying assignments to $C$ in significantly better than ... more >>>