MSI Weekly Bulletin - Week starting Monday 13 November, 2006

In Descriptive Complexity, there is a vast amount of literature on decision problems, and their classes such as \bff{P, NP, L and NL}. However, research on the descriptive complexity of optimisation problems has been limited. In a previous paper, we characterised the optimisation versions of \bf{P} via expressions in second order logic, using universal Horn formulae with successor relations. In this talk, we look at the syntactic hierarchy within the class of polynomially bound maximisation problems. We extend the result in the previous paper by showing that the class of polynomially-bound \bf{NP} (not just \bf{P}) maximisation problems can be expressed in second-order logic using Horn formulae with successor relations. Finally, we provide an application -- we show that the Bin Packing problem with online and item-size constraints can be approximated to within a $Theta(log n)$ bound, by providing a syntactic characterisation for this problem. BIOGRAPHY: Prabhu Manyem obtained his BS and MS degrees at the Indian Institutes of Technology, and his PhD (Discrete Optimisation), with a minor in Computer Science, at North Carolina State University, Raleigh, NC in 1996. After working in the US industry for three years, he joined the University of South Australia at Adelaide in 1999 as a Research Fellow. In February 2005, he moved to the University of Ballarat. His interests are in Complexity, Approximation Algorithms and Discrete Optimisation.

We introduce the method of degenerate variational asymptotics for a class of singularly perturbed ordinary differential equations whose leading order behavior is dominated by gyroscopic forces. Such systems exhibit dynamics on two separate time scales which are dynamically linked with no explicit splitting into slow and fast subsystems. We derive approximate equations for the slow motion to arbitrary order by performing an asymptotic expansion of the Lagrangian rather than the Euler--Lagrange equations of motion themselves. Rigorous justification of the method is provided in two different settings. For harmonic potentials, we show that the method can be understood explicitly in terms of perturbation theory for finite dimensional linear eigenvalue problems. In the general case, we resort to an indirect analysis involving a nonvariational auxiliary model. We present convergence results for O(1)-times and for long times. We illustrate our analytical results by numerical simulation.

The classical and fundamental unique correspondence between stationary point processes on the line and stationary sequences of interpoint distances is based on the linear ordering of the real numbers. In fact, any point of a locally finite doubly-infinite set of reals has a unique predecessor and a unique successor. The existence of such a complete linear and shift-invariant order on locally finite and aperiodic sets in higher dimensions is an amazing open problem. We will discuss a partial solution as well as some interesting relationships to Palm measures of stationary point processes.