<span class=strong>Reception and Poster Session</span>

Monday, April 16, 2007 - 4:00pm - 6:00pm
Lind 400
  • Computing Zeta Functions of Sparse, Nondegenerate Hypersurfaces
    John Voight (University of Minnesota, Twin Cities)
    We discuss the efficient computation of the zeta function of a
    hypersurface X defined over a finite field k. The zeta function
    Z(X,T) of X is the exponential generating series for the number of
    points on X defined over k and its finite extensions; Z(X,T) is a
    rational function in T. Zeta functions arise naturally in coding
    theory, arithmetic geometry, complexity theory, and many other areas.
    We consider the situation when X is affine, toric, or projective, when
    its defining equation f is nondegenerate (a condition which implies
    that X is smooth and which holds outside of a codimension 1 subset),
    and when f is sparse (consisting of few monomials). In this
    situation, one can use Dwork cohomology to give a very efficient
    method of computing Z(X,T). We exhibit this method and provide
    several examples.
  • Decoding Linear Codes via Solving Systems of Polynomial Equations
    Stanislav Bulygin (Universität Kaiserslautern)
    This is a joint work of the presenter and Ruud Pellikaan (Technical University of Eindhoven, Netherlands). We
    investigate a question of decoding linear codes, in particular up to half the minimum distance. We propose a method based on solving systems of polynomial equations over a finite field. Such a method was already quite successfully applied for cyclic codes earlier, we move on to the general case. We concentrate on solving the systems that emerge with the use of Groebner bases. The poster reflects a theoretical framework, the main result (the system we want to solve has a unique solution, etc.), and also some results on complexity estimation and experimental results.
  • Nonextendibility of Mutually Unbiased Bases
    Meera Sitharam (University of Florida)
    Two orthonormal bases of a finite dimensional Hilbert space are
    mutually unbiased if for every pair of vectors one from each basis,
    the modulus of the standard inner product is the same.
    The problem of determining bounds on the maximum number of
    such bases (MUBs) for a fixed dimension is an important open problem
    of 20 years that has been shown to arise in different guises in many
    areas of mathematics.
    The most common application of MUBs is found in quantum cryptography
    where MUBs are the quantum states used in many protocols.

    Here we consider 2 questions and provide preliminary results
    and conjectures:

    1. When is a given set of MUBs non-extendible? I.e.,
      characterize mutually unbiased sets
      M1,M2,..,Mk of for which there is no
      basis M unbiased to M1,..,Mk?

    2. Characterize families of bases where non-extendibility
      of a set of MUBs imply maximality, and are there natural
      families of bases with this property. I.e, within such a family of
      bases, a greedy method for constructing MUBs would guarantee
      a maximal cardinality MUB collection.

    This is joint work with Oscar Boykin and Mohamad Tarifi
    at the University of Florida.
  • Metric Structure of Linear Codes
    Diego Ruano (Universität Kaiserslautern)
    We use the study of bilinear forms over a finite field to give a decomposition of the linear codes similar to the one in [D. Ruano: On the structure of generalized toric codes, arXiv:cs.IT/0611010, 2006] for generalized toric codes. Such decomposition, called geometric decomposition of a linear code and which can be obtained in a constructive way, allows to express easily the dual of a linear code and gives a new paradigm for linear codes. The proofs for characteristic 2 are different, but they will be developed parallel.
  • A Complexity-reduced Interpolation Algorithm for Soft-decision Decoding of Reed-Solomon Codes
    Kwankyu Lee (Korea Institute for Advanced Study (KIAS))
    Soon after Lee and O'Sullivan proposed a new interpolation algorithm for
    algebraic soft-decision decoding of Reed-Solomon codes, there have been some
    attempts to apply a coordinate transformation technique to the new
    algorithm, with a remarkable complexity reducing effect. We propose a
    conceptually simple way of applying the transformation technique to the
    interpolation algorithm.
  • New Fewnomial Upper Bounds
    Frank Sottile (Texas A & M University)
    In 1980, Askold Khovanskii established his fewnomial bound
    for the number of real solutions to a system of polynomials,
    showing that the complexity of the set of real solutions to
    a system of polynomials depends upon the number of monomials
    and not on the degree. This fundamental finiteness result
    in real algebraic geometry is believed to be unrealistically large.

    I will Describe joint work with Frederic Bihan on a new
    fewnomial bound which is substantially lower than Khovanskii's
    bound and asymptotically optimal. This bound is obtained by
    first reducing a given system to a Gale system, and then
    bounding the number of solutions to a Gale system. Like
    Khovanskii's bound, this bound is the product of an exponential
    function and a polynomial in the dimension, with the exponents
    in both terms depending upon the number of monomials. In our
    bound, the exponents are smaller than in Khovanskii's.
  • Descartes Rule for Complete Fields and Arbitrary Codimension
    J. Maurice Rojas (Texas A & M University)
    We discuss an extension of Descartes' Rule (for univariate
    polynomials over the real numbers) to arbitrary k x n polynomial
    systems over a field L which is either the real numbers or the
    p-adic rationals. Over R, our extension fails for certain systems,
    but we can characterize precise regions (in the coefficient space)
    where our extension holds. Over the p-adic rationals, our extension
    holds over even larger regions in the coefficient space. We then
    conclude with a conjecture on what optimal fewnomial estimates should
    like in general.
  • List Decoding BCH Codes
    Philip Busse (University of Kentucky)
    List decoding Reed-Solomon codes via an interpolation and root-finding algorithm was pioneered by Madhu Sudan in the mid to late 1990's. In 2006, Kwankyu Lee and Michael O'Sullivan developed a Gröbner basis based implementation of the interpolation algorithm, which they showed was an efficient generalization of the Berlekamp-Massey Algorithm.
    We propose to apply these ideas to list decoding BCH codes by
    presenting BCH codes as subfield subcodes of generalized Reed-Solomon
    codes and to explore the resulting algorithm. In particular, we seek ways to optimize the new algorithm and to compare it with the Berlekamp-Massey algorithm.
  • The Word Problem for a Class of Groups with Infinite Presentation: Amputationally Universal Problem in the BSS Model
    Klaus Meer (Syddansk Universitet (University of Southern Denmark))
    Joint work with Martin Ziegler.

    The word problem for discrete groups is well-known to be undecidable
    by a Turing Machine; more precisely, it is reducible both to and from
    and thus equivalent to the discrete Halting Problem.
    The present work introduces and studies a real extension of
    the word problem for a certain class of groups which are presented
    as quotient groups of a free group and a normal subgroup.
    The main result establishes the word problem for such groups to be
    computationally equivalent to the Halting Problem for BSS machines
    over the reals.
    It thus provides the first non-trivial example of a concrete
    problem that is computationally universal for the BSS model.
  • NP, coNP and the Nullstellensatz: Lower Bounds for Stable Set and graph Coloring Nullstellensatze
    Susan Margulies (University of California)
    Systems of polynomial equations over the complex numbers can be used
    to characterize NP-Complete graph-theoretic decision problems. From
    the point of view of computer algebra and symbolic computation, these
    are interesting polynomial systems because they are provably hard:
    solving them is as hard as solving the underlying NP-Complete problem.
    Furthermore, unless NP = coNP, there must exist infinite instances of
    these infeasible systems whose Hilbert Nullstellensatz certificates
    grow with respect to the underlying graphs.