The Experts below are selected from a list of 58959 Experts worldwide ranked by ideXlab platform
Chaoping Xing - One of the best experts on this subject based on the ideXlab platform.
-
subspace designs based on Algebraic Function fields
arXiv: Computational Complexity, 2017Co-Authors: Venkatesan Guruswami, Chaoping Xing, Chen YuanAbstract: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 notion was put forth by Guruswami and Xing (STOC'13) with applications to list decoding variants of Reed-Solomon and Algebraic-geometric codes, and later also used for explicit rank-metric codes with optimal list decoding radius. Guruswami and Kopparty (FOCS'13, Combinatorica'16) gave an explicit construction of subspace designs with near-optimal parameters. This construction was based on polynomials and has close connections to folded Reed-Solomon codes, and required large field size (specifically $q \ge m$). Forbes and Guruswami (RANDOM'15) used this construction to give explicit constant degree "dimension expanders" over large fields, and noted that subspace designs are a powerful tool in linear-Algebraic pseudorandomness. Here, we construct subspace designs over any field, at the expense of a modest worsening of the bound $L$ on total intersection dimension. Our approach is based on a (non-trivial) extension of the polynomial-based construction to Algebraic Function fields, and instantiating the approach with cyclotomic Function fields. Plugging in our new subspace designs in the construction of Forbes and Guruswami yields dimension expanders over $\F^n$ for any field $\F$, with logarithmic degree and expansion guarantee for subspaces of dimension $\Omega(n/(\log \log n))$.
-
subspace designs based on Algebraic Function fields
International Colloquium on Automata Languages and Programming, 2017Co-Authors: Venkatesan Guruswami, Chaoping Xing, Chen YuanAbstract: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 notion was put forth by Guruswami and Xing (STOC'13) with applications to list decoding variants of Reed-Solomon and Algebraic-geometric codes, and later also used for explicit rank-metric codes with optimal list decoding radius. Guruswami and Kopparty (FOCS'13, Combinatorica'16) gave an explicit construction of subspace designs with near-optimal parameters. This construction was based on polynomials and has close connections to folded Reed-Solomon codes, and required large field size (specifically q >= m). Forbes and Guruswami (RANDOM'15) used this construction to give explicit constant degree "dimension expanders" over large fields, and noted that subspace designs are a powerful tool in linear-Algebraic pseudorandomness. Here, we construct subspace designs over any field, at the expense of a modest worsening of the bound $L$ on total intersection dimension. Our approach is based on a (non-trivial) extension of the polynomial-based construction to Algebraic Function fields, and instantiating the approach with cyclotomic Function fields. Plugging in our new subspace designs in the construction of Forbes and Guruswami yields dimension expanders over F^n for any field F, with logarithmic degree and expansion guarantee for subspaces of dimension Omega(n/(log(log(n)))).
-
asymptotic bound for multiplication complexity in the extensions of small finite fields
IEEE Transactions on Information Theory, 2012Co-Authors: Ignacio Cascudo, Chaoping Xing, Ronald Cramer, An YangAbstract:In 1986, D. V. Chudnovsky and G. V. Chudnovsky first employed Algebraic curves over finite fields to construct bilinear multiplication algorithms implicitly through supercodes introduced by Shparlinski-Tsfasman-Vladut, or equivalently, multiplication-friendly codes that we will introduce in this paper. This idea was further developed by Shparlinski-Tsfasman-Vladut in order to study the asymptotic behavior of multiplication complexity in extension fields. Later on, Ballet et al. further investigated the method and obtained some improvements. Recently, Ballet and Pieltant made use of curves over an extension field of to obtain an improvement on the complexity of multiplications in extensions of the binary field. In this paper, we develop the multiplication-friendly splitting technique and then apply this technique to study asymptotic behavior of multiplications in extension fields. By combining this with the idea of using Algebraic Function fields, we are able to improve further the asymptotic results of multiplication complexity. In particular, the improvement for small fields such as the binary and ternary fields is substantial.
-
the torsion limit for Algebraic Function fields and its application to arithmetic secret sharing
International Cryptology Conference, 2011Co-Authors: Ignacio Cascudo, Ronald Cramer, Chaoping XingAbstract:An (n, t, d, n-t)-arithmetic secret sharing scheme (with uniformity) for Fqk over Fq is an Fq-linear secret sharing scheme where the secret is selected from Fqk and each of the n shares is an element of Fq. Moreover, there is t-privacy (in addition, any t shares are uniformly random in Fqt) and, if one considers the d-fold "component-wise" product of any d sharings, then the d-fold component-wise product of the d respective secrets is (n - t)-wise uniquely determined by it. Such schemes are a fundamental primitive in information-theoretically secure multiparty computation. Perhaps counter-intuitively, secure multi-party computation is a very powerful primitive for communication-efficient two-party cryptography, as shown recently in a series of surprising results from 2007 on. Moreover, the existence of asymptotically good arithmetic secret sharing schemes plays a crucial role in their communication-efficiency: for each d ≥ 2, if A(q) > 2d, where A(q) is Ihara's constant, then there exists an infinite family of such schemes over Fq such that n is unbounded, k = Ω(n) and t = Ω(n), as follows from a result at CRYPTO'06. Our main contribution is a novel paradigm for constructing asymptotically good arithmetic secret sharing schemes from towers of Algebraic Function fields. It is based on a new limit that, for a tower with a given Ihara limit and given positive integer l, gives information on the cardinality of the l-torsion sub-groups of the associated degree-zero divisor class groups and that we believe is of independent interest. As an application of the bounds we obtain, we relax the condition A(q) > 2d from the CRYPTO'06 result substantially in terms of our torsion-limit. As a consequence, this result now holds over nearly all finite fields Fq. For example, if d=2, it is sufficient that q = 8,9 or q ≥ 16.
-
Algebraic geometry in coding theory and cryptography
2009Co-Authors: Harald Niederreiter, Chaoping XingAbstract:This textbook equips graduate students and advanced undergraduates with the necessary theoretical tools for applying Algebraic geometry to information theory, and it covers primary applications in coding theory and cryptography. Harald Niederreiter and Chaoping Xing provide the first detailed discussion of the interplay between nonsingular projective curves and Algebraic Function fields over finite fields. This interplay is fundamental to research in the field today, yet until now no other textbook has featured complete proofs of it. Niederreiter and Xing cover classical applications like Algebraic-geometry codes and elliptic-curve cryptosystems as well as material not treated by other books, including Function-field codes, digital nets, code-based public-key cryptosystems, and frameproof codes. Combining a systematic development of theory with a broad selection of real-world applications, this is the most comprehensive yet accessible introduction to the field available.Introduces graduate students and advanced undergraduates to the foundations of Algebraic geometry for applications to information theory Provides the first detailed discussion of the interplay between projective curves and Algebraic Function fields over finite fields Includes applications to coding theory and cryptography Covers the latest advances in Algebraic-geometry codes Features applications to cryptography not treated in other books
Patrick Morton - One of the best experts on this subject based on the ideXlab platform.
-
solutions of the cubic fermat equation in ring class fields of imaginary quadratic fields as periodic points of a 3 adic Algebraic Function
International Journal of Number Theory, 2016Co-Authors: Patrick MortonAbstract:Explicit solutions of the cubic Fermat equation are constructed in ring class fields Ωf, with conductor f prime to 3, of any imaginary quadratic field K whose discriminant satisfies dK ≡ 1 (mod 3), in terms of the Dedekind η-Function. As K and f vary, the set of coordinates of all solutions is shown to be the exact set of periodic points of a single Algebraic Function and its inverse defined on natural subsets of the maximal unramified, Algebraic extension K3 of the 3-adic field ℚ3. This is used to give a dynamical proof of a class number relation of Deuring. These solutions are then used to give an unconditional proof of part of Aigner’s conjecture: the cubic Fermat equation has a nontrivial solution in K = ℚ(−d) if dK ≡ 1 (mod 3) and the class number h(K) is not divisible by 3. If 3 | h(K), congruence conditions for the trace of specific elements of Ωf are exhibited which imply the existence of a point of infinite order in Fer3(K).
-
solutions of the cubic fermat equation in ring class fields of imaginary quadratic fields as periodic points of a 3 adic Algebraic Function
arXiv: Number Theory, 2014Co-Authors: Patrick MortonAbstract:Explicit solutions of the cubic Fermat equation are constructed in ring class fields $\Omega_f$, with conductor $f$ prime to $3$, of any imaginary quadratic field $K$ whose discriminant satisfies $d_K \equiv 1$ (mod $3$), in terms of the Dedekind $\eta$-Function. As $K$ and $f$ vary, the set of coordinates of all solutions is shown to be the exact set of periodic points of a single Algebraic Function and its inverse defined on natural subsets of the maximal unramified, Algebraic extension $\textsf{K}_3$ of the $3$-adic field $\mathbb{Q}_3$. This is used to give a dynamical proof of a class number relation of Deuring. These solutions are then used to give an unconditional proof of part of Aigner's conjecture: the cubic Fermat equation has a nontrivial solution in $K=\mathbb{Q}(\sqrt{-d})$ if $d_K \equiv 1$ (mod $3$) and the class number $h(K)$ is not divisible by $3$. If $3 \mid h(K)$, congruence conditions for the trace of specific elements of $\Omega_f$ are exhibited which imply the existence of a point of infinite order in $Fer_3(K)$.
Stéphane Ballet - One of the best experts on this subject based on the ideXlab platform.
-
tower of Algebraic Function fields with maximal hasse witt invariant and tensor rank of multiplication in any extension of mathbb f _2 and mathbb f _3
Journal of Pure and Applied Algebra, 2018Co-Authors: Stéphane Ballet, Julia PieltantAbstract:Up until now, it was recognized that a detailed study of the p-rank in towers of Function fields is relevant for their applications in coding theory and cryptography. In particular, it appears that having a large p-rank may be a barrier for a tower to lead to competitive bounds for the symmetric tensor rank of multiplication in every extension of the finite field $\mathbb{F}_q$ , with q a power of p. In this paper, we show that there are two exceptional cases, namely the extensions of $\mathbb{F}_2$ and $\mathbb{F}_3$. In particular, using the definition field descent on the field with 2 or 3 elements of a Garcia–Stichtenoth tower of Algebraic Function fields which is asymptotically optimal in the sense of Drinfel'd–Vlăduţ and has maximal Hasse–Witt invariant, we obtain a significant improvement of the uniform bounds for the symmetric tensor rank of multiplication in any extension of $\mathbb{F}_2$ and $\mathbb{F}_3$.
-
tower of Algebraic Function fields with maximal hasse witt invariant and tensor rank of multiplication in any extension of mathbb f _2 and mathbb f _3
arXiv: Algebraic Geometry, 2014Co-Authors: Stéphane Ballet, Julia PieltantAbstract:Up until now, it was recognized that a large number of 2-torsion points was a technical barrier to improve the bounds for the symmetric tensor rank of multiplication in every extension of any finite field. In this paper, we show that there are two exceptional cases, namely the extensions of $\mathbb{F}_2$ and $\mathbb{F}_3$. In particular, using the definition field descent on the field with 2 or 3 elements of a Garcia-Stichtenoth tower of Algebraic Function fields which is asymptotically optimal in the sense of Drinfel'd-Vladut and has maximal Hasse-Witt invariant, we obtain a significant improvement of the uniform bounds for the symmetric tensor rank of multiplication in any extension of $\mathbb{F}_2$ and $\mathbb{F}_3$.
-
on the tensor rank of multiplication in any extension of f2
Journal of Complexity, 2011Co-Authors: Stéphane Ballet, Julia PieltantAbstract:In this paper, we obtain new bounds for the tensor rank of multiplication in any extension of F"2. In particular, it also enables us to obtain the best known asymptotic bound. To this aim, we use the generalized algorithm of type Chudnovsky with derivative evaluations on places of degree one, two and four applied on the descent over F"2 of a Garcia-Stichtenoth tower of Algebraic Function fields defined over F"2"^"4.
-
on the tensor rank of multiplication in any extension of f_2
arXiv: Algebraic Geometry, 2010Co-Authors: Stéphane Ballet, Julia PieltantAbstract:In this paper, we obtain new bounds for the tensor rank of multiplication in any extension of $\F_2$. In particular, it also enables us to obtain the best known asymptotic bound. In this aim, we use the generalized algorithm of type Chudnovsky with derivative evaluations on places of degree one, two and four applied on the descent over $\F_2$ of a Garcia-Stichtenoth tower of Algebraic Function fields defined over $\F_{2^4}$.
-
On the existence of dimension zero divisors in Algebraic Function fields defined over F_q.
Acta Arithmetica, 2010Co-Authors: Stéphane Ballet, Christophe Ritzenthaler, Robert RollandAbstract:Let $\mathbf{F}/\mathbb{F}_q$ be an Algebraic Function field of genus $g$ defined over a finite field $\mathbb{F}_q$. We obtain new results on the existence, the number and the density of dimension zero divisors of degree $g-k$ in $\mathbf{F}/\mathbb{F}_q$ where $k$ is an integer $\geq 1$. In particular, for $q=2,3$ we prove that there always exists a dimension zero divisor of degree $\gamma-1$ where $\gamma$ is the $q$-rank of $\mathbf{F}/\mathbb{F}_q$ and in particular a non-special divisor of degree $g-1$ when the Jacobian of $\mathbf{F}/\mathbb{F}_q$ is ordinary. We also give a necessary and sufficient condition for the existence of a dimension zero divisor of degree $g-k$ for a hyperelliptic field $\mathbf{F}/\mathbb{F}_q$ in terms of its Zeta Function.
Henning Stichtenoth - One of the best experts on this subject based on the ideXlab platform.
-
topics in geometry coding theory and cryptography
2010Co-Authors: Arnaldo Garcia, Henning StichtenothAbstract:The theory of Algebraic Function fields over finite fields has its origins in number theory. However, after Goppa`s discovery of Algebraic geometry codes around 1980, many applications of Function fields were found in different areas of mathematics and information theory. This book presents survey articles on some of these new developments. The topics focus on material which has not yet been presented in other books or survey articles.
-
Algebraic Function Fields and Codes
2010Co-Authors: Henning StichtenothAbstract:The theory of Algebraic Function fields has its origins in number theory, complex analysis (compact Riemann surfaces), and Algebraic geometry. Since about 1980, Function fields have found surprising applications in other branches of mathematics such as coding theory, cryptography, sphere packings and others. The main objective of this book is to provide a purely Algebraic, self-contained and in-depth exposition of the theory of Function fields. This new edition, published in the series Graduate Texts in Mathematics, has been considerably expanded. Moreover, the present edition contains numerous exercises. Some of them are fairly easy and help the reader to understand the basic material. Other exercises are more advanced and cover additional material which could not be included in the text. This volume is mainly addressed to graduate students in mathematics and theoretical computer science, cryptography, coding theory and electrical engineering.
-
excellent nonlinear codes from Algebraic Function fields
IEEE Transactions on Information Theory, 2005Co-Authors: Henning Stichtenoth, Chaoping XingAbstract: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.
-
on the asymptotic behaviour of some towers of Function fields over finite fields
Journal of Number Theory, 1996Co-Authors: Arnaldo Garcia, Henning StichtenothAbstract:Let F Fl be an Algebraic Function field of one variable, whose constant field is the finite field of cardinality l. Weil's theorem states that the number N=N(F ) of places of degree one of F Fl satisfies the estimate N l+1+2g l , (0.1) where g= g(F ) denotes the genus of F. It is well known that for g large with respect to l, the Weil bound (0.1) is not optimal; see [5, 9]. Drinfeld and Vladut [1] proved the following asymptotic result: Let Nl (g) :=max[N(F ) | F is a Function field over Fl of genus g], and A(l) :=lim sup g Nl (g) g. (0.2) article no. 0147
-
elementary abelianp extensions of Algebraic Function fields
Manuscripta Mathematica, 1991Co-Authors: Arnaldo Garcia, Henning StichtenothAbstract:LetK be a field of characteristicp>0 andF/K be an Algebraic Function field. We obtain several results on Galois extensionsE/F with an elementary Abelian Galois group of orderpn. (a) E can be generated overF by some elementy whose minimal polynomial has the specific formTpn−T−z. (b) A formula for the genus ofE is given. (c) IfK is finite, then the genus ofE grows much faster than the number of rational points (as [E∶F] → ∞). (d) We present a new example of a Function fieldE/K whose gap numbers are nonclassical.
Julia Pieltant - One of the best experts on this subject based on the ideXlab platform.
-
tower of Algebraic Function fields with maximal hasse witt invariant and tensor rank of multiplication in any extension of mathbb f _2 and mathbb f _3
Journal of Pure and Applied Algebra, 2018Co-Authors: Stéphane Ballet, Julia PieltantAbstract:Up until now, it was recognized that a detailed study of the p-rank in towers of Function fields is relevant for their applications in coding theory and cryptography. In particular, it appears that having a large p-rank may be a barrier for a tower to lead to competitive bounds for the symmetric tensor rank of multiplication in every extension of the finite field $\mathbb{F}_q$ , with q a power of p. In this paper, we show that there are two exceptional cases, namely the extensions of $\mathbb{F}_2$ and $\mathbb{F}_3$. In particular, using the definition field descent on the field with 2 or 3 elements of a Garcia–Stichtenoth tower of Algebraic Function fields which is asymptotically optimal in the sense of Drinfel'd–Vlăduţ and has maximal Hasse–Witt invariant, we obtain a significant improvement of the uniform bounds for the symmetric tensor rank of multiplication in any extension of $\mathbb{F}_2$ and $\mathbb{F}_3$.
-
tower of Algebraic Function fields with maximal hasse witt invariant and tensor rank of multiplication in any extension of mathbb f _2 and mathbb f _3
arXiv: Algebraic Geometry, 2014Co-Authors: Stéphane Ballet, Julia PieltantAbstract:Up until now, it was recognized that a large number of 2-torsion points was a technical barrier to improve the bounds for the symmetric tensor rank of multiplication in every extension of any finite field. In this paper, we show that there are two exceptional cases, namely the extensions of $\mathbb{F}_2$ and $\mathbb{F}_3$. In particular, using the definition field descent on the field with 2 or 3 elements of a Garcia-Stichtenoth tower of Algebraic Function fields which is asymptotically optimal in the sense of Drinfel'd-Vladut and has maximal Hasse-Witt invariant, we obtain a significant improvement of the uniform bounds for the symmetric tensor rank of multiplication in any extension of $\mathbb{F}_2$ and $\mathbb{F}_3$.
-
on the tensor rank of multiplication in any extension of f2
Journal of Complexity, 2011Co-Authors: Stéphane Ballet, Julia PieltantAbstract:In this paper, we obtain new bounds for the tensor rank of multiplication in any extension of F"2. In particular, it also enables us to obtain the best known asymptotic bound. To this aim, we use the generalized algorithm of type Chudnovsky with derivative evaluations on places of degree one, two and four applied on the descent over F"2 of a Garcia-Stichtenoth tower of Algebraic Function fields defined over F"2"^"4.
-
on the tensor rank of multiplication in any extension of f_2
arXiv: Algebraic Geometry, 2010Co-Authors: Stéphane Ballet, Julia PieltantAbstract:In this paper, we obtain new bounds for the tensor rank of multiplication in any extension of $\F_2$. In particular, it also enables us to obtain the best known asymptotic bound. In this aim, we use the generalized algorithm of type Chudnovsky with derivative evaluations on places of degree one, two and four applied on the descent over $\F_2$ of a Garcia-Stichtenoth tower of Algebraic Function fields defined over $\F_{2^4}$.