All reports by Author Chaoping Xing:

__
TR19-108
| 23rd August 2019
__

Chaoping Xing, chen yuan#### Beating the probabilistic lower bound on perfect hashing

__
TR18-017
| 26th January 2018
__

Venkatesan Guruswami, Nicolas Resch, Chaoping Xing#### Lossless dimension expanders via linearized polynomials and subspace designs

__
TR17-064
| 20th April 2017
__

Venkatesan Guruswami, Chaoping Xing, chen yuan#### Subspace Designs based on Algebraic Function Fields

__
TR16-051
| 7th April 2016
__

Ronald Cramer, Chaoping Xing, chen yuan#### On Multi-Point Local Decoding of Reed-Muller Codes

Revisions: 4

__
TR15-161
| 24th September 2015
__

Chaoping Xing, chen yuan#### A new class of rank-metric codes and their list decoding beyond the unique decoding radius

__
TR13-175
| 6th December 2013
__

Venkatesan Guruswami, Chaoping Xing#### Hitting Sets for Low-Degree Polynomials with Optimal Density

Revisions: 1

__
TR13-046
| 27th March 2013
__

Venkatesan Guruswami, Chaoping Xing#### Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets

__
TR12-146
| 7th November 2012
__

Venkatesan Guruswami, Chaoping Xing#### List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound

__
TR12-036
| 12th April 2012
__

Venkatesan Guruswami, Chaoping Xing#### Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding

Chaoping Xing, chen yuan

For an interger $q\ge 2$, a perfect $q$-hash code $C$ is a block code over $\ZZ_q:=\ZZ/ q\ZZ$ of length $n$ in which every subset $\{\bc_1,\bc_2,\dots,\bc_q\}$ of $q$ elements is separated, i.e., there exists $i\in[n]$ such that $\{\proj_i(\bc_1),\proj_i(\bc_2),\dots,\proj_i(\bc_q)\}=\ZZ_q$, where $\proj_i(\bc_j)$ denotes the $i$th position of $\bc_j$. Finding the maximum size $M(n,q)$ ... more >>>

Venkatesan Guruswami, Nicolas Resch, Chaoping Xing

For a vector space $\mathbb{F}^n$ over a field $\mathbb{F}$, an $(\eta,\beta)$-dimension expander of degree $d$ is a collection of $d$ linear maps $\Gamma_j : \mathbb{F}^n \to \mathbb{F}^n$ such that for every subspace $U$ of $\mathbb{F}^n$ of dimension at most $\eta n$, the image of $U$ under all the maps, $\sum_{j=1}^d ... more >>>

Venkatesan Guruswami, Chaoping Xing, chen yuan

Subspace designs are a (large) collection of high-dimensional subspaces $\{H_i\}$ of $\F_q^m$ such that for any low-dimensional subspace $W$, only a small number of subspaces from the collection have non-trivial intersection with $W$; more precisely, the sum of dimensions of $W \cap H_i$ is at most some parameter $L$. The ... more >>>

Ronald Cramer, Chaoping Xing, chen yuan

Reed-Muller codes are among the most important classes of locally correctable codes. Currently local decoding of Reed-Muller codes is based on decoding on lines or quadratic curves to recover one single coordinate. To recover multiple coordinates simultaneously, the naive way is to repeat the local decoding for recovery of a ... more >>>

Chaoping Xing, chen yuan

Compared with classical block codes, efficient list decoding of rank-metric codes seems more difficult. The evidences to support this view include: (i) so far people have not found polynomial time list decoding algorithms of rank-metric codes with decoding radius beyond $(1-R)/2$ (where $R$ is the rate of code) if ratio ... more >>>

Venkatesan Guruswami, Chaoping Xing

We give a length-efficient puncturing of Reed-Muller codes which preserves its distance properties. Formally, for the Reed-Muller code encoding $n$-variate degree-$d$ polynomials over ${\mathbb F}_q$ with $q \ge \Omega(d/\delta)$, we present an explicit (multi)-set $S \subseteq {\mathbb F}_q^n$ of size $N=\mathrm{poly}(n^d/\delta)$ such that every nonzero polynomial vanishes on at most ... more >>>

Venkatesan Guruswami, Chaoping Xing

We construct a new list-decodable family of asymptotically good algebraic-geometric (AG) codes over fixed alphabets. The function fields underlying these codes are constructed using class field theory, specifically Drinfeld modules of rank $1$, and designed to have an automorphism of large order that is used to ``fold" the AG code. ... more >>>

Venkatesan Guruswami, Chaoping Xing

We consider Reed-Solomon (RS) codes whose evaluation points belong to a subfield, and give a linear-algebraic list decoding algorithm that can correct a fraction of errors approaching the code distance, while pinning down the candidate messages to a well-structured affine space of dimension a constant factor smaller than the code ... more >>>

Venkatesan Guruswami, Chaoping Xing

We give a new construction of algebraic codes which are efficiently list decodable from a fraction $1-R-\epsilon$ of adversarial errors where $R$ is the rate of the code, for any desired positive constant $\epsilon$. The worst-case list size output by the algorithm is $O(1/\epsilon)$, matching the existential bound for random ... more >>>