University of Southampton

The satisfiability (SAT) problem is a central problem in mathematical

logic, computing theory, and artificial intelligence. We consider

instances of SAT specified by a set of boolean variables and a

propositional formula in conjunctive normal form. Given such an instance,

the SAT problem asks whether there is a truth assignment to the variables

such that the formula is satisfied. It is well known that SAT is in

general NP-complete, although several important special cases can be

solved in polynomial time. Extending the work of de Klerk, Warners and van

Maaren, we present new linearly sized semidefinite programming (SDP)

relaxations arising from a recently introduced paradigm of higher

semidefinite liftings for discrete optimization problems. These

relaxations yield truth assignments satisfying the SAT instance if a

feasible matrix of sufficiently low rank is computed. The sufficient rank

values differ between relaxations and can be viewed as a measure of the

relative strength of each relaxation. The SDP relaxations also have the

ability to prove that a given SAT formula is unsatisfiable. Computational

results on hard instances from the SAT Competition 2003 show that the SDP

approach has the potential to complement existing techniques for SAT.

The talk starts with a general introduction of the convex

quadratic semidefinite programming problem (QSDP), followed by a number of

interesting examples arising from finance, statistics and computer sciences.

We then discuss the concept of primal nondegeneracy for QSDP and show that

some QSDPs are nondegenerate and others are not even under the linear

independence assumption. The talk then moves on to the algorithmic side by

introducing the dual approach and how it naturally leads to Newton's method,

which is quadratically convergent for degenerate problems. On the

implementation side of the Newton method, we stress that direct methods for

the linear equations in Newton's method are impossible simply because the

equations are quite large in size and dense. Our numerical experiments use

the conjugate gradient method, which works quite well for the nearest

correlation matrix problem. We also discuss difficulties for us to find

appropriate preconditioners for the linear system encountered. The talk

concludes in discussing some other available methods and some future topics.

The significance of the effects of non-healing wounds has been the topic of many research papers and lectures during the last 25 years. Efforts have been made to understand the effects of long-standing venous hypertension, diabetes, the prevalence of wounds in such conditions with as well as the difficulties faced in managing such wounds with some success. Successful efforts to define standard care regimes have also been made. However, attempts to introduce innovative therapy have been much less successful. Is this merely because we have not understood the intricacies of the problem? And would system based modelling be an untried technique?

Venous ulcers are the majority of lower extremity wounds, and a clinical challenge. A previously developed model of venous ulcers permits some understanding of why compression bandaging is successful but fails to accommodate complications such as exudate and infection. Could this experimental model be improved by system based modelling?

Chronic wounds need to be modelled however the needs for such models should be examined in order that the outcome permits advances in our thinking as well in clinical management.

In this talk I will look at a definition of the energy-momentum for the dynamical horizon of a black hole. The talk will begin by examining the role of a special class of observers at null infinity determined by Bramson's concept of frame alignment. It is shown how this is given in terms of asymptotically constant spinor fields and how this framework may be used together with the Nester-Witten two form to give a definition of the Bondi mass at null infinity.

After reviewing Ashtekar's concept of an isolated horizon we will look at the propagation of spinor fields and show how to introduce spinor fields for the horizon which play the role of the asymptotically constant spinor fields at null infinity, giving a concept of alignment of frames on the horizon. It turns out that the equations satisfied by these spinor fields give precisely the Dougan-Mason holomorphic condition on the cross sections of the horizon, together with a simple propagation equation along the generators. When combined with the Nester-Witten 2-form these equations give a quasi-local definition of the mass and momentum of the black hole, as well as a formula for the flux across the horizon. These ideas are then generalised to the case of a dynamical horizon and the results compared to those obtained by Ashtekar as well as to the known answers for a number of exact solutions.