4 papers
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…
Near Neighbor Search via Efficient Average Distortion Embeddings
Deepanshu Kush, Aleksandar Nikolov, Haohua Tang
A recent series of papers by Andoni, Naor, Nikolov, Razenshteyn, and Waingarten (STOC 2018, FOCS 2018) has given approximate near neighbour search (NNS) data structures for a wide…
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(…
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…