Showing cs.CCShow all
3 papers · 1 filter
cs.CC2022
Improved Low-Depth Set-Multilinear Circuit Lower Bounds
Deepanshu Kush, Shubhangi Saraf
We prove strengthened lower bounds for constant-depth set-multilinear formulas. More precisely, we show that over any field, there is an explicit polynomial in VNP defined over…
cs.CC2020
Tree-depth and the Formula Complexity of Subgraph Isomorphism
Deepanshu Kush, Benjamin Rossman
For a fixed "pattern" graph , the $\textit{colored $G$-subgraph isomorphism problem}$ (denoted ) asks, given an -vertex graph and a coloring $V(H) \to V(…
cs.CC2018
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…