3 papers
cs.CC2026
Improved Subexponential Upper Bounds for -Restricted Matching Vector Families
Sidhant Saraogi
Matching Vector families (MVFs) are defined by two ordered lists of vectors in whose inner products satisfy specific residue patterns modulo an integer . Most f…
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…