This content will become publicly available on June 1, 2025
Title: On the generalized Hamming weights of hyperbolic codes
[Formula: see text]A hyperbolic code is an evaluation code that improves a Reed–Muller code because the dimension increases while the minimum distance is not penalized. We give necessary and sufficient conditions, based on the basic parameters of the Reed–Muller code, to determine whether a Reed–Muller code coincides with a hyperbolic code. Given a hyperbolic code [Formula: see text], we find the largest Reed–Muller code contained in [Formula: see text] and the smallest Reed–Muller code containing [Formula: see text]. We then prove that similar to Reed–Muller and affine Cartesian codes, the [Formula: see text]th generalized Hamming weight and the [Formula: see text]th footprint of the hyperbolic code coincide. Unlike for Reed–Muller and affine Cartesian codes, determining the [Formula: see text]th footprint of a hyperbolic code is still an open problem. We give upper and lower bounds for the [Formula: see text]th footprint of a hyperbolic code that, sometimes, are sharp.
Ben-Sasson, Eli; Carmon, Dan; Ishai, Yuval; Kopparty, Swastik; Saraf, Shubhangi(
, Journal of the ACM)
A collection of sets displays aproximity gapwith respect to some property if for every set in the collection, either (i) all members areδ-close to the property in relative Hamming distance or (ii) only a tiny fraction of members areδ-close to the property. In particular, no set in the collection has roughly half of its membersδ-close to the property and the othersδ-far from it.
We show that the collection of affine spaces displays a proximity gap with respect to Reed–Solomon (RS) codes, even over small fields, of size polynomial in the dimension of the code, and the gap applies to anyδsmaller than the Johnson/Guruswami–Sudan list-decoding bound of the RS code. We also show near-optimal gap results, over fields of (at least)linearsize in the RS code dimension, forδsmaller than the unique decoding radius. Concretely, ifδis smaller than half the minimal distance of an RS code\(V\subset {\mathbb {F}}_q^n \), every affine space is either entirelyδ-close to the code, or alternatively at most an (n/q)-fraction of it isδ-close to the code. Finally, we discuss several applications of our proximity gap results to distributed storage, multi-party cryptographic protocols, and concretely efficient proof systems.
We prove the proximity gap results by analyzing the execution of classical algebraic decoding algorithms for Reed–Solomon codes (due to Berlekamp–Welch and Guruswami–Sudan) on aformal elementof an affine space. This involves working with Reed–Solomon codes whose base field is an (infinite) rational function field. Our proofs are obtained by developing an extension (to function fields) of a strategy of Arora and Sudan for analyzing low-degree tests.
Ratcliffe, John G.; Ruberman, Daniel; Tschantz, Steven T.(
, Journal of Topology and Analysis)
In this paper, we use the [Formula: see text]-spin theorem to show that the Davis hyperbolic 4-manifold admits harmonic spinors. This is the first example of a closed hyperbolic [Formula: see text]-manifold that admits harmonic spinors. We also explicitly describe the spinor bundle of a spin hyperbolic 2- or 4-manifold and show how to calculated the subtle sign terms in the [Formula: see text]-spin theorem for an isometry, with isolated fixed points, of a closed spin hyperbolic 2- or 4-manifold.
CSS-T codes were recently introduced as quantum error-correcting codes that respect a transversal gate. A CSS-T code depends on a CSS-T pair, which is a pair of binary codes$$(C_1, C_2)$$such that$$C_1$$contains$$C_2$$,$$C_2$$is even, and the shortening of the dual of$$C_1$$with respect to the support of each codeword of$$C_2$$is self-dual. In this paper, we give new conditions to guarantee that a pair of binary codes$$(C_1, C_2)$$is a CSS-T pair. We define the poset of CSS-T pairs and determine the minimal and maximal elements of the poset. We provide a propagation rule for nondegenerate CSS-T codes. We apply some main results to Reed–Muller, cyclic and extended cyclic codes. We characterize CSS-T pairs of cyclic codes in terms of the defining cyclotomic cosets. We find cyclic and extended cyclic codes to obtain quantum codes with better parameters than those in the literature.
A collection of sets displays a proximity gap with respect to some property if for every set in the collection, either (i) all members are δ-close to the property in relative Hamming distance or (ii) only a tiny fraction of members are δ-close to the property. In particular, no set in the collection has roughly half of its members δ-close to the property and the others δ-far from it. We show that the collection of affine spaces displays a proximity gap with respect to Reed-Solomon (RS) codes, even over small fields, of size polynomial in the dimension of the code, and the gap applies to any δ smaller than the Johnson/Guruswami-Sudan list-decoding bound of the RS code. We also show near-optimal gap results, over fields of (at least) linear size in the RS code dimension, for δ smaller than the unique decoding radius. Concretely, if δ is smaller than half the minimal distance of an RS code V ⊂ Fq n , every affine space is either entirely δ-close to the code, or alternatively at most an ( n/q)-fraction of it is δ-close to the code. Finally, we discuss several applications of our proximity gap results to distributed storage, multi-party cryptographic protocols, and concretely efficient proof systems. We prove the proximity gap results by analyzing the execution of classical algebraic decoding algorithms for Reed-Solomon codes (due to Berlekamp-Welch and Guruswami-Sudan) on a formal element of an affine space. This involves working with Reed-Solomon codes whose base field is an (infinite) rational function field. Our proofs are obtained by developing an extension (to function fields) of a strategy of Arora and Sudan for analyzing low-degree tests.
Bridgeman, Martin; Bromberg, Kenneth(
, Journal of Topology and Analysis)
World Scientific
(Ed.)
In general, it is difficult to measure distances in the Weil–Petersson metric on Teichmüller space. Here we consider the distance between strata in the Weil–Petersson completion of Teichmüller space of a surface of finite type. Wolpert showed that for strata whose closures do not intersect, there is a definite separation independent of the topology of the surface. We prove that the optimal value for this minimal separation is a constant [Formula: see text] and show that it is realized exactly by strata whose nodes intersect once. We also give a nearly sharp estimate for [Formula: see text] and give a lower bound on the size of the gap between [Formula: see text] and the other distances. A major component of the paper is an effective version of Wolpert’s upper bound on [Formula: see text], the inner product of the Weil–Petersson gradient of length functions. We further bound the distance to the boundary of Teichmüller space of a hyperbolic surface in terms of the length of the systole of the surface. We also obtain new lower bounds on the systole for the Weil–Petersson metric on the moduli space of a punctured torus.
Camps-Moreno, Eduardo, García-Marco, Ignacio, López, Hiram H, Márquez-Corbella, Irene, Martínez-Moro, Edgar, and Sarmiento, Eliseo. On the generalized Hamming weights of hyperbolic codes. Retrieved from https://par.nsf.gov/biblio/10523653. Journal of Algebra and Its Applications 23.07 Web. doi:10.1142/S0219498825500628.
Camps-Moreno, Eduardo, García-Marco, Ignacio, López, Hiram H, Márquez-Corbella, Irene, Martínez-Moro, Edgar, & Sarmiento, Eliseo. On the generalized Hamming weights of hyperbolic codes. Journal of Algebra and Its Applications, 23 (07). Retrieved from https://par.nsf.gov/biblio/10523653. https://doi.org/10.1142/S0219498825500628
Camps-Moreno, Eduardo, García-Marco, Ignacio, López, Hiram H, Márquez-Corbella, Irene, Martínez-Moro, Edgar, and Sarmiento, Eliseo.
"On the generalized Hamming weights of hyperbolic codes". Journal of Algebra and Its Applications 23 (07). Country unknown/Code not available: World Scientific. https://doi.org/10.1142/S0219498825500628.https://par.nsf.gov/biblio/10523653.
@article{osti_10523653,
place = {Country unknown/Code not available},
title = {On the generalized Hamming weights of hyperbolic codes},
url = {https://par.nsf.gov/biblio/10523653},
DOI = {10.1142/S0219498825500628},
abstractNote = {[Formula: see text]A hyperbolic code is an evaluation code that improves a Reed–Muller code because the dimension increases while the minimum distance is not penalized. We give necessary and sufficient conditions, based on the basic parameters of the Reed–Muller code, to determine whether a Reed–Muller code coincides with a hyperbolic code. Given a hyperbolic code [Formula: see text], we find the largest Reed–Muller code contained in [Formula: see text] and the smallest Reed–Muller code containing [Formula: see text]. We then prove that similar to Reed–Muller and affine Cartesian codes, the [Formula: see text]th generalized Hamming weight and the [Formula: see text]th footprint of the hyperbolic code coincide. Unlike for Reed–Muller and affine Cartesian codes, determining the [Formula: see text]th footprint of a hyperbolic code is still an open problem. We give upper and lower bounds for the [Formula: see text]th footprint of a hyperbolic code that, sometimes, are sharp.},
journal = {Journal of Algebra and Its Applications},
volume = {23},
number = {07},
publisher = {World Scientific},
author = {Camps-Moreno, Eduardo and García-Marco, Ignacio and López, Hiram H and Márquez-Corbella, Irene and Martínez-Moro, Edgar and Sarmiento, Eliseo},
}
Warning: Leaving National Science Foundation Website
You are now leaving the National Science Foundation website to go to a non-government website.
Website:
NSF takes no responsibility for and exercises no control over the views expressed or the accuracy of
the information contained on this site. Also be aware that NSF's privacy policy does not apply to this site.