Seminars 2005

Title: SYSTEMS OF POLYNOMIAL INEQUALI SYSTEMS OF POLYNOMIAL INEQUALITIES OVER QUADRATIC MAPS : TIES OVER QUADRATIC MAPS : COMPLEXITY, ALGORITHMS, APPLICATIONS
Speaker: Dr Dmitrii V. Pasechnik
Date:25 October 2005
Time: 3.00pm – 4.00pm
Venue: NIE 5-01-04 (Executive Seminar Room)
Abstract: A semialgebraic set (i.e. the union of solutions of a finite number of systems of polynomial inequalities) S is said to be defined over a map Q if S is given by a formula of the form F(Q(X)), where Q : Rn→ R k is a polynomial map and F(Y) is a quantifier-free Boolean formula with polynomial inequalities (with polynomials of degree at most d belonging to a subset of R[Y] of size s) as atoms.

We concentrate on a nontrivial and important for applications case when Q is quadratic. We show that the behaviour of S differs rather drastically from the behaviour of a general n-variate semialgebraic set given by degree d polynomials. For instance, the sum of the Betti numbers of S is bounded by (sdn)O(k) , and a similar bound holds for the complexity of sampling in S (i.e. computing representatives of the connected components of S).

Important applications of our results are, for instance:
1) A polynomial-time algorithm for the extended trust-region problem (a problem of minimising a quadratic function subject to a fixed number k of quadratic constraints)
2) The best known complexity bound for solving semidefinite programming problems exactly. 

 

Title: Statistical solutions : Debiased estimates for rate of, and prognostic effects on, progression to cirrhosis for Hepatitis C-infected individuals-when analysis is based on Hepatitis C-infected patients referred to liver clinics
Speaker: Dr Bo Fu
Date:12 October 2005
Time: 10.30am - 11.30am 
Venue: NIE 5-01-04 (Executive Seminar Room)
Host:Professor Ling San
Abstract: We will discuss the statistical solutions to estimating biases for rate of, and prognostic effects on, progression to cirrhosis for Hepatitis C (HCV)-infected individuals when analysis is restricted to Hepatitis C-infected patients referred to liver clinic. Referral to liver clinics is increasingly likely the closer the patient is to development of cirrhosis. Thus liver clinic studies will surely over-estimate the progression rate. We have designed stimulation experiments to illustrate the sort of referral bias patterns and have investigated the effect of referral bias on regression coefficients in both the accelerate (AL) failure time model and the proportional hazard (PH) model. As we anticipated, prognostic effects on HCV progression will be under-estimated. This simulation design was informed by preliminary analyses of two liver clinic HCV cohorts from Edinburgh and Cambridge, UK. We also used the stimulated clinic cohort data to investigate the performances of the proposed debiassing methods: left truncation; incorporation of frailty; and finally, reweighting, which reweights the likelihood by the inverse of probability that a subject in population would be selected to clinic.

 

Title: Theoretical investigations of interfacial effects in nanoscale structures
Speaker: Miss Quek Su Ying
Date:19 August 2005
Time: 11.00am - 12.00pm 
Venue: SBS-01n-28
Host:Professor Ling San
Abstract: Nanoscale structures such as supported ultrathin oxide films are of interest in a number of technological applications. On the other hand, oxide-supported metal nanostructures are also of interest, as catalysts, for example. In this work, we show that ultrathin transition metal oxides exhibit remarkable flexibility and can distort to fit the substrate on which the oxide is grown. This distortion gives rise to novel structures and properties distinct from those of bulk oxides. Moreover, when ultrathin oxides are in turn used as supports for ultrathin metal catalysts, the buried metal/oxide interface can distort in response to adsorbates on the metal, thereby stabilizing adsorption. This suggests that more effective oxide-supported metal catalysts can be designed by replacing traditional oxide supports with ultrathin oxide films.

 

Title: The Parametric Complexity of Fundamental Problems in Coding Theory 
Speaker: Dr Rodney Graham Downey 
Date:2 August 2005
Time: 3pm - 4pm 
Venue: NIE7-B1-10
Host:Dr Wu Guohua 
Abstract: In this talk, Dr Rod Downey will analyze the computational complexity of some problems in coding theory. The first results in this area were obtained by Berlekamp, McEliece and van Tilborg in 1978. They proved that maximum likelihood decoding and computing the weight distribution for k-dimensional linear code of length n are NP hard problems. Recently a new problem classification from the point of view of computational complexity was introduced by Downey and Fellows. For the classical approach the complexity is estimated as a function of the total length of input only. The new approach takes into account other measurements of the input. The asymptotic complexity is computed as a function of a few arguments; some arguments are considered as parameters. The problem can be intractable or tractable depending on some parameter value. Downey and Fellows proposed the W-hierarchy of parametric complexity. They will prove that the above mentioned coding theory problems are hard for the parametric complexity class W[1] and belong to the class W[2]. Similar results are obtained for the nearest vector problem and theta series problem in the theory of integer lattices.