4 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 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…
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…
Dual Bounded Generation: Polynomial, Second-order Cone and Positive Semidefinite Matrix Inequalities
Khaled Elbassioni
In the monotone integer dualization problem, we are given two sets of vectors in an integer box such that no vector in the first set is dominated by a vector in the second. The que…