Elias Tsigaridas Department of Computer Science, Aarhus University

Abstract: We present aggregate separation bounds, named after Davenport-Mahler-Mignotte (DMM), on the isolated roots of polynomial systems, specifically on the minimum distance between any two such roots. The bounds exploit the structure of the system and the height of the sparse (or toric) resultant by means of mixed volume, as well as recent advances on aggregate root bounds for univariate polynomials.

Søren Asmussen, University of Aarhus, Department of Mathematical Sciences

Abstract: Importance sampling is a technique for improving the performance of crude Monte Carlo simulation. One of the main areas of application is simulation of small probabilities (rare event simulation) where there are many examples where the improvement one can obtain roughly corresponds from going from exponential time algorithms to polynomial time ones.

I give a short introduction to the method and a short survey of classical examples. The last part of the talk is a more detailed case study. A task like the execution of a computer program or the transmission of a file may fail and then needs to restarted. How does one do importance sampling for estimating the rare event probability of excessive delays due to failures?

Srikanth Srinivasan, Institute of Mathematical Sciences, Chennai
joint work with Vikraman Arvind

Abstract: We study the computational complexity of computing the noncommutative determinant. We first consider the arithmetic circuit complexity of computing the noncommutative determinant polynomial. Then, more generally, we also examine the complexity of computing the determinant (as a function) over noncommutative domains. Our hardness results are summarized below:

1. We show that if the noncommutative determinant polynomial has small noncommutative arithmetic circuits then so does the noncommutative permanent, which would imply that the commutative permanent polynomial would have small commutative arithmetic circuits.
2. For any field F we show that computing the n X n permanent over F is polynomial-time reducible to computing the 2n X 2n (noncommutative) determinant whose entries are O(n^2) X O(n^2) matrices over the field F.
3. We also derive as a consequence that computing the n X n permanent over nonnegative rationals is polynomial-time reducible to computing the noncommutative determinant over Clifford algebras of n^{O(1)} dimension.

Our techniques are elementary and use primarily the notion of the Hadamard Product of noncommutative polynomials.

Preprint: arXiv:0910.2370

Host: Peter Bro Miltersen

Kent Andersen, Otto-Von-Guericke University Magdeburg

Abstract: Integer optimization is an important component of Operations Research, and it is used for solving many problems that arise in practice. The state-of-the-art approach for solving integer problems uses so-called cutting-planes to cut off points that have fractional coordinates. Recently a new cutting-plane theory has emerged which is based on lattice-free sets. Lattice-free sets are convex sets whose interior does not contain integer points. The interior of a lattice-free set does therefore not contain any feasible solutions to an integer optimization problem. In this talk we survey this new approach and present some of the results that have been obtained. We also consider algorithmic consequences. In particular we present a new class of cutting planes that have a number of desirable theoretical properties. We call these cutting-planes for zero-coefficient cuts. In terms of quality, zero-coefficient cuts are those cuts that are violated the most, and in terms of efficiency, zero-coefficient cuts can be identified efficiently in polynomial time. Initial computational experiments suggest that zero-coefficient cuts could be an interesting class of cutting-planes to include in practical software for mixed integer optimization.

Uffe Heide-Jørgensen, Department of Mathematics, Aarhus University

Abstract: Everyone knows the determinant of a square matrix. The permanent is less known though it is almost the same thing, one just omits all the switching of signs. Note that in characteristic 2 the permanent and determinant are the same thing. One can compute the determinant of a given matrix in polynomial time using Gaussian elimination. However this does not hold for the permanent, assuming the characteristic is not 2, since it is not multiplicative.

One might ask if there is some way to compute the permanent by "blowing up and applying the determinant". More precisely can one compute the permanent by constructing a bigger matrix with linear (affine) polynomials as entries, such that the permanent equals the determinant applied to this bigger matrix? Valiant has shown that such maps exist; in fact all polynomials can be written as the determinant of some matrix with linear entries.

