16 papers
Rigidity matroids and linear algebraic matroids with applications to matrix completion and tensor codes
Joshua Brakensiek, Manik Dhar, Jiyang Gao +2
We establish a connection between problems studied in rigidity theory and matroids arising from linear algebraic constructions like tensor products and symmetric products. A specia…
Improved Constructions and Lower Bounds for Maximally Recoverable Grid Codes
Joshua Brakensiek, Manik Dhar, Sivakanth Gopi
In this paper, we continue the study of Maximally Recoverable (MR) Grid Codes initiated by Gopalan et al. [SODA 2017]. More precisely, we study codes over an grid topo…
Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Sampler
Sivakanth Gopi, Yin Tat Lee, Daogao Liu +2
The development of efficient sampling algorithms catering to non-Euclidean geometries has been a challenging endeavor, as discretization techniques which succeed in the Euclidean s…
AG Codes Achieve List-decoding Capacity over Constant-sized Fields
Joshua Brakensiek, Manik Dhar, Sivakanth Gopi +1
The recently-emerging field of higher order MDS codes has sought to unify a number of concepts in coding theory. Such areas captured by higher order MDS codes include maximally rec…
Generalized GM-MDS: Polynomial Codes are Higher Order MDS
Joshua Brakensiek, Manik Dhar, Sivakanth Gopi
The GM-MDS theorem, conjectured by Dau-Song-Dong-Yuen and proved by Lovett and Yildiz-Hassibi, shows that the generator matrices of Reed-Solomon codes can attain every possible con…
Differentially Private Synthetic Data via Foundation Model APIs 1: Images
Zinan Lin, Sivakanth Gopi, Janardhan Kulkarni +2
Generating differentially private (DP) synthetic data that closely resembles the original private data is a scalable way to mitigate privacy concerns in the current data-driven wor…