7 papers
Universally optimal (wiretap) codes
Madhura Pathegama, Alexander Barg
Universally optimal (UO) codes were introduced by H. Cohn and A. Kumar in 2007 and later extended to the discrete setting by Cohn and Y. Zhao. They minimize the ``energy'' among al…
Minimum distance and decoding of Coxeter codes
Alexander Barg, Qëndrim R. Gashi, Tianyuan Xu
A binary Coxeter code associated with a finite Coxeter system is an -linear span of indicators of standard cosets of a fixed rank. Coxeter codes, introduced…
Coxeter codes: Extending the Reed-Muller family
Nolan J. Coble, Alexander Barg
Binary Reed-Muller (RM) codes are defined via evaluations of Boolean-valued functions on . We introduce a class of binary linear codes that generalizes the RM famil…
Rényi divergence-based uniformity guarantees for -universal hash functions
Madhura Pathegama, Alexander Barg
Universal hash functions map the output of a source to random strings over a finite alphabet, aiming to approximate the uniform distribution on the set of strings. A classic result…
Rényi divergence guarantees for hashing with linear codes
Madhura Pathegama, Alexander Barg
We consider the problem of distilling uniform random bits from an unknown source with a given -entropy using linear hashing. As our main result, we estimate the expected -div…
Limitations of the decoding-to-LPN reduction via code smoothing
Madhura Pathegama, Alexander Barg
The Learning Parity with Noise (LPN) problem underlines several classic cryptographic primitives. Researchers have attempted to demonstrate the algorithmic hardness of this problem…