The topic of this talk is to establish a lower bound of how fast these matrices grow as the original matrices grow. A result due to Mignon and Ressayre gives by use of Hessian matrices that the growth is at least quadratic, when working over a field of characteristic 0. This has been generalized by Cai, Chen and Li to hold over fields of odd characteristic. For a variety X there is a link from the rank of a Hessian matrix to the dimension of the dual variety. We will outline a translation of the work of Mignon, Ressayre, Cai, Chen and Li into the language of dual varieties.

Joshua Brody, Dartmouth College
joint work with Amit Chakrabarti, Ishay Haviv, Oded Regev, Thomas Vidick, and Ronald de Wolf.

Abstract: The past fifteen years has seen an amazing burst of research in streaming algorithms, starting with the famous paper by Alon, Matias, and Szegedy. In particular, space-efficient algorithms are possible for several functions, when you allow both randomness and approximation. However, this comes at a price: most of the algorithms pay a penalty in space that is quadratic with the approximation factor.

In 2003, Woodruff and Indyk showed that this penalty was necessary in the case of one-pass data streams, using a reduction from the one-way complexity of the Gap Hamming problem. However, it has been a long standing open problem whether the same lower bound applies to multipass algorithms.

We extend this lower bound so it holds even when a constant number of rounds of communication are allowed. As a result, we show that even with O(1) passes, streaming algorithms must pay a high price for their approximation. Our main technique combines a Round Elimination Lemma with several isoperimetric inequalities.

Vladimir V. Podolskii, Steklov Mathematical Institute

Abstract: A Boolean function f on n inputs is called a sign-function of an integer polynomial p on n variables if for all n-bit strings x it holds that p(x)>0 if f(x)=1 and p(x)<0 if f(x)=0. In this case p is called a perceptron for f. The degree of the perceptron is simply the degree of the polynomial and the weight of the perceptron is the sum of the absolute values of its coefficients.

In this talk we will be interested in the smallest possible weight of a perceptron of a given degree for a given function. We will review upper and lower bounds on this quantity and give some proof ideas.

The talk will be based on the following papers:

• Vladimir V. Podolskii. Perceptrons of Large Weight. Problems of Information Transmission. 45(1):51-59, 2009.
• Vladimir V. Podolskii. A Uniform Lower Bound on Weights of Perceptrons. Proc. of the Third International Computer Science Symposium in Russia (CSR), pp. 261-272, 2008.

Elias P. Tsigaridas, Institut national de recherche en informatique et automatique (INRIA)

Abstract: Real algebraic numbers are the numbers that are real solutions of a univariate polynomial with integer coefficients, and they are usually represented using the isolating interval representation, that is a square-free polynomial and an isolating interval. To construct such numbers we need to isolate the real roots of a univariate polynomial. We will present some recent complexity and algorithmic results for the problem of real root isolation, and we will sketch on going work on random polynomials.

Algebraic algorithms, and in particular computations with real algebraic numbers and (real) solving of univariate polynomials and polynomial systems, are powerful tools that could be used in many applications. We will present some recent advances in the problem of symmetric tensor decomposition, and in non-linear computational geometry. The latter includes the arrangement of conic arcs, the Voronoi diagram of convex smooth pseudo-circles. and the computation of the topology of a real plane algebraic curve. If time permits, we will also present algorithms that given a convex lattice polygon, test whether it can be decomposed into a Minkowski sum of two other such polygons and if so, find one or all such decompositions. The problem is closely related to the problem of bivariate polynomial factorization.

Peter Bro Miltersen, University of Aarhus, Department of Computer Science

Abstract: Through the example of the BIG MATCH, we give a gentle invitation to the theory of two-player zero-sum stochastic games with limiting average payoffs. Such games were shown to have values in a celebrated 1981-paper by Mertens and Neyman, building on earlier work of Bewley and Kohlberg. A key ingredient of this earlier work is an elegant use of the Tarski transfer theorem. In 2009, Solan and Vielle published an algorithmic version of the theorem of Mertens and Neyman, but without any non-trivial upper bound on the computational resources used by the algorithm. Such a bound would seem to require new theorems of semi-algebraic geometry. We shall discuss as much of the above as the patience of the audience and the ability of the lecturer permits, and save the rest of the story for a later meeting.

