The Element Extraction Problem and the Cost of Determinism and Limited Adaptivity in Linear Queries

Amit Chakrabarti, Manuel Stoeckl

Two widely-used computational paradigms for sublinear algorithms are using linear measurements to perform computations on a high dimensional input and using structured queries to a…