Krenn-Gu conjecture for sparse graphs
Mathematical Foundations of Computer Science (MFCS), Slovakia · Slides
Rishikesh Gajjala
I am a Founding researcher at Pramaana Labs. Prior to this, I spent a wonderful decade doing theoretical computer science across NYU Abu Dhabi, IISc Bengaluru, and IIT Delhi for my postdoc, PhD, and bachelor’s degree, respectively. I enjoy pushing LLMs to their limits on math.
Publications
Author names are alphabetical unless noted otherwise, following common practice in theory venues.
Filter by topic 23 papers
Legend (venues in alphabetical ordering): ALENEX: SIAM Symposium on Algorithm Engineering and Experiments; AISTATS: International Conference on Artificial Intelligence and Statistics; CCCG: Canadian Conference on Computational Geometry; DCC: Data Compression Conference; DistributedML: Workshop on Distributed Machine Learning; E-JC: The Electronic Journal of Combinatorics; FSTTCS: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science; ISAAC: International Symposium on Algorithms and Computation; 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 |
|---|---|---|---|
| Counterexamples to Wegner's Conjecture for Rectangles | with Deepak Ajwani, Rajiv Raman and Saurabh Ray | PreprintDisproves a 60-year-old conjecture | 2026 |
| Random Garbage Separates XOR from Forward-Only Queries | with Khaled Elbassioni and Saurabh Ray | PreprintSolves Aaronson's Open Problem 11 | 2026 |
| Tight UGC Thresholds for Geometric Stabbing Problems | with Khaled Elbassioni and Saurabh Ray | PreprintCloses a 25-year approximation gap | 2026 |
| Two-copy nondistillability of Werner states: sharp partial-trace inequalities and finite-copy extensions | with Kishor Bharti and Tobias Haug | PreprintSolves KCiK Golden Award problem | 2026 |
| On Erdős's Multiplicative Representation Problem | Proof and Lean Formalization by GPT-5.6 Sol | Lean FormalizationErdos 796 | 2026 |
| W-state graphs: Structure and Algorithms | with Saurabh Ray and Dimitrios M. Thilikos | Preprint | 2026 |
| On the smallest antichain that generates an ideal of a given size | with L. Sunil Chandran and Kuldeep S. Meel | JCTA | 2026 |
| Edge-coloured graphs with only monochromatic perfect matchings and their connection to quantum physics | with L. Sunil Chandran | E-JCQuantum-Graph Best-Paper Award | 2026 |
| Geometric Graph Representations via Compact SAT Encodings | with L. Sunil Chandran, Suraj Kumar Sahoo and Aatman Supkar | ALENEX | 2026 |
| Towards Learning-Guided Discovery of Extremal Geometric Constructions: A PatternBoost Study | with Deepak Ajwani, Paula Carroll, Ananta Manoranjan, Rajiv Raman, Ryan O'Connor, Saurabh Ray and Aimen Taha | ALENEX | 2026 |
| Counterexamples to an Extremal Conjecture for Random Cycle-Factors | single-authored | ISAAC | 2026 |
| Connectivity bounds for GHZ graphs | with L. Sunil Chandran | FSTTCS | 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 |
| 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)