The PCP theorem [Arora et al. 1998; Arora and Safra 1998] says that every NP-proof can be encoded to another proof, namely, a probabilistically checkable proof (PCP), which can be tested by a verifier that queries only a small part of the PCP. A natural question is how large is the blow-up incurred by this encoding, that is, how long is the PCP compared to the original NP-proof? The state-of-the-art work of Ben-Sasson and Sudan [2008] and Dinur [2007] shows that one can encode proofs of length n by PCPs of length n · poly log n that can be verified using a constant number of queries. In this work, we show that if the query complexity is relaxed to n ε , then one can construct PCPs of length O ( n ) for circuit-SAT, and PCPs of length O ( t log t ) for any language in NTIME( t ). More specifically, for any ε > 0, we present (nonuniform) probabilistically checkable proofs (PCPs) of length 2 O (1/ε) · n that can be checked using n ε queries for circuit-SAT instances of size n . Our PCPs have perfect completeness and constant soundness. This is the first constant-rate PCP construction that achieves constant soundness with nontrivial query complexity ( o ( n )). Our proof replaces the low-degree polynomials in algebraic PCP constructions with tensors of transitive algebraic geometry (AG) codes. We show that the automorphisms of an AG code can be used to simulate the role of affine transformations that are crucial in earlier high-rate algebraic PCP constructions. Using this observation, we conclude that any asymptotically good family of transitive AG codes over a constant-sized alphabet leads to a family of constant-rate PCPs with polynomially small query complexity. Such codes are constructed in the appendix to this article for the first time for every message length, building on an earlier construction for infinitely many message lengths by Stichtenoth [2006].

The Gilbert-Varshamov bound guarantees the existence of families of codes over the finite field Fℓwith good asymptotic parameters. We show that this bound can be improved for all nonprime fields Fℓwith ℓ ≥ 49 , except possibly ℓ = 125. We observe that the same improvement even holds within the class of transitive codes and within the class of self-orthogonal codes.

The PCP theorem (Arora et. al., J. ACM 45(1, 3)) says that every NP-proof can be encoded to another proof, namely, a probabilistically checkable proof (PCP), which can be tested by a verifier that queries only a small part of the PCP. A natural question is how large is the blow-up incurred by this encoding, i.e., how long is the PCP compared to the original NP-proof. The state-of-the-art work of Ben-Sasson and Sudan (SICOMP 38(2)) and Dinur (J. ACM 54(3)) shows that one can encode proofs of length n by PCPs of quasi-linear length that can be verified using a constant number of queries. In this work, we show that if the query complexity is relaxed to polynomial, then one can construct PCPs of linear length for circuit-SAT, and PCPs of length O(tlog t) for any language in NTIME(t). Our PCPs have perfect completeness and constant soundness. This is the first constant-rate PCP construction that achieves constant soundness with nontrivial query complexity. Our proof replaces the low-degree polynomials in algebraic PCP constructions with tensors of transitive algebraic geometry (AG) codes. We show that the automorphisms of an AG code can be used to simulate the role of affine transformations which are crucial in earlier high-rate algebraic PCP constructions. Using this observation we conclude that any asymptotically good family of transitive AG codes over a constant-sized alphabet leads to a family of constant-rate PCPs with polynomially small query complexity. Such codes are constructed for the first time for every message length.

A major problem in coding theory is the question of whether the class of cyclic codes is asymptotically good. In this correspondence-as a generalization of cyclic codes-the notion of transitive codes is introduced (see Definition 1.4 in Section I), and it is shown that the class of transitive codes is asymptotically good. Even more, transitive codes attain the Tsfasman-Vlabrevedut$80-Zink bound over Fq, for all squares q=l2. It is also shown that self-orthogonal and self-dual codes attain the Tsfasman-Vlabrevedut$80-Zink bound, thus improving previous results about self-dual codes attaining the Gilbert-Varshamov bound. The main tool is a new asymptotically optimal tower E0subeE1subeE2sube middotmiddotmiddot of function fields over Fq(with q=lscr2), where all extensions En/E0are Galois

