Seminars 2008

The class of quasi-twisted codes are known to contain lots of good codes. By employing Discrete Fourier Transform(DFT) and Generalized Discrete Fourier Transform(GDFT), the algebraic structure of quasi-cyclic(QC) codes have been carefully studied. Unfortunately, very little known on the algebraic structure of quasi-twisted(QT) codes or explicit constructions, especially the repeated root case. In this paper, the spectral technique has been generalized to study the algebraic structure of QT codes. With the growing interest in generator construction of QT codes, explicit construction formula is derived in this paper, which is another direction to study the construction of QT codes. It has been shown that some best-known linear codes can also be obtained by the formula.

References:
[1]S. Ling and P. Sol´e, "On the algebraic structure of quasi-cyclic codes I: Finite Fields," IEEE Trans. Inform. Theory, vol.47, pp.2751-2760, 2001.
[2]S. Ling and P. Sol´e, "On the algebraic structure of quasi-cyclic codes II: chain rings," Designs, Codes and Cryptography 30. pp.113-130, 2003.
[3]S. Ling and P. Sol´e, "On the algebraic structure of quasi-cyclic codes III: generator theory," IEEE Trans. Inform. Theory, vol.51, pp. 2692-2700, 2005.
[4]S. Ling, H. Niederreiter, and P. Sol´e,"On the Algebraic Structure of Quasi-cyclic Codes IV: Repeated Roots," Designs, Codes and Cryptography 38, no. 3, pp.337-361, 2006.

This talk is divided in two distinct parts.
The first part deals with codes in Grassmannian spaces.
After a short introduction on codes in Grassmannian spaces, we will present a method to construct infinite families of optimal (regarding the so-called chordal distance) codes in Grassmannian spaces.

The second part of the talk concerns codes and division algebras.
We will explain briefly how division algebras are related to wireless communication. Then we will discuss about the construction of division algebras which fulfills constrains related wireless communications.

The concept of erasure-tolerant information authentication was recently introduced to study an unconditionally secure setting where it is allowed to loose a limited number of message letters during transmission. Even if a part of the message is lost, the verifier will still be able to check the authenticity of some or all of the received message letters.  In general, there might be some letters whose authenticity cannot be verified although they have arrived at the recipient's side. These letters will be discarded.

We consider a special case when the verifier can always check the authenticity of all received message letters.  This property is desirable since no data will be lost due to the verifier's inability to verify its authenticity (i.e., the scheme does not introduce additional degradation of the quality of the received information). We provide necessary and sufficient conditions for a set system based erasure-tolerant authentication scheme to be non-degrading. We also discuss efficient implementations and propose a provably secure stream authentication scheme that makes use of erasure-tolerant authentication codes.

This is based on joint work with Goce Jakimoski and was presented at CT-RSA 2007.

This is a series of three lectures, each between one and one and a half hour, 
intended to show a very tight relationship between algorithms for multiplication of polynomials  over finite fields and error-correcting codes.

Tutorial 1: Algorithms for polynomial multiplication.

This is a general introduction to polynomial multiplication that does not require any
background (neither in Computability, nor in Mathematics). I have already taught this
material in my first MAS720 lecture.

Tutorial 2: From algorithms for polynomial multiplication to error-correcting codes – a lower bound.
In this tutorial I will show how algorithms for polynomial multiplication can be transformed

into error-correcting codes. I will teach all necessary Math background (that is not deep,
but acquaintance with regular matrix representation of field extensions would help).

Tutorial 3: From Goppa codes to algorithms for polynomial multiplication – an upper bound.

In this tutorial I will show how Goppa codes transform into algorithms for polynomial
multiplication (the D.V. & G.V. Chudnovsky algorithm). Math background required is basics
of Algebraic Function Fields (up to the Riemann-Roch theorem) needed for understanding
Goppa codes.

Secret sharing plays an important role in modern cryptography. In a t- out-of-n threshold scheme, n parties receive shares of a secret such that any t+1 can reconstruct the secret, but t cannot. When the probability distribution corresponding to these t shares is independent of the secret, the threshold scheme is called perfect. To satisfy this requirement the size of each share must be at least the size of the secret. If we have equality, we call the scheme "ideal".

