56 citations · 56 across the 4 of their papers we have counts for
4 papers · 1 filter
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…
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 \…
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…
Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms
Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje +1
Range Avoidance (AVOID) is a total search problem where, given a Boolean circuit , , the task is to find a outside the range of $…