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.CG2025
A Deterministic Bicriteria Approximation Algorithm for the Art Gallery Problem
Khaled Elbassioni
Given a polygon in the plane, the art gallery problem calls for fining the smallest set of points in from which every other point in is seen. We give a deterministic al…