3 papers
cs.CC2026
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…
cs.CG2026
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…
cs.CG2026
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…