Cover Image

Lower Bounds on Adaptive Sensing for Matrix Recovery

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kacham, Praneeth, Woodruff, David P
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms Information Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Faster Algorithms for Schatten-p Low Rank Approximation
by: Kacham, Praneeth, et al.
Published: (2024)

Approximating the Top Eigenvector in Random Order Streams
by: Kacham, Praneeth, et al.
Published: (2024)

Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
by: Kacham, Praneeth, et al.
Published: (2023)

High-Dimensional Geometric Streaming for Nearly Low Rank Data
by: Esfandiari, Hossein, et al.
Published: (2024)

Optimal Communication for Classic Functions in the Coordinator Model and Beyond
by: Esfandiari, Hossein, et al.
Published: (2024)

LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions
by: Kannan, Ravindran, et al.
Published: (2024)

Tight Sampling Bounds for Eigenvalue Approximation
by: Swartworth, William, et al.
Published: (2024)

Bounds and Algorithms for Alphabetic Codes and Binary Search Trees
by: Bruno, Roberto, et al.
Published: (2024)

Support Recovery in One-bit Compressed Sensing with Near-Optimal Measurements and Sublinear Time
by: Li, Xiaxin, et al.
Published: (2025)

PTF Testing Lower Bounds for Non-Gaussian Component Analysis
by: Diakonikolas, Ilias, et al.
Published: (2025)

Universal Maximum Likelihood (List) Decoding via Fast Vector-Matrix Multiplication
by: Ly, Hoang, et al.
Published: (2025)

Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut
by: Cheng, Yu, et al.
Published: (2024)

An $Ω( (\log n / \log \log n)^2 )$ Cell-Probe Lower Bound for Dynamic Boolean Data Structures
by: Ko, Young Kun
Published: (2026)

Optimal Binary Variable-Length Codes with a Bounded Number of 1's per Codeword: Design, Analysis, and Applications
by: Bruno, Roberto, et al.
Published: (2025)

Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model
by: Feng, Shiyuan, et al.
Published: (2025)

Better Bounds for the Distributed Experts Problem
by: Woodruff, David P., et al.
Published: (2026)

Better and Simpler Lower Bounds for Differentially Private Statistical Estimation
by: Narayanan, Shyam
Published: (2023)

Achievability of Heterogeneous Hypergraph Recovery from its Graph Projection
by: Morgan, Alexander, et al.
Published: (2026)

Random Reed-Solomon Codes Achieve the Half-Singleton Bound for Insertions and Deletions over Linear-Sized Alphabets
by: Con, Roni, et al.
Published: (2024)

Sharper Bounds for $\ell_p$ Sensitivity Sampling
by: Woodruff, David P., et al.
Published: (2023)

Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness
by: Gribelyuk, Elena, et al.
Published: (2025)

Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold
by: Gu, Yuzhou, et al.
Published: (2025)

Subsampling Suffices for Adaptive Data Analysis
by: Blanc, Guy
Published: (2023)

Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms
by: Li, Yi, et al.
Published: (2024)

Efficient Algorithms for Attributed Graph Alignment with Vanishing Edge Correlation
by: Wang, Ziao, et al.
Published: (2023)

Satisfying the Restricted Isometry Property with the Optimal Number of Rows and Slightly Less Randomness
by: Rao, Shravas
Published: (2023)

Nonadaptive Noise-Resilient Group Testing with Order-Optimal Tests and Fast-and-Reliable Decoding
by: Guruswami, Venkatesan, et al.
Published: (2023)

Preprocessing Uncertain Data into Supersequences for Sorting and Gaps
by: Löffler, Maarten, et al.
Published: (2026)

A probabilistic analysis on general probabilistic scheduling problems
by: Suruga, Daiki
Published: (2024)

Key Compression Limits for $k$-Minimum Value Sketches
by: Dickens, Charlie, et al.
Published: (2024)

Information Theoretic Limits of Cardinality Estimation: Fisher Meets Shannon
by: Pettie, Seth, et al.
Published: (2020)

Capacity-Achieving Gray Codes
by: Guruswami, Venkatesan, et al.
Published: (2024)

Robust Gray Codes Approaching the Optimal Rate
by: Con, Roni, et al.
Published: (2024)

Investigations on Algorithm Selection for Interval-Based Coding Methods
by: Strutz, Tilo, et al.
Published: (2024)

List Decoding Expander-Based Codes via Fast Approximation of Expanding CSPs: I
by: Jeronimo, Fernando Granha, et al.
Published: (2025)

Pcodec: Better Compression for Numerical Sequences
by: Loncaric, Martin, et al.
Published: (2025)

List Decoding Reed--Solomon Codes in the Lee, Euclidean, and Other Metrics
by: Peikert, Chris, et al.
Published: (2025)

Old and New Results on Alphabetic Codes
by: Bruno, Roberto, et al.
Published: (2025)

Efficient $\varepsilon$-approximate minimum-entropy couplings
by: Compton, Spencer
Published: (2025)

Algorithmic Improvements to List Decoding of Folded Reed-Solomon Codes
by: Ashvinkumar, Vikrant, et al.
Published: (2025)