All reports by Author Vaibhav Krishan:

__
TR24-074
| 11th April 2024
__

Vaibhav Krishan, Sundar Vishwanathan#### Towards ACC Lower Bounds using Torus Polynomials

__
TR23-111
| 29th July 2023
__

Vaibhav Krishan#### $\mathit{MidBit}^+$, Torus Polynomials and Non-classical Polynomials: Equivalences for $\mathit{ACC}$ Lower Bounds

__
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, Sundar Vishwanathan

The class $ACC$ consists of Boolean functions that can be computed by constant-depth circuits of polynomial size with $AND, NOT$ and $MOD_m$ gates, where $m$ is a natural number. At the frontier of our understanding lies a widely believed conjecture asserting that $MAJORITY$ does not belong to $ACC$. The Boolean ... more >>>

Vaibhav Krishan

We give a conversion from non-classical polynomials to $\mathit{MidBit}^+$ circuits and vice-versa. This conversion, along with previously known results, shows that torus polynomials, non-classical polynomials and $\mathit{MidBit}^+$ circuits can all be converted to each other. Therefore lower bounds against any of these models lead to lower bounds against all three ... more >>>

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 >>>