Deepanshu Kush

According to our database, Deepanshu Kush authored at least 10 papers between 2019 and 2026.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2026

An Unconditional Barrier for Proving Multilinear Algebraic Branching Program Lower Bounds.

Deepanshu Kush

Electron. Colloquium Comput. Complex., 2026

2025

Polynomial-Time PIT from (Almost) Necessary Assumptions.

Robert Andrews, Deepanshu Kush, Roei Tell

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

2024

Lower Bounds for Set-Multilinear Branching Programs.

Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka

Proceedings of the 39th Computational Complexity Conference, 2024

2023

Exponential Lower Bounds Against Sums of ROABPs.

Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka

Electron. Colloquium Comput. Complex., 2023

Near-Optimal Set-Multilinear Formula Lower Bounds.

Deepanshu Kush, Shubhangi Saraf

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Improved Low-Depth Set-Multilinear Circuit Lower Bounds.

Deepanshu Kush, Shubhangi Saraf

Proceedings of the 37th Computational Complexity Conference, 2022

2021

The Normalized Matching Property in Random and Pseudorandom Bipartite Graphs.

Niranjan Balachandran, Deepanshu Kush

Electron. J. Comb., 2021

Near Neighbor Search via Efficient Average Distortion Embeddings.

Deepanshu Kush, Aleksandar Nikolov, Haohua Tang

Proceedings of the 37th International Symposium on Computational Geometry, 2021

2020

Tree-depth and the Formula Complexity of Subgraph Isomorphism.

Deepanshu Kush, Benjamin Rossman

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

A #SAT Algorithm for Small Constant-Depth Circuits with PTF Gates.

Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019