Karnin, Greene and Hellman (1983) gave several bounds concerning the maximal number of participants (i.e., the maximal n) in ideal threshold sharing schemes.  We revisit and update the Karnin, Greene, and Hellman bounds, providing optimal bounds on the number of participants in ideal linear threshold secret sharing schemes for various finite fields. We construct these bounds using the same tools that Karnin, Greene, and Hellman introduced in their seminal paper.  We provide optimal bounds for the maximal number of players for a t-out-of-n ideal linear threshold scheme when t=3, for all possible finite fields.  These bounds are very similar to the Bush bounds on MDS codes.  We then generalize this observation.

 An important issue that we encounter today is how to make effective use of the enormous amount of data. These data we can get via internet are from various ways such as various database, electronic articles, academia literatures, technical experimental results, etc. How to automatically and effectively extract, integrate and make use of information embedded in such heterogeneous unstructured data is a challenging task. Two systems, ONBIRES and QUANTA, will be introduced in the talk.

ONBIRES (ONtology-based BIological Relation Extraction System) is designed to perform the tasks: automatic relation extraction from literature, knowledge management such as biological interaction network visualization and query answer, providing hypothesis prediction information for new biological concepts discovery, and even information for knowledge inference.

QUANTA (QUestion Answering Tavern) is a prototype system of question answering, which is designed for natural language search. Currently, search engines, such as Google, all push the task of data mining back to users. The process of a web search is an interactive process repeating what’s illustrated below: the user has to analyze pages to find the information needed and, often, requires better keywords to repeat the search. We think the next generation search engine should be able to provide direct answers. Such a system is possible as demonstrated in our QUANTA system. 

Several open problems regarding super-rotation of Venus atmosphere and the structure and persistence of Jupiter’s Great Red Spot (14000 km across) – in particular the high velocity of 100 m/s in its circumferential band of 3000 km width as observed by Voyagers 1 and 2 – were partially resolved using advanced Monte-Carlo simulations on Desktops of the author’s recent unified statistical theory of shallow water flows on a rotating sphere.

This talk will emphasize some open mathematical problems connected with the existence of constrained minimizers for the Lagrangian of the flow and their relation to the minimizers of the free energy of the statistical theory. Collaborations include T. Andersen, S.M. Assad, Xueru Ding, J. Nebus, R.S. Mavi, and Junping Shi and research over the past 4 years funded by US ARO and DOE. 

In recent years, there has been a great deal of interests in research at the boundaries between algorithms, game theory and economics. This is because many important artifacts, such as the Internet and the web, are deeply affected by cooperation and competition among parties with different economic interests, and logarithms and protocols, e.g. for routing, resource allocation and electronic commerce, need to be rethought in light of these economic effects.

We consider one particular effect, externalities (or network effects), that links the value of a good to a consumer to the set of other consumers having that good. We will review recent studies on externalities in different areas (including mechanism design, viral marketing and social networks, online dating systems, and envy-free pricing) in algorithmic game theory, and discuss directions for future study.

Most of the quantum error-correcting codes (QECCs) are based on the stabilizer formalism which relates quantum codes to certain additive codes over GF(4). However, it is known that non-additive QECCs can have a higher dimension compared to additive QECCs with the same length and minimum distance. The most prominent example is the code  ((5,6,2)) of Rains et al. More recently, some improved one-error-correcting codes of length 9 and 10 have been found. All these codes can be described as codeword stabilized (CWS) quantum codes.

The class of CWS QECCs is very rich, it includes e.g. all stabilizer codes. The prize we have to pay for this generality is that with increasing length it is getting more difficult to find good codes.

Based on the classical non-linear binary Goethals and Preparata codes, we obtain a new family of non-additive quantum codes with parameters ((2^m,2^{2^m-5m+1},8)). The dimension of these codes is eight times higher than the dimension of the best known additive quantum codes of equal length and minimum distance.

We present some theoretic and heuristic estimates for the number of elliptic curves with low embedding which is essential for their applicability in pairing based cryptography. We also give estimates for the number of fields over which such curves may exist. The main ideas behind the proofs will be explained as well. Finally, we give a heuristic analysis of the so-called MNT algorithm and show that it produces a rather "thin" sequence of curves.

One-way functions are the basic primitive of private-key cryptography. However, no provably one-way functions (the ones that can be computed more than polynomially faster than inverted) are known. A natural question is to construct a function that would be at least a little bit (provably!) harder to compute than to invert (call it feebly secure one-way function). Alain Hiltgen (1992) answered this question affirmatively by constructing a function that can be computed by n+O(1)-size circuits but can be inverted only by 2n-size circuits. However, similar constructions of other cryptographic primitives remained unknown.

Trapdoor functions are the basic primitive of public-key cryptography. In this work we construct a family of feebly secure trapdoor functions. This is joint work with Sergey Nikolenko.