Kristoffer Arnsfelt Hansen, University of Aarhus, Department of Computer Science

Abstract: This lecture is the third in a series of lectures on semi-algebraic geometry.

We continue our coverage of cylindrical algebraic decompositions (c.a.d.). We will complete the proof of existence of a c.a.d. adapted to a finite set of polynomials, covering classical theory on resultants and subresultants of polynomials in the process. After this we will turn to the algorithmic aspects of actually computing the c.a.d.

The next talk in the series is the same day an hour later.

Book mentioned at the lecture: Algorithms in Real Algebraic Geometry

Kristoffer Arnsfelt Hansen, University of Aarhus, Department of Computer Science

Abstract: This lecture is the second in a series of lectures on semi-algebraic geometry.

In this lecture we will review the Tarski-Seidenberg theorem proved in last lecture and discuss in detail several consequences of it. Our next goal will be to cover cylindrical algebraic decompositions (c.a.d.), that will provide a vehicle for understanding the geometry of semi-algebraic sets. For instance, using the c.a.d. it is possible to show that any semi-algebraic set is a disjoint union of semialgebraic subsets that are all semialgebraically homeomorphic to an open hypercube. The c.a.d. will also provide the basis for obtaining much more efficient algorithms for deciding first-order sentences over the reals.

Kristoffer Arnsfelt Hansen, University of Aarhus, Department of Computer Science

There is coffee and cake at this seminar.

Abstract: Semi-algebraic geometry is concerned with the set of real solutions of systems of polynomial equations and inequalities, called semi-algebraic sets. In this lecture we will introduce semi-algebraic sets from basics. Next we will prove the Tarski-Seidenberg theorem, that semi-algebraic sets in (n+1)-dimensional space projects to semi-algebraic sets in n-dimensional space. Coupled with parametric versions of real root counting techniques such as Sturm sequences (that we will also cover from basics) this gives us a decision procedure for determining if the given system has a real solution.

This lecture marks the beginning of a series of lectures on semi-algebraic geometry. The intent is that it will over time transform into a reading/lecture series working towards research problems.

To get an impression of the content of the course, see these notes.

Peyman Afshani, University of Aarhus, Department of Computer Science

There is coffee and cake at this seminar.

Abstract: Given a set P of n points in d-dimensional space, a unit-disk graph is a graph built with P as the vertex set, by connecting two vertices (i.e., points) if and only if their Euclidean distance is at most one. We are interested in problems related to the maximum cliques in a unit-disk graph.

These graphs have numerous applications (for instance, they can be used to model wireless networks) and are well studied in computational geometry literature and other fields.

In this talk, after a brief introduction, we will survey a few previous results on this problem. First, we will review how the algorithmic problem of computing the maximum clique corresponds to the following non-algorithmic covering problem: for R^d, find the minimum value of k and a set S of k objects of diameter one, such that *any* shape of diameter one can be covered using k elements of S.

For d=2 the answer is two; for d=3 the best result so far is five and no non-trivial result is known for higher dimensions.

We will also examine a related problem of embedding graphs as unit-disk graphs including some embedding results.

References

• Finding k points with minimum diameter and related problems Alok Aggarwal and Hiroshi Imai and Naoki Katoh and Subhash Suri, Journal of Algorithms, volume 12, pages: 38 - 56, 1991
• Approximation algorithms for maximum cliques in 3D unit-disk graphs, Peyman Afshani and Timothy Chan, CCCG, pages 6--9, 2005
• Approximation and inapproximability results for maximum clique of disc graphs in high dimensions, Peyman Afshani and Hamed Hatami, Information Processing Letters, volume 105, pages 83--87, January 2008
• On finding a large number of 3D points with a small diameter, Minghui Jiang, Discrete Applied Mathematics, 155:2355-2361, 2007

Diophantine approximation in positive characteristic and linear complexity profiles
April 14, 2009 at 15:15-16:15 in Aud. D1 at Department of Mathematics