The Gilbert-Varshamov (GV) bound for asymptotic families of codes over F/sub q/ has been improved by Tsfasman, Vla/spl breve/dut$80, and Zink (TVZ) in 1982, and only recently further improvements have been obtained by Xing, Elkies, and Niederreiter-O/spl uml/zbudak, by considering also nonlinear codes. These improvements involve higher derivations in function fields and are very computational. We give in this correspondence a much simpler proof for those improvements. Our construction of asymptotically good nonlinear codes is very similar to Goppa's construction of algebraic-geometry codes.

We show that the concept of "generalized algebraic geometry codes" which was introduced by Xing, Niederreiter, and Lam (see ibid., vol.45, p.2498-2501, Nov. 1999) gives a natural framework for constructing linear unequal error protection codes.

A description of how places split in an asymptotically optimal tower of function fields studied by Garcia and Stichtenoth (1995) is provided and an exact count of the number of places of degree one is given. This information is useful in the setting up of generator matrices for algebraic-geometry codes constructed over this function field tower. These long codes have performance that asymptotically improves upon the Gilbert-Varshamov bound.

Since the proof in 1982, by Tsfasman Vladut and Zink of the existence of algebraic-geometric (AG) codes with asymptotic performance exceeding the Gilbert-Varshamov (G-V) bound, one of the challenges in coding theory has been to provide explicit constructions for these codes. In a major step forward during 1995-1996, Garcia and Stichtenoth (GS) provided an explicit description of algebraic curves, such that AG codes constructed on them would have a performance better than the G-V bound. We present the first low-complexity algorithm for obtaining the generator matrix for AG codes on the curves of GS. The symbol alphabet of the AG code is the finite field of q/sup 2/, q/sup 2//spl ges/49, elements. The complexity of the algorithm, as measured in terms of multiplications and divisions over the finite field GF(q/sup 2/), is upper-bounded by [Nlog/sub q/(N)]/sup 3/ where N is the length of the code. An example of code construction using the above algorithm is presented. By concatenating the AG code with short binary block codes, it is possible to obtain binary codes with asymptotic performance close to the G-V bound. Some examples of such concatenation are included.

We discuss some previous constructions of codes from algebraic curves due to Xing, Niederreiter and Lam (see ibid., vol.45, no.7, p.2498-2501, 1999), and we investigate their relations with Goppa's (1981) algebraic-geometric codes.

Algebraic function fields (or equivalently, algebraic curves) provide a useful tool for coding theory (for instance, algebraic-geometric codes and trace codes), but also for other branches of information theory. In these applications, the number of rational places of a function field plays a crucial role. One is particularly interested in function fields having a large number of rational places. After a short introduction into the mathematical theory of algebraic functions, the paper gives a survey of old and new results on the number of rational places of function fields.

Linear codes over F/sub p/ often admit a natural representation as trace codes of codes that are defined over an extension field F/sub p/m. In the paper, the authors obtain estimates for the weights of subcodes of such trace codes. Their main result is a far-reaching generalization of the Carlitz-Uchiyama bound for the duals of binary BCH codes. In particular, they prove sharp bounds for the generalized Hamming weights of a large class of codes, including duals of BCH codes, classical Goppa codes, Melas codes, and arbitrary cyclic codes of length n=p/sup m/-1. The main tool is the theory of algebraic functions over finite fields, in particular the Hasse-Weil bound for the number of places of degree one.>

The weight hierarchy of a linear code is the set of generalized Hamming weights of the code. In the paper, the authors consider geometric Goppa codes and provide a lower bound on their generalized Hamming weights similar to Goppa's lower bound on their minimum distance. In the particular case of Hermitian codes, exact results on the second and third generalized Hamming weights are given for any m except a few cases, where m is a parameter that governs the dimension of these codes. In many instances, the authors are able to provide considerably more information on their generalized Hamming weights. An upper bound relating the generalized Hamming weights of Hermitian codes to the pole numbers at a special point on the curve is also provided. Similar results are given in the case of codes from some subfields of the Hermitian function fields, which are also maximal. Finally, a nontrivial family of codes is also presented whose weight hierarchy is completely determined.>

A new lower bound for the dimension of a subfield subcode is given. This bound improves the well-known lower bound of P. Delsarte (1975) and coincides in many cases with the true dimension of the code. Alternant codes and geometric Goppa codes are discussed as special cases.>

Properties of codes defined by Goppa's algebraic-geometric method using Hermitian curves are discussed. Generator and parity check matrices for such codes are derived explicitly. Results concerning the minimum distance and the weight distribution of the codes are provided.>