Deepanshu Kush
I am a fourth 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. Previously, I studied mathematics as an undergrad at IIT Bombay, where I was advised by Srikanth Srinivasan and Niranjan Balachandran.
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
Near-Optimal Set-Multilinear Formula Lower Bounds (with Shubhangi Saraf)
In Proceedings of 38th Computational Complexity Conference (CCC 2023)
Improved Low-Depth Set-Multilinear Circuit Lower Bounds (with Shubhangi Saraf)
In Proceedings of 37th Computational Complexity Conference (CCC 2022)
Conference Version | arXiv | ECCC
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
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
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
I was the course instructor for CSC373 (Algorithm Design, Analysis & Complexity) for the Summer 2022 term. The course webpage can be found here.