Showing 2026Show all
2 papers · 1 filter
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 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…