Deepanshu Kush

23 papers A* 3A 4Journal 16
YearRankTypeTitle / Venue / Authors
2025 A* conf
Polynomial-Time PIT from (Almost) Necessary Assumptions.
STOC
Robert Andrews, Deepanshu Kush, Roei Tell
2025 J jnl
Polynomial-Time PIT from (Almost) Necessary Assumptions.
CoRR
Robert Andrews, Deepanshu Kush, Roei Tell
2025 J jnl
Polynomial-Time PIT from (Almost) Necessary Assumptions.
Electron. Colloquium Comput. Complex.
Robert Andrews, Deepanshu Kush, Roei Tell
2024 A conf
Lower Bounds for Set-Multilinear Branching Programs.
CCC
Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka
2023 J jnl
Exponential Lower Bounds Against Sums of ROABPs.
Electron. Colloquium Comput. Complex.
Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka
2023 J jnl
Lower Bounds for Set-Multilinear Branching Programs.
CoRR
Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka
2023 A conf
Near-Optimal Set-Multilinear Formula Lower Bounds.
CCC
Deepanshu Kush, Shubhangi Saraf
2023 J jnl
Near-Optimal Set-Multilinear Formula Lower Bounds.
Electron. Colloquium Comput. Complex.
Deepanshu Kush, Shubhangi Saraf
2023 J jnl
Tree-Depth and the Formula Complexity of Subgraph Isomorphism.
SIAM J. Comput.
Deepanshu Kush, Benjamin Rossman
2022 J jnl
A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates.
Algorithmica
Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan
2022 A conf
Improved Low-Depth Set-Multilinear Circuit Lower Bounds.
CCC
Deepanshu Kush, Shubhangi Saraf
2022 J jnl
Improved Low-Depth Set-Multilinear Circuit Lower Bounds.
CoRR
Deepanshu Kush, Shubhangi Saraf
2022 J jnl
Improved Low-Depth Set-Multilinear Circuit Lower Bounds.
Electron. Colloquium Comput. Complex.
Deepanshu Kush, Shubhangi Saraf
2021 A* conf
Near Neighbor Search via Efficient Average Distortion Embeddings.
SoCG
Deepanshu Kush, Aleksandar Nikolov, Haohua Tang
2021 J jnl
Near Neighbor Search via Efficient Average Distortion Embeddings.
CoRR
Deepanshu Kush, Aleksandar Nikolov, Haohua Tang
2021 J jnl
The Normalized Matching Property in Random and Pseudorandom Bipartite Graphs.
Electron. J. Comb.
Niranjan Balachandran, Deepanshu Kush
2020 A* conf
Tree-depth and the Formula Complexity of Subgraph Isomorphism.
FOCS
Deepanshu Kush, Benjamin Rossman
2020 J jnl
Tree-depth and the Formula Complexity of Subgraph Isomorphism.
CoRR
Deepanshu Kush, Benjamin Rossman
2020 J jnl
Tree-depth and the Formula Complexity of Subgraph Isomorphism.
Electron. Colloquium Comput. Complex.
Deepanshu Kush, Benjamin Rossman
2019 A conf
A #SAT Algorithm for Small Constant-Depth Circuits with PTF Gates.
ITCS
Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan
2019 J jnl
The Normalized Matching Property in Random and Pseudorandom Bipartite Graphs.
CoRR
Niranjan Balachandran, Deepanshu Kush
2018 J jnl
A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates.
CoRR
Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan
2018 J jnl
A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates.
Electron. Colloquium Comput. Complex.
Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan