1 citations · 2 across the 13 of their papers we have counts for
18 papers
Geometric Graph Representations via Compact SAT Encodings
L. Sunil Chandran, Rishikesh Gajjala, Suraj Kumar Sahoo +1
We present compact SAT encodings and certifying exact solvers for boxicity and cubicity. The boxicity of a graph is the minimum dimension in which it is the intersection graph of a…
Connectivity Bounds for GHZ Graphs
L. Sunil Chandran, Rishikesh Gajjala
Greenberger-Horne-Zeilinger (GHZ) states are multipartite entangled quantum states that play a central role in quantum information theory, with applications in quantum communicatio…
Towards Learning-Guided Discovery of Extremal Geometric Constructions: A PatternBoost Study
Deepak Ajwani, Paula Carroll, Rishikesh Gajjala +5
Extremal constructions play a central role in the design and analysis of algorithms. Integrality-gap instances expose the limitations of relaxations, while hard configurations reve…
Random Garbage Separates XOR from Forward-Only Queries
Khaled Elbassioni, Rishikesh Gajjala, Saurabh Ray
We give exponential quantum query separations between the standard XOR interface and two forward-only interfaces that supply neither an adjoint nor an inverse oracle. Let $X=\F_2^n…
Tight Approximation Thresholds for Geometric Stabbing
Khaled Elbassioni, Rishikesh Gajjala, Saurabh Ray
We study geometric covering problems: stabbing axis-parallel squares and cubes by coordinate hyperplanes, stabbing horizontal segments by horizontal and vertical lines, and transve…
Two-copy nondistillability of Werner states: sharp partial-trace inequalities and finite-copy extensions
Kishor Bharti, Rishikesh Gajjala, Tobias Haug
We solve the two-copy distillability problem for Werner states in every local dimension. Our main matrix result is a sharp, dimension-free inequality: for every rank-at-most-two op…
Counterexamples to Wegner's Conjecture for Rectangles
Deepak Ajwani, Rishikesh Gajjala, Rajiv Raman +1
Wegner conjectured in 1965 that every finite family of axis-parallel rectangles satisfies , where is the minimum num…
Counterexamples to an Extremal Conjecture for Random Cycle-Factors
Rishikesh Gajjala
Christoph, Draganić, Girão, Hurley, Michel, and Müyesser conjectured that, when , the expected number of cycles in a uniformly random cycle-factor of a directed -regula…
W-state graphs: Structure and Algorithms
Rishikesh Gajjala, Saurabh Ray, Dimitrios M. Thilikos
We study the class of edge-coloured graphs arising from the graph-theoretic representation of quantum photonic experiments that generate multipartite W-states. Abstracting away phy…
CNFs and DNFs with Exactly Solutions
L. Sunil Chandran, Rishikesh Gajjala, Kuldeep S. Meel
Model counting is a fundamental problem that consists of determining the number of satisfying assignments for a given Boolean formula. The weighted variant, which computes the weig…
Two Results on LPT: A Near-Linear Time Algorithm and Parcel Delivery using Drones
L. Sunil Chandran, Rishikesh Gajjala, Shravan Mehra +1
The focus of this paper is to increase our understanding of the Longest Processing Time First (LPT) heuristic. LPT is a classical heuristic for the fundamental problem of uniform m…
Krenn-Gu conjecture for sparse graphs
L. Sunil Chandran, Rishikesh Gajjala, Abraham M. Illickan
Greenberger-Horne-Zeilinger (GHZ) states are quantum states involving at least three entangled particles. They are of fundamental interest in quantum information theory, and the co…
Improved upper bounds for the Heilbronn's Problem for -gons
Rishikesh Gajjala, Jayanth Ravi
The Heilbronn triangle problem asks for the placement of points in a unit square that maximizes the smallest area of a triangle formed by any three of those points. In ,…
No distributed quantum advantage for approximate graph coloring
Xavier Coiteux-Roy, Francesco d'Amore, Rishikesh Gajjala +7
We give an almost complete characterization of the hardness of -coloring -chromatic graphs with distributed algorithms, for a wide range of models of distributed computing. I…
Graph-theoretic insights on the constructability of complex entangled states
L. Sunil Chandran, Rishikesh Gajjala
The most efficient automated way to construct a large class of quantum photonic experiments is via abstract representation of graphs with certain properties. While new directions w…
Edge-coloured graphs with only monochromatic perfect matchings and their connection to quantum physics
L. Sunil Chandran, Rishikesh Gajjala
Krenn, Gu and Zeilinger initiated the study of PMValid edge-colourings because of its connection to a problem from quantum physics. A graph is defined to have a PMValid -edge-co…
Learning Sparse Fixed-Structure Gaussian Bayesian Networks
Arnab Bhattacharyya, Davin Choo, Rishikesh Gajjala +2
Gaussian Bayesian networks (a.k.a. linear Gaussian structural equation models) are widely used to model causal interactions among continuous variables. In this work, we study the p…
Generalizations of Length Limited Huffman Coding for Hierarchical Memory Settings
Shashwat Banchhor, Rishikesh Gajjala, Yogish Sabharwal +1
In this paper, we study the problem of designing prefix-free encoding schemes having minimum average code length that can be decoded efficiently under a decode cost model that capt…