6 papers
Tight UGC Thresholds for Geometric Stabbing Problems
Khaled Elbassioni, Rishikesh Gajjala, Saurabh Ray
The paper proves tight hardness thresholds under the Unique Games Conjecture for several geometric stabbing problems by linking integrality‑gap instances of covering LPs to matchin…
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…
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 -reg…
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…