Simon Kristensen, University of Aarhus, Department of Mathematics

Download slides

Abstract: Diophantine approximation is the quantitative study of the density of the rational numbers inside the real numbers. A fruitful analogue over function fields in positive characteristic has been developed over the years.

This setup has been applied to problems in linear complexity profiles. Linear complexity profiles are a refinement of the global linear complexity, a well known complexity measure in the theory of stream ciphers. The linear complexity profile of a sequence gives a measure of the deviation of the sequence from a truly random sequence.

In the talk, I will describe the field of Diophantine approximation in positive characteristic and outline several results. A particular emphasis will be put on the so-called metrical theory, wherein the measure and Hausdorff dimension of involved sets is studied. I will also describe the relation between Diophantine approximation and complexity profiles.

Many of the mathematical technicalities will be omitted, and all key concepts will be defined and explained.

(This talk is moved from its usual slot of April 7 due to Easter.)

Klaus Thomsen, University of Aarhus, Department of Mathematics

Download slides

There is coffee and cake at this seminar.

Abstract: Formal languages which are infinite, prolongable and factorial are in bijective correspondence with a particular class of dynamical systems, known as subshifts. Subshifts, on the other hand, are currently being studied and partly classified with tools from C*-algebra theory and K-theory. In this talk I want primarily to describe the underlying ideas, and I shall be brief on the more technical details. But references to the litterature will be given.

Kristoffer Arnsfelt Hansen, University of Aarhus, Department of Computer Science

There will be coffee and cake at this seminar.

Abstract: A Kakeya set is any set of points in n-Euclidean space which contains a unit line segment in every direction. The famous Kakeya conjecture is that such sets must have Hausdorff dimension and Minkowski dimension n. In this talk we consider the finite field version of the Kakeya question, and cover a recent optimal lower bound on the size of Kakeya sets due to Zeev Dvir.

We will next cover applications to the problem of randomness extraction studied in theoretical computer science. This problem is the following: We are given access to a source of "dirty" randomness with a guarantee that it has min-entropy k. Using a short seed of pure random bits we wish to transform the source of "dirty" randomness into a source of "pure" randomness, i.e close in statiscal distance to pure random bits.

The talk will be based on the following papers (available at http://www.math.ias.edu/~dvir/papers/lop.html).

• Z. Dvir. On the size of Kakeya sets in finite fields. J. Amer. Math. Soc. (to appear), 2008.
  
• Z. Dvir and A. Wigderson. Kakeya sets, new mergers and old extractors. In FOCS '08, 2008.
  
• Z. Dvir, S. Kopparty, S. Saraf, and M. Sudan. Extensions to the method of multiplicities, with applications to kakeya sets and mergers.

Computing the Tutte Polynomial in Vertex-Exponential Time
Math Aud D3 (1531-215) at 15:15 - 16:15 on Februrary 10, 2009

Thore Husfeldt, ITU Copenhagen and Lund University
joint work with A. Björklund (Lund), P. Kaski (Helsinki), and M. Koivisto (Helsinki), FOCS 2008

There will be coffee and cake at this seminar.

Abstract: The Tutte polynomial sits in the intersection of enumerative combinatorics, graph theory, and statistical physics. Depending on who looks at it, it counts the colourings of a graph, its number of spanning forests, the reliability of a network, the topology of a knot, and many other things; perhaps most importantly, it computes the partition function of the Ising, Potts, and random cluster model. All in all, tens of thousands of research papers have been written about it in some guise or another.

In the first half of my talk I will spend some time introducing the Tutte polynomial in several ways. For the algorithmic audience this will go via the deletion-contraction algorithm. For the more algebraically inclined I will approach it via the chromatic polynomial from algebraic graph theory. I will also show the connection to statistical mechanics via the Potts model, demonstrating all the theoretical physics I know, which isn't a lot.

Then I will show how the Tutte polynomial for a given graph can be computed in time exponential in the number of vertices. (It's straightforward to do this in time exponential in the number of edges.)