Author name cluster

Manik Dhar

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

2 author rows

STOC Conference 2024 Conference Paper

AG Codes Achieve List Decoding Capacity over Constant-Sized Fields

Joshua Brakensiek
Manik Dhar
Sivakanth Gopi
Zihan Zhang 0001

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 recoverable (MR) tensor codes, codes with optimal list-decoding guarantees, and codes with constrained generator matrices (as in the GM-MDS theorem). By proving these equivalences, Brakensiek-Gopi-Makam showed the existence of optimally list-decodable Reed-Solomon codes over exponential sized fields. Building on this, recent breakthroughs by Guo-Zhang and Alrabiah-Guruswami-Li have shown that randomly punctured Reed-Solomon codes achieve list-decoding capacity (which is a relaxation of optimal list-decodability) over linear size fields. We extend these works by developing a formal theory of relaxed higher order MDS codes. In particular, we show that there are two inequivalent relaxations which we call lower and upper relaxations. The lower relaxation is equivalent to relaxed optimal list-decodable codes and the upper relaxation is equivalent to relaxed MR tensor codes with a single parity check per column. We then generalize the techniques of Guo-Zhang and Alrabiah-Guruswami-Li to show that both these relaxations can be constructed over constant size fields by randomly puncturing suitable algebraic-geometric codes. For this, we crucially use the generalized GM-MDS theorem for polynomial codes recently proved by Brakensiek-Dhar-Gopi. We obtain the following corollaries from our main result: Randomly punctured algebraic-geometric codes of rate R are list-decodable up to radius L / L +1(1− R −є) with list size L over fields of size exp( O ( L /є)). In particular, they achieve list-decoding capacity with list size O (1/є) and field size exp( O (1/є 2 )). Prior to this work, AG codes were not even known to achieve list-decoding capacity. By randomly puncturing algebraic-geometric codes, we can construct relaxed MR tensor codes with a single parity check per column over constant-sized fields, whereas (non-relaxed) MR tensor codes require exponential field size.

Details

STOC Conference 2024 Conference Paper

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 configuration of zeros for an MDS code. The recently emerging theory of higher order MDS codes has connected the GM-MDS theorem to other important properties of Reed-Solomon codes, including showing that Reed-Solomon codes can achieve list decoding capacity, even over fields of size linear in the message length. A few works have extended the GM-MDS theorem to other families of codes, including Gabidulin and skew polynomial codes. In this paper, we generalize all these previous results by showing that the GM-MDS theorem applies to any polynomial code, i.e., a code where the columns of the generator matrix are obtained by evaluating linearly independent polynomials at different points. We also show that the GM-MDS theorem applies to dual codes of such polynomial codes, which is non-trivial since the dual of a polynomial code may not be a polynomial code. More generally, we show that GM-MDS theorem also holds for algebraic codes (and their duals) where columns of the generator matrix are chosen to be points on some irreducible variety which is not contained in a hyperplane through the origin. Our generalization has applications to constructing capacity-achieving list-decodable codes as shown in a follow-up work [Brakensiek, Dhar, Gopi, Zhang; 2024], where it is proved that randomly punctured algebraic-geometric (AG) codes achieve list-decoding capacity over constant-sized fields.

Details

FOCS Conference 2022 Conference Paper

Linear Hashing with ℓ∞ guarantees and two-sided Kakeya bounds

Manik Dhar
Zeev Dvir

We show that a randomly chosen linear map over a finite field gives a good hash function in the $\ell_{\infty}$ sense. More concretely, consider a set $S\subset\mathbb{F}_{q}^{n}$ and a randomly chosen linear ${map}L: \mathbb{F}_{q}^{n}\rightarrow\mathbb{F}_{q}^{t}$ with q t taken to be sufficiently smaller than $|S|$. Let U S denote a random variable distributed uniformly on S. Our main theorem shows that, with high probability over the choice of L, the random variable $L(U_{S})$ is close to uniform in the $\ell_{\infty}$ norm. In other words, every element in the range $\mathbb{F}_{q}^{t}$ has about the same number of elements in S mapped to it. This complements the widely-used Leftover Hash Lemma (LHL) which proves the analog statement under the statistical, or $\ell_{1}$, distance (for a richer class of functions) as well as prior work on the expected largest ’bucket size’ in linear hash functions [1]. By known bounds from the load balancing literature [2], our results are tight and show that linear functions hash as well as truly random function up to a constant factor in the entropy loss. Our proof leverages a connection between linear hashing and the finite field Kakeya problem and extends some of the tools developed in this area, in particular the polynomial method.

Details

AAAI Conference 2018 Conference Paper

Flow-GAN: Combining Maximum Likelihood and Adversarial Learning in Generative Models

Aditya Grover
Manik Dhar
Stefano Ermon

Adversarial learning of probabilistic models has recently emerged as a promising alternative to maximum likelihood. Implicit models such as generative adversarial networks (GAN) often generate better samples compared to explicit models trained by maximum likelihood. Yet, GANs sidestep the characterization of an explicit density which makes quantitative evaluations challenging. To bridge this gap, we propose Flow-GANs, a generative adversarial network for which we can perform exact likelihood evaluation, thus supporting both adversarial and maximum likelihood training. When trained adversarially, Flow-GANs generate high-quality samples but attain extremely poor log-likelihood scores, inferior even to a mixture model memorizing the training data; the opposite is true when trained by maximum likelihood. Results on MNIST and CIFAR-10 demonstrate that hybrid training can attain high held-out likelihoods while retaining visual ﬁdelity in the generated samples.

PDF Details

ICML Conference 2018 Conference Paper

Modeling Sparse Deviations for Compressed Sensing using Generative Models

Manik Dhar
Aditya Grover
Stefano Ermon

In compressed sensing, a small number of linear measurements can be used to reconstruct an unknown signal. Existing approaches leverage assumptions on the structure of these signals, such as sparsity or the availability of a generative model. A domain-specific generative model can provide a stronger prior and thus allow for recovery with far fewer measurements. However, unlike sparsity-based approaches, existing methods based on generative models guarantee exact recovery only over their support, which is typically only a small subset of the space on which the signals are defined. We propose Sparse-Gen, a framework that allows for sparse deviations from the support set, thereby achieving the best of both worlds by using a domain specific prior and allowing reconstruction over the full space of signals. Theoretically, our framework provides a new class of signals that can be acquired using compressed sensing, reducing classic sparse vector recovery to a special case and avoiding the restrictive support due to a generative model prior. Empirically, we observe consistent improvements in reconstruction accuracy over competing approaches, especially in the more practical setting of transfer compressed sensing where a generative model for a data-rich, source domain aids sensing on a data-scarce, target domain.

Details