Our Projects
Finally we're getting down to what it's all about!
The exciting, innovative stuff done here doesn't just happen out of the blue,
as you may guess, so let me direct a word to those not in the know.
You got ideas, you need a framework to realize them, what do you do?
Define a project!
That's exactly how it works and the IDMATH folks go to great lengths
to do exactly that.
Below the concrete results of their past and current efforts.
Project Gallery
Clicking inside an image will get you to the respective project description.
Construction of Low-Discrepancy Sequences
- Description
- Low-discrepancy sequences are the basic ingredients of quasi-Monte
Carlo methods, e.g. for numerical integration and global optimization.
All modern techniques for the construction of low-discrepancy sequences
are based on the theory of digital (t,s)-sequences.
The project aims to obtain digital (t,s)-sequences
with a significantly better quality parameter t.
- Results
- With the help of global function fields, considerably improved
constructions of digital (t,s)-sequences have been obtained. The
resulting sequences are the best current low-discrepancy sequences.
If t is viewed as a function of the dimension s,
then it can be shown that the construction is asymptotically optimal,
as far as orders of magnitude are concerned.
- Future Targets
- Constructions using places of larger degree.
Software implementation of the sequences.
- Project Manager
- Harald Niederreiter
- References
-
Global Function Fields with Many Rational Places
- Description
- Global function fields (algebraic function fields over finite fields)
with many rational places (places of degree 1) are important in
algebraic coding theory (construction of algebraic geometry codes) and
in quasi-Monte Carlo methods (construction of low-discrepancy sequences).
The main problem is the existence and the explicit construction of
such global function fields. An equivalent problem can
be posed for algebraic curves over finite fileds with many rational points.
- Results
- Asymptotic results based on class field theory for global function
fields and on the Garcia-Stichtenoth tower of global function fields.
Explicit constructions for small fields of constants.
- Future Targets
- Further explicit constructions for small fields of constants.
- Project Manager
- Harald Niederreiter
- References
-
Stream Ciphers and Linear Complexity
- Description
- Stream ciphers are used for the encryption of data in environments requiring a high level of security. The key is a pseudorandom sequence of bits which has to satisfy stringent statistical and complexity-theoretic conditions. The aim of our research is to apply the theory of linear complexity to the analysis of pseudorandom sequences of bits.
- Results
- Probabilistic results on the linear complexity of random sequences of bits
and their linear complexity profile.
- Future Targets
- Study related concepts such as jump complexity and jump complexity profile.
- Project Manager
- Harald Niederreiter
Multiple-Recursive Matrix Method for Pseudorandom Number and Vector Generation
- Description
- The multiple-recursive matrix method generalizes classical methods for
pseudorandom number and vector generation, such as the linear
congruential method, the GFSR method and the matrix method, and
provides a general framework for studying linear methods for
pseudorandom number and vector generation. The aim of the project is a
detailed analysis of this method.
- Results
- Earlier results on the performance of pseudorandom numbers and vectors
have been improved through the analysis of sigma-splitting subspaces of
finite fields.
- Future Targets
- Further analysis of sigma-splitting subspaces of finite fields.
- Project Manager
- Harald Niederreiter
- References
-
Construction of Algebraic-Geometry Codes
- Description
- Algebraic-geometry codes are linear codes for error correction that are
constructed by means of algebraic curves over finite fields. It is
known that this family of codes contains sequences of codes with
excellent asymptotic behavior. The project aims to improve on the
classical construction of algebraic-geometry codes due to Goppa.
- Results
-
Several improved constructions of algebraic-geometry codes have been
obtained. The key idea is to use arbitrary rational points of the
curve rather than just rational points over the field of definition of
the curve as in Goppa's construction. An important asymptotic result
breaks the Gilbert-Varshamov bound for finite fields of sufficiently
large composite nonsquare order.
- Future Targets
- Further constructions and asymptotic results.
- Project Manager
- Harald Niederreiter
- References
-
Eulerian Graphs and Related Topics
- Description
-
This is a monograph consisting of three volumes. Starting from the problem
of the Seven Bridges of Königsberg (treated by L. Euler in 1736), the
first two volumes (already published) have covering walks in graphs as
their main theme, that is, various types of Eulerian trails in Eulerian
graphs and their transformations, double tracings, nowhere-zero flows
and the Chinese Postman Problem in arbitrary graphs. The third volume
will focus on cycle decompositions in Eulerian graphs and cycle
coverings in arbitrary graphs. Other topics will also be treated.
- Results
-
Some of the material presented in the first two volumes has been
developed in the course of writing this monograph, e.g. the theory of
transforming Eulerian trails of special types, characterizing Directed
Postman Tours in a way similar to the undirected case. Some of this new
material has been published subsequently in an improved form in
separate papers.
- Future Targets
-
In Part 2 of the monograph, cycle decompositions with a given
transition system will figure prominently because of their relevance
for the yet unsolved Cycle Double Cover Conjecture and other topics in
graph theory.
- Project Manager
- Herbert Fleischner
- References
-