7 papers
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 UGC Thresholds for Geometric Stabbing Problems
Khaled Elbassioni, Rishikesh Gajjala, Saurabh Ray
Many geometric stabbing problems admit natural covering LPs in which each constraint is a union of consecutive traces on ordered candidate sets. We prove a transfer theorem showing…
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…