Jo60: A Modern Computer Algebraist
Celebrating the Research and Influence of Joachim von zur Gathen at 60
Thursday 27 - Saturday 29 May 2010,
at b-it, Bonn, Germany.
The research of Joachim von zur Gathen has spanned many areas of mathematics and computer science, including computational complexity, cryptography, finite fields, and computer algebra. His influence and contributions to these fields has been felt through his many papers, students, collaborators, colleagues and friends.
Please join us in celebrating the rich and ongoing career of our friend and colleague in Bonn, Germany from May 27 - 29, 2010.
Program
Thursday
27 May 2010 0930
Welcome
27 May 2010 0940
How modern is computer algebra?
Jürgen Gerhard (Maplesoft, Canada)
After finishing my PhD, I have been fortunate enough to be able to work close to research and on topics closely related to what I was trained for, as part of my daily job in industry. In this talk, I will discuss several aspects of computer algebra that I've worked on or been involved with, their relation to Modern Computer Algebra, as well as the challenges they pose. The topics include symbolic series computations, asymptotically fast algorithms, control theory, modeling of dynamical systems, and parallel algorithms.
27 May 2010 1025
Problem reductions in algorithmic number theory
Eric Bach (University of Wisconsin, USA)
As a field of research, the design and analysis of algorithms for number-theoretic problems draws from two sources. On one hand, there is the pragmatic need, coming from number theory and the areas to which it is applied, to have efficient methods to solve particular problems. On the other hand, there is the theoretical computer scientist's natural desire to classify number-theoretic problems as to their computational difficulty. These two approaches converged in the 1970's, with the advent of provably effective randomized algorithms for problems such as primality. In the decades hence, one recurrent dream has been to build a theory that does for number-theoretic complexity what NP-completeness has done for combinatorial algorithms, and uncover the relations between problems that explain why certain ones are easy and others difficult. This talk will be a report on the status of this project, with some attention paid to recent progess (derandomizations, invading the turf of modular forms, etc.)
Talk slides (PDF).
27 May 2010 1130
Smoothed analysis of condition numbers
Peter Bürgisser (Universität Paderborn, Germany)
We present some recent results on the probabilistic behaviour of interior point methods for the convex conic feasibility problem and for homotopy methods solving complex polynomial equations. As suggested by Spielman and Teng, the goal is to prove that for all inputs (even ill-posed ones), and all slight random perturbations of that input, it is unlikely that the running time will be large. These results are obtained through a probabilistic analysis of the condition of the corresponding computational problems.
Talk slides (PDF).
27 May 2010 1215
Evaluation, interpolation and multivariate multiplication
Éric Schost (University of Western Ontario, Canada)
Efficient algorithms are known for operations such as univariate polynomial multiplication or Euclidean division; the main challenge is to close gaps between linear time and linear-up-to-logarithmic-factors. For multivariate problems, the situation is less clear, as many algorithms involve overheads that are exponential in the dimension.
This talk will present algorithms for multivariate evaluation and interpolation, with an application to the multiplication of multivariate power series, that manage to avoid such issues.
Based on joint work with Joris van der Hoeven.
Talk slides (PDF).
27 May 2010 1430
Official opening ceremony
27 May 2010 1500
Probability, algorithms and complexity
Volker Strassen (Universität Konstanz, ret., Germany)
In this talk I will discuss some topics of mathematics and theoretical computer science that I found and find fascinating.
Extended talk slides (PDF).
27 May 2010 1630
Polynomial iterations: Algebraic properties and applications
Igor Shparlinski (Macquarie University, Australia)
We outline some recent results and pose several open questions about the algebraic properties of univariate and multivariate polynomial iterations. These include the degree growth, irreducibility and non-singularity. Studying these properties is also motivated by applications to pseudorandom number generators and some other cryptographic constructions, such applications will be outline as well.
Talk slides (PDF).
27 May 2010 1715
The indomitable Berlekamp/Massey algorithm
Erich Kaltofen (North Carolina State University, USA)
The numbers 1,1,2,3,5,8,13,21,... are linearly generated. But how to compute the generator from an initial segement of the sequence? And how long a segment? And how to update the recursion when an element down the line doesn't fit. The Toeplitz solvers up to the early 1960s couldn't, until Elwyn Berlekamp's 1967 BCH decoding algorithm.
My talk will give a simple self-contained explanation on the workings of the classical Berlekamp-Massey algorithm, based structured column echelon forms, i.e., sigma bases. I shall also mention a Berlekamp/Massey algorithm for linearly generated matrix sequences with early termination, Fatou's 1906 lemma, a fraction free algorithm for normalizable linearly generated matrix sequences, and explicit counts how many Toeplitz matrices with entries prescribed to fixed values or ranging over a finite field are singular.
This is joint work with George Yuhasz.
Friday
28 May 2010 0930
29.5 years of Maple: how many of the design principles of the system paid dividends
Gaston Gonnet (ETH Zürich, Switzerland)
Most of the original literature about Maple described it as a "compact and efficient computer algebra system". It was partly our goal to be able to run in small desktop computers and even on a pocket computer (the term "pocket symbolic" was also used). This talk will concentrate on four aspects of the early design that went in this direction and were the cornerstones of the design. These are the use of the language C, the S2T measure of complexity, option remember and its implication which is the unique representation of subexpression and the systematic elimination of quadratic algorithms.
Talk slides (PDF).
28 May 2010 1000
Inverting integer and polynomial matrices
Arne Storjohann (University of Waterloo, Canada)
The exact inverse of an integer or polynomial matrix of dimension n can require a factor of n more space to write down than the input matrix. The cost of traditional inversion methods, such as Chinese remaindering or Newton iteration, cost a factor of n more than this. In this talk I survey three recent improvements in computing and representing the inverse. The first is the double-divide and conquer method of Jennearod & Villard (2005), the first nearly optimal algorithm in the case of generic polynomial matrices. The second is the sparse inverse expansion formula, which gives a representation as a straight line formula whose size is only a logarithmic factor larger than the input matrix. Finally, I will discuss the outer product adjoint formula, which gives a Las Vegas algorithm to compute the exact inverse of a well conditioned integer matrix in nearly optimial time.
Talk slides (PDF).
28 May 2010 1030
Computer algebra and practical decoding algorithms
Amin Shokrollahi (École Polytechnique Fédérale de Lausanne, Switzerland)
Reed-Solomon codes are one the most widely used error-correcting codes. Thanks to their use in modern storage systems, they amount to over 75 percent of all codes used in practice. The need for larger storage media has called for a major change in this industry, leading to the near adoption of 4KB sector sizes of hard disks, as opposed to 512 bytes which has been the de-facto standard for the last decade. This change has caused a rethinking of the error-correcting technology used. One of the proposals in this regard is the use of long Reed-Solomon codes. A major bottleneck of traditional decoders for long codes is finding roots of a univariate polynomial over a finite field. In this talk we will show how to use tools from computer algebra to solve this problem and produce decoders that are fast in software and, not surprisingly, also in hardware.
28 May 2010 1130
Average time fast SVP and CVP algorithms for low density lattices and the factorization of integers
Claus-Peter Schnorr (Johann Wolfgang Goethe-Universität Frankfurt, Germany)
We propose and analyze novel algorithms for finding shortest and closest lattice vectors. The algorithm New Enum performs the stages of exhaustive enumeration of short/close lattice vectors in order of decreasing success rate. We analyze New Enum for lattice bases satisfying GSA which in practice holds on the average for well reduced bases. New Enum solves SVP in nn/8+o(n) time for bases of dimension n that satisfy GSA. Under the volume heuristics a shortest lattice vector is found in polynomial time if the density of the lattice is moderately small. This might affect the RSA scheme. Integers N can be factored by solving (ln N)O(1) CVP's for the prime number lattice. Under combined standard and new heuristics these CVP's are solvable in polynomial time.
Talk slides (PDF).
28 May 2010 1215
General cryptographic protocols: A brief survey
Oded Goldreich (Weizmann Institute of Science, Israel)
We survey basic definitions and results concerning secure multi-party computations, where the two-party case is an important special case. In a nutshell, these results assert that, under a variety of reasonable settings and/or assumptions, it is possible to construct protocols for securely computing any desirable multi-party functionality. Confining ourselves to the very basics of this vast area of study, we focus on the stand-alone setting, while leaving the survey of the study of the security of concurrent executions to other surveys.
Talk slides (PowerPoint).
28 May 2010 1400
Greedy algorithms and why simple algorithms can be complex
Allan Borodin (University of Toronto, Canada)
While there has been a rich and ongoing development of new and often surprising algorithms in diverse areas, conceptually simple algorithms are often used for expediency and sometimes even to obtain the best known results for many fundamental problems. An ambitious (or perhaps naive) goal is to develop a theory for ``conceptually simple combinatorial algorithms'', starting off with greedy or myopic algorithms. I will review some of the (extensive) history of previous work in this regard, some recent ideas and results, and my current thinking about the power and (provable) limitations of simple algorithmic paradigms. In particular, I will present the priority algorithm framework as a model for greedy-like optimization algorithms. This model is also a good starting point for other simple algorithmic frameworks.
28 May 2010 1445
Galois theory in algebras over finite fields - applications to the Berlekamp algebra
Preda Mihăilescu (University Göttingen, Germany)
It is a useful pattern to interpret an Fp-algebra A = Fp[ X ]/(f(X)), with f ∈ Fp[ X ], as the image from some global extension in the following sense: there is an p-unramified global galois extension L/K in which p is totally split, and a prime PK ⊆ K above p, such that:
- L = K[ X ]/(g1), for some polynomial g1 ∈ O(K)[ X ] with g1 mod PK = f.
- A = O(K)[ X ]/ (PK, g1 O(K) )[ X ])
In such a situation the galois group Aut( A/Fp ) is generated by Frobenius on the one side and the reduction of the global galois group G=Gal(L/K), on the other side. Since the latter can be evaluated using some polynomials which can be computed in the complex plane, we have a ressource for relaxing the use of evaluations of the Frobenius. This is interesting for small extension degrees and large p.
There are different applications to this idea. I will talk about a new road - which might be better investigated by May - that yields a deterministic variant of the Berlekamp algorithm in some cases in which the lift L/K is well controlled.
Talk slides (PDF).
Saturday
29 May 2010 0930
Counting polynomials over finite fields: Random properties and algorithms
Daniel Panario (Carleton University, Canada)
In this talk we survey old and new results about counting univariate polynomials over finite fields. For example, we are interested in questions such as:
- How many irreducible factors a polynomial is expected to have?
- How often will it be squarefree or k-free?
- What is the expected largest (smallest) degree among its irreducible factors?
- How is the degree distribution among its irreducible factors?
- How often a polynomial is m-smooth (all irreducible factors of degree ≤m)?
- How often two polynomials are m-smooth and coprime?
- How is the degree distribution among the irreducible factors of the gcd of several polynomials?
- What is the expected degree of the splitting field of a polynomial?
We show a methodology that can be systematically employed to study this type of problems. This framework has two basic components: generating functions to express the properties of interest, and asymptotic analysis when exact estimations are not possible. This generic methodology naturally relates finite fields and their applications to combinatorics, number theory, and average-case analysis of polynomial factorization algorithms.
Talk slides (PDF).
29 May 2010 1000
Aspects of a mathematicians work in the business world
Michael Nöcker (Düsseldorf, Germany)
A mathematician's work in the scientific world is well-known to most of use. Searching and creating new ideas, teaching classes and publishing these results. But how is a mathematician's work in the business world? Is there any mathematics in his daily work at all? We will give a survey influenced by personal experiences after working in the Business World for a couple of years. And the experience shows that the core competences of a mathematician are very useful in the Business World - even if he does not deal with mathematics at all.
Talk slides (PowerPoint).
29 May 2010 1030
Decomposing for 24 years and counting the collisions
Mark Giesbrecht (University of Waterloo, Canada)
Algorithms for the functional decomposition of polynomials have come a long way since those first presented more than three decades ago. We will make a whirlwind survey of functional decomposition algorithms, especially for the aptly-named "wild" case. One focus will be on decomposing linearized polynomials and recent work on counting and classifying those polynomials with multiple distinct decompositions -- collisions -- in some very wild cases. Another focus will be on the (insidious?) effect of this work on a young Master's student and his many subsequent collisions with these problems.
Talk slides (PDF).