56 citations · 56 across the 4 of their papers we have counts for
6 papers
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…
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…
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 $…
Pulse-level noisy quantum circuits with QuTiP
Boxi Li, Shahnawaz Ahmed, Sidhant Saraogi +4
The study of the impact of noise on quantum circuits is especially relevant to guide the progress of Noisy Intermediate-Scale Quantum (NISQ) computing. In this paper, we address th…