All reports by Author Deepanshu Kush:

__
TR20-061
| 28th April 2020
__

Deepanshu Kush, Benjamin Rossman#### Tree-depth and the Formula Complexity of Subgraph Isomorphism

__
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

Deepanshu Kush, Benjamin Rossman

For a fixed "pattern" graph $G$, the $\textit{colored}$ $G\textit{-subgraph isomorphism problem}$ (denoted $\mathrm{SUB}(G)$) asks, given an $n$-vertex graph $H$ and a coloring $V(H) \to V(G)$, whether $H$ contains a properly colored copy of $G$. The complexity of this problem is tied to parameterized versions of $\mathit{P}$ ${=}?$ $\mathit{NP}$ and $\mathit{L}$ ... 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 >>>