BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
In this paper, we propose a probabilistic algorithm suitable for any linear code C to determine whether a given vector x belongs to C. The algorithm achieves O(nlogn) time complexity, O(n2) space complexity and with an error probability less than 1/poly(n) in the asymptotic sense.
In a recent paper, Andrews and Merca investigated the number of even parts in all partitions of n into distinct parts, which arise naturally from the Euler-Glaisher bijective proof. They obtained new combinatorial interpretations for this number by using generating functions. We obtain a new direct combinatorial proof in this note.
We use the generating function approach to derive simple expressions for the factorial moments of the distance distribution over Reed-Solomon codes. We obtain better upper bounds for the error term of a counting formula given by Li and Wan, which gives nontrivial estimates on the number of polynomials over finite fields with prescribed leading coefficients and a given number of linear factors. This improvement leads to new results on the classification of deep holes of Reed Solomon codes.
A conjecture of Le says that the Deligne polytope Δd is generically ordinary if p≡1 (mod D(Δd)), where D(Δd) is a combinatorial constant determined by Δd. In this paper a counterexample is given to show that the conjecture is not true in general.
Let Fq be the finite field of q elements and a1,a2,…,ak,b∈Fq. We investigate NFq(a1,a2,…,ak;b), the number of ordered solutions (x1,x2,…,xk)∈Fqk of the linear equation a1x1+a2x2+⋯+akxk=b with all xi distinct. We obtain an explicit formula for NFq(a1,a2,…,ak;b) involving combinatorial numbers depending on ai's. In particular, we obtain closed formulas for two special cases. One is that ai,1≤i≤k take at most three distinct values and the other is that ∑i=1kai=0 and ∑i∈Iai=0 for any I⊊[k]. The same technique works when Fq is replaced by Zn, the ring of integers modulo n. In particular, we give a new proof for the main result given by Bibak, Kapron and Srinivasan, which generalizes a theorem of Schönemann via a graph theoretic method.
A conjecture of Borwein asserts that for any positive integers n and k, the coefficient a3k of q3k in the expansion of ∏j=0n(1−q3j+1)(1−q3j+2) is nonnegative. In this paper we prove that for any 0≤k≤n, there is a constant 0<c<1 such that a3k+a3(n+1)+3k+⋯+a3n(n+1)+3k=n+12⋅3n(1+O(cn)). In particular, a3k+a3(n+1)+3k+⋯+a3n(n+1)+3k>0.
Sensitivity is an important complexity measure of Boolean functions. In this paper we present properties of the minimal and maximal sensitivity of the simplified weighted sum function. A simple close formula of the minimal sensitivity of the simplified weighted sum function is obtained. A phenomenon is exhibited that the minimal sensitivity of the weighted sum function is indeed an indicator of large primes, that is, for large prime number p, the minimal sensitivity of the weighted sum function is always equal to one.
Let D be a subset of a finite commutative ring R with identity. Let f(x)∈R[x] be a polynomial of positive degree d. For integer 0≤k≤∣D∣, we study the number Nf(D,k,b) of k-subsets S⊆D such that \begin{align*} \sum_{x\in S} f(x)=b. \end{align*} In this paper, we establish several asymptotic formulas for Nf(D,k,b), depending on the nature of the ring R and f. For R=Zn, let p=p(n) be the smallest prime divisor of n, ∣D∣=n−c≥Cdnp−d1+c and f(x)=adxd+⋯+a0∈Z[x] with (ad,…,a1,n)=1. Then Nf(D,k,b)−n1(kn−c)≤(kδ(n)(n−c)+(1−δ(n))(Cdnp−d1+c)+k−1), partially answering an open question raised by Stanley \cite{St}, where δ(n)=∑i∣n,μ(i)=−1i1 and Cd=e1.85d. Furthermore, if n is a prime power, then δ(n)=1/p and one can take Cd=4.41. For R=Fq of characteristic p, let f(x)∈Fq[x] be a polynomial of degree d not divisible by p and D⊆Fq with ∣D∣=q−c≥(d−1)q+c. Then Nf(D,k,b)−q1(kq−c)≤(kpq−c+pp−1((d−1)q21+c)+k−1). If f(x)=ax+b, then this problem is precisely the well-known subset sum problem over a finite abelian group. Let G be a finite abelian group and let D⊆G with ∣D∣=∣G∣−c≥c. Then Nx(D,k,b)−∣G∣1(k∣G∣−c)≤(kc+(∣G∣−2c)δ(e(G))+k−1), where e(G) is the exponent of G and δ(n)=∑i∣n,μ(i)=−1i1. In particular, we give a new short proof for the explicit counting formula for the case D=G.
Computing the minimum distance of a linear code is one of the fundamental problems in algorithmic coding theory. Vardy [14] showed that it is an \np-hard problem for general linear codes. In practice, one often uses codes with additional mathematical structure, such as AG codes. For AG codes of genus 0 (generalized Reed-Solomon codes), the minimum distance has a simple explicit formula. An interesting result of Cheng [3] says that the minimum distance problem is already \np-hard (under \rp-reduction) for general elliptic curve codes (ECAG codes, or AG codes of genus 1). In this paper, we show that the minimum distance of ECAG codes also has a simple explicit formula if the evaluation set is suitably large (at least 2/3 of the group order). Our method is purely combinatorial and based on a new sieving technique from the first two authors [8]. This method also proves a significantly stronger version of the MDS (maximum distance separable) conjecture for ECAG codes.
The polynomial coefficient (kn,q) is defined to be the coefficient of xk in the expansion of (1+x+x2+...+xq−1)n. In this note we give an asymptotic estimate for (cnn,q) as n tends to infinity, where c is a positive integer. Based on experimental results, it was conjectured that for any n, (cnn,q)−(cnn,q−1) is unimodal and its maximum value occurs q=⌊log1+c1n⌋ or q=⌊log1+c1n⌋+1. In particular, when c=1, its maximum value occurs for q=⌊log2n⌋ or q=⌊log2n⌋+1.
In this paper we simplify the definition of the weighted sum Boolean function which used to be inconvenient to compute and use. We show that the new function has essentially the same properties as the previous one. In particular, the bound on the average sensitivity of the weighted sum Boolean function remains unchanged after the simplification.
For a linear code, deep holes are defined to be vectors that are further away from codewords than all other vectors. The problem of deciding whether a received word is a deep hole for generalized Reed-Solomon codes is proved to be co-NP-complete. For the extended Reed-Solomon codes $RS_q(\F_q,k)$, a conjecture was made to classify deep holes by Cheng and Murray in 2007. Since then a lot of effort has been made to prove the conjecture, or its various forms. In this paper, we classify deep holes completely for generalized Reed-Solomon codes RSp(D,k), where p is a prime, ∣D∣>k⩾2p−1. Our techniques are built on the idea of deep hole trees, and several results concerning the Erd{ö}s-Heilbronn conjecture.
We obtain an asymptotic formula on the Odlyzko-Stanley enumeration problem. Let Nm∗(k,b) be the number of k-subsets S⊆Fp∗ such that ∑x∈Sxm=b. If m<p1−δ, then there is a constant ε=ε(δ)>0 such that | N_m^*(k,b)-p^{-1}{p-1 \choose k}|\leq {p^{1-ε}+mk-m \choose k}. In addition, let γ′(m,p) denote the distinct Waring's number (modp), the smallest positive integer k such that every integer is a sum of m-th powers of k-distinct elements (modp). The above bound implies that there is a constant ε(δ)>0 such for any prime p and any m<p1−δ, if ε−1<(e−1)pδ−ε, then γ′(m,p)≤ε−1.
In this paper we obtain the average sensitivity of the laced Boolean functions. This confirms a conjecture of Shparlinski. We also compute the weights of the laced Boolean functions and show that they are almost balanced.
In \cite{D1}, Dickson listed all permutation polynomials up to degree 5 over an arbitrary finite field, and all permutation polynomials of degree 6 over finite fields of odd characteristic. The classification of degree 6 permutation polynomials over finite fields of characteristic 2 was left incomplete. In this paper we complete the classification of permutation polynomials of degree 6 over finite fields of characteristic 2. In addition, all permutation polynomials of degree 7 over finite fields of characteristic 2 are classified.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.