Deepanshu Kush
Deepanshu Kush
Embedded Files
I am a final-year PhD student in the Department of Computer Science at the University of Toronto, where I am part of the Theory Group and co-supervised by Benjamin Rossman and Shubhangi Saraf. I will join the Department of Computer Science & Technology at the University of Cambridge as a postdoc under Tom Gur, starting Fall 2025. Previously, I studied mathematics as an undergrad at IIT Bombay, where I was advised by Niranjan Balachandran and Srikanth Srinivasan.
My primary area of research is computational complexity theory, but I am also more broadly interested in theoretical computer science and combinatorics, and their connections to other areas of mathematics. Some of the things I am always happy to talk about include, in no particular order, tennis, psychology, football, and Indian cooking!
My email address is <deepkush [at] cs [dot] toronto [dot] edu>.
Publications
Publications
Polynomial-Time PIT from (Almost) Necessary Assumptions (with Robert Andrews and Roei Tell)
To appear in 57th ACM Symposium on Theory of Computing (STOC 2025)
Conference Version | arXiv | ECCC | talk for STOC (June '25)
Lower Bounds for Set-Multilinear Branching Programs (with Prerona Chatterjee, Shubhangi Saraf, and Amir Shpilka)
In Proceedings of 39th Computational Complexity Conference (CCC 2024)
Conference Version | arXiv | ECCC
Near-Optimal Set-Multilinear Formula Lower Bounds (with Shubhangi Saraf)
In Proceedings of 38th Computational Complexity Conference (CCC 2023)
Conference Version | ECCC | talk for CCC (July '23)
Improved Low-Depth Set-Multilinear Circuit Lower Bounds (with Shubhangi Saraf)
In Proceedings of 37th Computational Complexity Conference (CCC 2022)
Conference Version | arXiv | ECCC | talk for CCC (July '22)
Near Neighbor Search via Efficient Average Distortion Embeddings (with Aleksandar Nikolov and Haohua Tang)
In Proceedings of 37th International Symposium on Computational Geometry (SoCG 2021)
Invited to the Journal Special Issue
Tree-depth and the Formula Complexity of Subgraph Isomorphism (with Benjamin Rossman)
In Proceedings of 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS 2020)
In SIAM Journal on Computing (SICOMP) Volume 52, Issue 1
Journal Version | Conference Version | arXiv | ECCC | talk for FOCS (November '20)
The Normalized Matching Property in Random and Pseudorandom Bipartite Graphs (with Niranjan Balachandran)
In The Electronic Journal of Combinatorics (E-JC) Volume 28, Issue 2
A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates (with Swapnam Bajpai, Vaibhav Krishan, Nutan Limaye, and Srikanth Srinivasan)
In Proceedings of 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
In Algorithmica Volume 84, Issue 4
Additional Manuscripts
Additional Manuscripts
A Faster Algorithm for 0-1 Integer Programming from Communication Complexity (with Srikanth Srinivasan)
Note: The SoCG 2017 paper by Timothy Chan, among other things, implies the main result in this write-up using a similar reduction of 0-1 Integer Programming to Orthogonal Vectors. We were unaware of this work at the time of writing but were thereafter informed of it by Ryan Williams.
In Resonance Journal, Volume 22, Issue 9, September 2017, pp 879-887
(First half of) Master's Project: Orthogonal Vectors and Related Problems
(Second half subsumed in the paper above with Niranjan)
Teaching
Teaching
I was the course instructor for CSC373 (Algorithm Design, Analysis & Complexity) for the Summer 2022 term. The course webpage can be found here.
Page updated
Google Sites
Report abuse