3 papers
cs.DS2026
Online Orthogonal Vectors Revisited
Karthik Gajulapalli, Alexander Golovnev, Samuel King +1
We prove new upper and lower bounds for the Online Orthogonal Vectors Problem (). In this problem, a preprocessing algorithm receives vectors $x_1,\ldo…
cs.CC2025
Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust Daisies
Guy Goldberg, Tom Gur, Sidhant Saraogi
We show a nearly optimal lower bound on the length of linear relaxed locally decodable codes (RLDCs). Specifically, we prove that any -query linear RLDC $C\colon \{0,1\}^k \to \…
cs.CC2025
Downward self-reducibility in the total function polynomial hierarchy
Karthik Gajulapalli, Surendra Ghentiyala, Zeyong Li +1
A problem is considered downward self-reducible, if there exists an efficient algorithm for that is allowed to make queries to only strictly smaller ins…