Talk 12
| Title: | The languages of words that occur infinitely many times in an infinite word |
| Speaker: | Klaus Thomsen |
| When: | Thursday, May 11, 10:15-12:00 |
| Where: | Aud D1, Department of Mathematical Sciences |
| Abstract |
|
In the talk I will present necessary and sufficient conditions for a
language to be the language of words occurring infinitely many times
in an infinite word. Based on a review of the relation between
dynamical systems and formal languages I will explain the meaning of
this characterisation in dynamical terms.
An accompanying note may be found here.
|
Talk 11
| Title: | On the complexity of numerical computation |
| Speaker: | Peter Bro Miltersen |
| When: | Thursday, April 6, 10:15-12:00 |
| Where: | Aud. D3, Department of Mathematical Sciences |
| Abstract |
|
We study the problem PosSLP: Given a division-free straight-line
program producing an integer N, decide whether N>0. We relate PosSLP
to the Blum-Shub-Smale model of computation and we show that PosSLP
essentially captures the problem of doing arbitrary-precision
numerical computation. We show that the problem of computing the
total degree of a multivariate polynomial given by a straight line
program reduces to PosSLP. Then, using techniques derived from the
construction of uniform constant-depth circuits for integer division
by Hesse et al, we show that PosSlp lies in the counting hierarchy,
CH. Combining our results with work of Tiwari, we show that the
Euclidean Traveling Salesman Problem lies in CH - the previous best
upper bound for this important problem (in terms of classical
complexity classes) being PSPACE.
Along the way, we encounter and discuss a very important
problem in computational complexity of an algebraic flavour:
Given two multi-variate artithmetic straight line programs
(or even formula), decide if they denote the same polynomial.
An efficient Monte Carlo algorithm is known for this problem,
but it is not known to be in P. It was recently shown by
Impagliazzo and Kabanets that giving a non-trivial deterministic
algorithm for this this problem is equivalent to proving
non-trivial circuit lower bounds (in a sense that can be made
precise and will be made precise during the talk).
Joint work with Eric Allender, Peter Burgisser and Johan
Kjeldgaard-Pedersen.
|
Talk 10
| Title: | The F4 algorithm - speeding up Gröbner basis computations
using linear algebra |
| Speaker: | Bjarke Hammersholt Roune |
| When: | Thursday, March 16, 10:15-12:00 |
| Where: | Aud. D2, Department of Mathematical Sciences |
| Abstract |
|
Gröbner bases have many applications and have become one of the more
attractive applications of computer algebra. A major reason for this is the
efficiency of the Buchberger algorithm which is used to compute Gröbner
bases. Even though its worst case complexity is in some cases doubly
exponential, the Buchberger algorithm can compute Gröbner bases of ideals of
practical interest, and it has been radically improved in the last few
years. This non-math-heavy talk is about such an improved variant of the
Buchberger algorithm called F4 (by Faugere), which speeds up the reduction
step in the Buchberger algorithm by exchanging multiple polynomial divisions
for row-reduction of a single matrix. The talk will start with a brief look
at Gröbner bases and the Buchberger algorithm.
An accompanying note may be found here.
|
|
|
