Krenn-Gu conjecture for sparse graphs
Mathematical Foundations of Computer Science (MFCS), Slovakia · Slides
Rishikesh Gajjala
I am a Post-Doctoral Researcher at the Center for Quantum and Topological Systems (CQTS) at New York University in Abu Dhabi. Before this, I completed my PhD in Theoretical Computer Science at the Indian Institute of Science (IISc) and my Bachelor’s degree in Computer Science at the Indian Institute of Technology, Delhi (IITD).
I broadly work in theoretical computer science. These days, I am mostly playing around with the use of various AI tools for Math.
Publications
Author names are alphabetical unless noted otherwise, following common practice in theory venues.
Filter by topic 16 papers
Legend (venues in alphabetical ordering): AISTATS: International Conference on Artificial Intelligence and Statistics; CCCG: Canadian Conference on Computational Geometry; DCC: Data Compression Conference; DistributedML: Workshop on Distributed Machine Learning; FSTTCS: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science; JCTA: Journal of Combinatorial Theory, Series A; MFCS: International Symposium on Mathematical Foundations of Computer Science; Quantum: Quantum journal; SAT: International Conference on Theory and Applications of Satisfiability Testing; STOC: ACM Symposium on Theory of Computing.
| Title | Authors | Venue | Year |
|---|---|---|---|
| A Counterexample to Wegner's Conjecture for Axis-Parallel Rectangles | with Deepak Ajwani, Rajiv Raman and Saurabh Ray | Preprint(disproves a 60 year old conjecture!) | 2026 |
| W-state graphs: Structure and Algorithms | with Saurabh Ray and Dimitrios M. Thilikos | Preprint | 2026 |
| Counterexamples to an Extremal Conjecture for Random Cycle-Factors | single-authored | Preprint | 2026 |
| On the smallest antichain that generates an ideal of a given size | with L. Sunil Chandran and Kuldeep S. Meel | JCTA | 2026 |
| CNFs and DNFs with exactly n solutions | with L. Sunil Chandran and Kuldeep Meel | SAT | 2025 |
| No distributed quantum advantage for approximate graph coloring | with Xavier Coiteux-Roy, Francesco d'Amore, Fabian Kuhn, François Le Gall, Henrik Lievonen, Augusto Modanese, Marc-Olivier Renou, Gustav Schmid and Jukka Suomela | STOC | 2024 |
| Graph-theoretic insights on the constructability of complex entangled states | with L. Sunil Chandran | Quantum | 2024 |
| Graph reduction approach to Krenn-Gu conjecture | with L. Sunil Chandran and Abraham M. Illickan | MFCS | 2024 |
| Two Results on LPT: A Near-Linear Time Algorithm and Parcel Delivery using Drones | with L. Sunil Chandran, Shravan Mehra, Saladi Rahul | FSTTCS | 2024 |
| Improved upper bounds for the Heilbronn’s Problem for k-gons | with Jayanth Ravi | CCCG | 2024 |
| Learning Sparse Fixed-Structure Gaussian Bayesian Networks | with Arnab Bhattacharyya, Davin Choo, Sutanu Gayen and Yuhao Wang | AISTATS | 2022 |
| Edge-coloured graphs with only monochromatic perfect matchings and their connection to quantum physics | with L. Sunil Chandran | PreprintQuantum-Graph Best-Paper Award | 2022 |
| Generalizations of Length Limited Huffman Coding for Hierarchical Memory Settings | with Shashwat Banchhor, Yogish Sabharwal and Sandeep Sen | FSTTCS | 2021 |
| Efficient algorithms for decode efficient prefix codes | with Shashwat Banchhor, Yogish Sabharwal and Sandeep Sen | DCC | 2021 |
| Decode-Efficient Prefix Codes for Hierarchical Memory Models | with Shashwat Banchhor, Yogish Sabharwal and Sandeep Sen | DCC | 2020 |
| Huffman Coding Based Encoding Techniques for Fast Distributed Deep Learning | with Shashwat Banchhor, Ahmed Sayed, Aritra Dutta, Marco Canini, Panos Kalnis | DistributedML | 2020 |
Selected presentations
Talks
A combinatorial problem from weighted model counting
Helsinki CS Theory Seminar
Algorithmic Graph Theory seminar series
No distributed quantum advantage for approximate graph coloring
EECS Research Symposium · Winner of Best Presentation Award
Designing quantum experiments via Graph Theory
PMRF Research Symposium · Winner of Best Poster Award
IISc–MSR Theory Seminar · Quantum Colloquium @ NYU Abu Dhabi
Community
Service
Reviewer
ICALP ’23, NeurIPS ’23, ICML ’24, IWOCA ’24, FOCS ’24, SODA ’25 and NeurIPS ’25.
Teaching Assistant
- Quantum Computing at NYU Abu Dhabi
- Graph Theory and Design & Analysis of Algorithms at IISc Bengaluru
- Introduction to Parallel Programming at IIT Delhi
Mentoring
- Abraham M. Illickan (MFCS 2024, IIT Palakkad → UC Irvine)
- Jayanth Ravi (CCCG 2024, IIT Delhi)
- Shravan Mehra (FSTTCS 2024, IISc Bangalore → Univ. of Birmingham)