Category Archives: Research

The (un)importance of theory

I went to a talk by Mike Powell (Cambridge University) yesterday. He is a well-known worker in approximation theory and optimization. His title, “The unimportance of theory in the development of optimization algorithms” certainly provoked me to attend.

As I understood his thesis, many practically useful algorithms have been developed for optimization problems (we are talking about continuous stuff here, not the discrete algorithms beloved of CS theorists), despite a lack of proper convergence theory. People (may) have been deterred from publishing good algorithms for lack of such theory. Also, worst-case bounds available do not predict the running time on typical problem instances.

This of course is old news if you know about quicksort, or indeed almost any algorithm. In 2003 Robert Sedgewick told me about experiments he undertook when writing the latest version of his series of textbooks on algorithms. The known upper bounds turned out to be useless in comparing algorithms, since they were so huge compared to the typical runtime. This is why the field of analysis of algorithms has existed and developed since started by Knuth in 1962.

But there is a big difference, it seems to me. For algorithms like quicksort, correctness is easy to prove and we are only discussing running time. But for optimization algorithms as discussed above, as far as I understand it, correctness can only be established by convergence theory. When I raised this,, I was told that the algorithms in question had been validated by checking them on test cases. If I were relying on an algorithm for running a nuclear power station or flying a spacecraft, I would not be reassured by this.

The right approach to a poor theory is to find a better theory, not to claim that theories are not useful.

Commutative ring theory strikes again

A long time ago I tried to do research in (noncommutative) ring theory. Although I have not worked in the area this millennium, I am always glad to see algebraic methods used in novel ways. One of the most interesting authors to me is Jesus de Loera, who has been involved in LattE (lattice point enumeration program that implements Barvinok’s algorithm), Groebner basis approaches to integer programming, and now using Hilbert’s Nullstellensatz to show that, for example, certain graphs are not 3-colorable.

The idea is that for a graph with $latex n$ vertices and $latex e$ edges, the property of being 3-colorable is equivalent to the solvability over $latex mathbb{C}$ of a certain set of polynomial equations in $latex n + e$ variables. The Nullstellensatz (constructive form) says that if the set is not solvable, then a certificate can be found. The worst-case upper bounds on certificate degree are doubly exponential, but for this particular problem it appears that the degree is low rather often. The paper above has lots of clever tricks to reduce the computational effort. Great stuff!

The remarkable Donald Knuth

On the occasion (today in the USA) of Don Knuth’s 70th birthday, several bloggers have posted tributes (see Jeffrey Shallit’s list). His list of achievements is really impressive, and he has had a big influence on me. To name a few areas, somewhat facetiously: his founding of the field of analysis of algorithms (AofA) led to the development of a community of people who are heavy users of generating function methodology and therefore may be interested in my research in that area, and it gave me something nice to teach as a mathematician moving into a CS department! More seriously, I can’t conceive of computer science as a real science without proper analysis of algorithms, and I would hate to have to write papers without using TeX.

Since unalloyed praise can get a bit cloying, I will mention that it might have been better for the world if Knuth (or someone else) had been able to build a school of AofA in the USA. The algorithms community in the USA is heavily dominated by “worst-case” analysis and indeed by analysis of problem complexity, which is a very weak form of analysis of algorithms, concentrating as it does on lower bounds and rather weak (many would say useless) upper bounds.

The main development of AofA along Knuthian lines has been in Europe, in France (Philippe Flajolet and others) and Austria particularly. In recent years Bob Sedgewick and others have tried to bridge the gap between these communities through meetings such as ANALCO, but at least to my eyes they have not yet had great success.

Of course some may say that the sort of very detailed analysis by Knuth is unnecessary for a working computer scientist. And even if his analyses made sense in the days of flat memory, the prevalence of such things as caching makes it impossible to make such detailed predictions nowadays. But perhaps we just need some better mathematics.

Come to New Zealand for algorithms/combinatorics in 2008

I am involved in organizing two conferences in 2008 (both in summer in nice places to visit!)

Napier, 18-22 February, sponsored by NZIMA, with invited speakers Michael Mitzenmacher (Harvard), Dominic Welsh (Oxford), Steve Linton (St Andrews), Brendan McKay (ANU Canberra), Michael Langston (Tennessee).
Auckland 15-19 December, Fourth International Conference on Combinatorial Mathematics and Combinatorial Computing (4-ICC).

The first is aimed at creating more of a recognized community in the general area of algorithms in NZ (rather than isolated researchers who work on algorithms and applications), and will include many informal sessions and much free time. Costs for NZ students are essentially zero and other subsidies are available. Participant numbers are limited to 60; we currently have some free spaces.

This conference is part of a 6-month NZIMA programme on Algorithms. There are other activities planned including public lectures around the country by David Harel (Weizmann Institute). There is a possibility of another meeting later in the year.

The 4-ICC is in a series of meetings (building on smaller more frequent ones like ACCMCC) that occurs every 10 years, and about 150-200 participants are expected. Details will become available later. If you have never been to New Zealand and have some interest in these research areas, 2008 would be an excellent time to come!

Open source mathematical software!

For many years I have wondered why there was no open-source alternative to Maple, Mathematica and the like. The November 2007 Notices of the American Mathematical Society has an opinion piece discussing this and advocating such a thing. The authors are involved in producing just such an alternative, called SAGE. Written in Python, it seems very promising. It has interfaces to Magma, Maple, Mathematica, MATLAB, and MuPAD, and the free programs Axiom, GAP, GP/PARI, Macaulay2, Maxima, Octave, and Singular. Try it out!

The diameter of random Cayley digraphs of given degree

Manuel Lladser, Primoz Potocnik, Jana Siagova, Jozef Siran and Mark C. Wilson, submitted to Random Structures and Algorithms, June 2006 (12 pages)

Download author version

Abstract: We consider random Cayley digraphs of order $latex n$ with uniformly distributed generating set of size $latex k$. Specifically, we are interested in the asymptotics of the probability such a Cayley digraph has diameter two as $latex ntoinfty$ and $latex k=f(n)$. We find a sharp phase transition from 0 to 1 as the order of growth of $latex f(n)$ increases past $latex sqrt{n log n}$. In particular, if $latex f(n)$ is asymptotically linear in $latex n$, the probability converges exponentially fast to 1.

A new method for computing asymptotics of diagonal coefficients of multivariate generating functions

Alexander Raichev and Mark C. Wilson, to appear in Proceedings of the International Conference on Analysis of Algorithms (Juan-les-Pins, June 2007).

Download author version

Let $latex sum_{mathbf{n}inmathbb{N}^d} f_{mathbf{n}} mathbf{x}^mathbf{n}$ be a multivariate generating function that converges in a neighborhood of the origin of $latex mathbb{C}^d$. We present a new, multivariate method for computing the asymptotics of the diagonal coefficients $latex f_{a_1n,ldots,a_dn}$ and show its superiority over the standard, univariate diagonal method.

Note: there is a typo: in Example 3.6, we should have $latex c = ( (L-b)/a, (L-a)/b )$ where $latex L = sqrt{a^2 + b^2}$.

Random and exhaustive generation of permutations and cycles

to appear in Annals of Combinatorics (10 pages).

Download author version

Abstract: In 1986 S. Sattolo introduced a simple algorithm for uniform random generation of cyclic permutations on a fixed number of symbols. This algorithm is very similar to the standard method for generating a random permutation, but is less well known.

We consider both methods in a unified way, and discuss their relation with exhaustive generation methods. We analyse several random variables associated with the algorithms and find their grand probability generating functions, which gives easy access to moments and limit laws.