Lower Bounds on Adaptive Sensing for Matrix Recovery
Authors: Praneeth Kacham, David Woodruff
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show that any adaptive algorithm that uses k linear measurements in each round and outputs an approximation as in (1) with probability 9/10 must run for t = Ω(log(n2/k)/ log log n) rounds. Our techniques also readily extend to obtain lower bounds on adaptive algorithms for tensor recovery. |
| Researcher Affiliation | Academia | Praneeth Kacham Computer Science Department Carnegie Mellon University pkacham@cs.cmu.edu David P. Woodruff Computer Science Department Carngie Mellon University dwoodruf@cs.cmu.edu |
| Pseudocode | No | The paper focuses on theoretical lower bounds and does not include any pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statements about releasing open-source code or links to a code repository for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not involve empirical studies with datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical studies with dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup or specific hardware used. |
| Software Dependencies | No | The paper is theoretical and does not specify any software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not include details about an experimental setup or hyperparameters. |