8 papers
An Unconditional Barrier for Proving Multilinear Algebraic Branching Program Lower Bounds
Deepanshu Kush
Since the breakthrough superpolynomial multilinear formula lower bounds of Raz (Theory of Computing 2006), proving such lower bounds against multilinear algebraic branching program…
Polynomial-Time PIT from (Almost) Necessary Assumptions
Robert Andrews, Deepanshu Kush, Roei Tell
The celebrated result of Kabanets and Impagliazzo (Computational Complexity, 2004) showed that PIT algorithms imply circuit lower bounds, and vice versa. Since then it has been a m…
Lower Bounds for Set-Multilinear Branching Programs
Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf +1
In this paper, we prove super-polynomial lower bounds for the model of \emph{sum of ordered set-multilinear algebraic branching programs}, each with a possibly different ordering (…
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(…
The Normalized Matching Property in Random and Pseudorandom Bipartite Graphs
Niranjan Balachandran, Deepanshu Kush
A simple generalization of the Hall's condition in bipartite graphs, the Normalized Matching Property (NMP) in a graph with vertex partition states that for any…
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…