Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author chen yuan:

TR19-108 | 23rd August 2019
Chaoping Xing, chen yuan

Beating the probabilistic lower bound on perfect hashing

Revisions: 2

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 >>>

TR17-064 | 20th April 2017
Venkatesan Guruswami, Chaoping Xing, chen yuan

Subspace Designs based on Algebraic Function Fields

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 >>>

TR16-051 | 7th April 2016
Ronald Cramer, Chaoping Xing, chen yuan

On Multi-Point Local Decoding of Reed-Muller Codes

Revisions: 4

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 >>>

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

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 >>>

ISSN 1433-8092 | Imprint