Conferences, Lectures and Workshops
The Department hosted the ninth annual conference: MINOS 09, 18-19 April 2009
The Department hosted the 20th POSTGRADUATE COMBINATORIAL CONFERENCE, 22-24 June 2009
Seminars
| Date | 17 March 2009 |
| Speaker | Dr. Glen Cowan - Department of Physics, Royal Holloway |
| Title | Machine Learning techniques in High Energy Physics |
| Abstract | Particle physicists recently began a new era of research with the start-up of the Large Hadron Collider (LHC) in Geneva. Over the next 10 years or more, this particle accelerator will collide beams of high energy protons and hopefully reveal phenomena that go beyond our current Standard Model of particle physics. Almost 1016 collisions or "events" per year will be produced, only a tiny fraction of which are of interest as indicators of new phenomena. Over the last 10 to 20 years, particle physicists have increasingly turned to multivariate statistical methods to distinguish the interesting events (signal) from the rest (background). Linear discriminant methods and neural networks have been widely used, and a number of modern methods such as support vector machines and boosted decision trees are also attracting attention. Some applications of these methods will be described and difficulties of multivariate analyses that are particular to particle physics will be discussed. |
| Date | 18 March 2009 |
| Speaker | Mr. Matthias Mnich - Eindhoven University |
| Title | Algebraic Techniques for Exact Algorithms for NP-hard Problems |
| Abstract | The design of exact algorithms for NP-hard problems is an area of research
that gained a lot of momentum in the last few years. Recently, the portfolio
of algorithm design tools has been extended by the algebraic technique of
"fast subset convolution". It is based on convoluting the zeta transforms of
two functions over a ring, the result of which is inverted via the Moebius
transform. Fast subset convolution yielded dramatic improvements in
running time
for many a combinatorial problem, including Steiner Tree, k-Colouring and
various
partitioning problems. All these problems satisfy a recurrence relation,
where
the optimal value of the problem is a linear function of optimal values of
sub-problems. In this talk we first give an introduction to fast subset convolution, and then extend the approach to problems where the optimal value is non-linear. In particular, we solve some consensus tree problems in time O*(2^n), as opposed to O*(3^n) which is the best known so far. |
| Date | 24 March 2009 |
| Speaker | Dr. Yuri Gurevich - Microsoft Research Seattle Joint CLRC/Computer Science Seminar |
| Title | The Church-Turing Thesis: Story and Recent Progress |
| Abstract | he Church-Turing thesis is one of the foundations of computer science. The thesis heralded the dawn of the computer revolution by enabling the construct of the universal Turing machine which led the way, at least conceptually, to the von Neumann architecture and first electronic computers. One way to state the Church-Turing thesis is as follows: A Turing Machine computes every numerical function that is computable by means of a purely mechanical procedure. It is that remarkable and a priori implausible characterization that underlies the ubiquitous applicability of digital computers. But why do we believe the thesis? Careful analysis shows that the existing arguments are insufficient. Kurt Gödel surmised that it might be possible to state axioms which embody the generally accepted properties of computability, and to prove the thesis on that basis. That is exactly what we did in a recent paper with Nachum Dershowitz of Tel Aviv University. Beyond our proof, the story of the Church-Turing thesis is fascinating and scattered in specialized and often obscure publications. I will try to do justice to that intellectual drama. |
| Date | 28 April 2009 |
| Speaker | Dr. Mark-Jan Nerderhof - Department of Computer Science, St. Andrews |
| Title | Computation of the partition function of probabilistic context-free grammers. |
| Date | 5 May 2009 |
| Speaker | Dr. Alexey Koloydenko - Department of Mathematics, RHUL |
| Title | Statistical Models for Diffusion Weighted Magnetic Resonance Imaging (MRI) |
| Abstract | Diffusion weighted MRI (DMRI) has relatively recently become available for non-invasive probing of microstructure of various types of matter. The availability of this new tool has been embraced by researchers and practitioners studying structural integrity and organization of matter. In particular, white matter tractography based on DMRI attempts to integrate local charts of white matter fiber bundles in order to assess connectivity of the brain. At the core of these efforts is the ability to estimate reliably dominant fiber directions from a set of DMRI probes registered to a particular location (voxel) in the brain. I plan to consider two issues associated with the popular diffusion tensor approach to DMRI data analysis. The first one is about doing basic statistics with diffusion tensors taking into account the non-euclidian structure of their space. This theme turns out to be rather general since diffusion tensors are essentially semi-definite symmetric matrices arising also in other fields. Secondly, I plan to discuss briefly suitability of a hidden Markov random field model (HMRFM) for DMRI data. Preliminary results confirm that inference based on these new models is noticeably different from that based on the commonly used models with additive mean structure. |
| Speaker | Michael Lampis - City University of New York |
| Time | 1 June 2009 |
| Title | Directed widths from the algorithmic perspective. |
| Abstract | Treewidth is one of the most important notions in parameterized complexity, mainly due to its success in providing efficient FPT algorithms for a huge variety of graph problems. Several attempts have been made in the past to generalize treewidth and related notions to digraphs; these include directed treewidth, DAG-width, Kelly-width and directed pathwidth. In this talk we outline the known results about these widths and a related digraph parameter which arises from regular language complexity called cycle rank. We specifically focus on the algorithmic power of these widths: We demonstrate a W[2]-hardness result for Hamiltonian Cycle parameterized by any of these measures which shows that the best known algorithm for this problem cannot be significantly improved to achieve an FPT running time. We also mention several other recently published hardness results for digraph problems which are easy on DAGs but hard for digraphs of small width. Finally, directions for further research will be discussed. |
| Speaker | Valia Mitsou - City University of New York |
| Date | 2 June 2009 |
| Title | The Ferry Cover Problem |
| Abstract | In this talk we define and study a family of optimization problems called Ferry problems, which may be viewed as generalizations of the classical wolf-goat-cabbage puzzle. We present the Ferry Cover problem, where the objective is to determine the minimum required boat size to safely transport n items represented by a graph G and demonstrate a close connection with Vertex Cover which leads to hardness and approximation results. We also completely solve the problem on trees. Then we focus on a variation of the same problem with the added constraint that only 1 round-trip is allowed. We present a reduction from MAX-NAE-{3}-SAT which shows that this problem is NP-hard and APX-hard. We also provide approximation algorithms for specific graph families. Finally, we will discuss some recent results on the problem by Csorba, Hurkens and Woeginger (ESA 2008) and mention further open problems. |
| Speaker | Prof. David Wild - Warwick University |
| Date | 23 June 2009 |
| Title | TBA |
| Abstract | |
| Date | Friday 11 September 2009 |
| Speaker | Dr. Jüri Lember - University of Tartu |
| Title | On recent developments in HMM-based segmentation |
| Abstract | Hidden Markov models (HMM) are commonly used in many areas, including
signal processing, speech recognition and computational molecular
biology. Roughly, an HMM consists of an unobserved hidden Markov
chain
and its "noisy" observed counterpart. Often, the main object of
interest is the true realization of the hidden Markov chain from
observed data. Estimation of the hidden realization is also known as
segmentation. For example, speech signal can be segmented into
sentences, words, phonems etc; DNA sequences can be segmented into
coding and non-coding regions, or into CpG islands and background. A
widely used estimate of the underlying hidden path is
maximum-likelihood, or maximum a posteriori (MAP), sequence of
states,
commonly known as Viterbi alignment. A well-known alternative is
pointwise, i.e. symbol-by-symbol, maximum-likelihood, or
PMAP-alignment. This latter alignment is optimal in the sense of
minimizing the expected number of incorrectly classified components
of
the hidden sequence. However, depending on the task, the best
(optimal) alignment might be yet different from those two.
When the HMM extends to infinity, then (under certain mild
conditions)
many alignments (including Viterbi and PMAP alignments) converge,
generally to distinct limiting alignments. Viewed as proper random
processes derived from the original hidden Markov process, the
infinite limiting alignments can be used to study various asymptotic
properties of their respective segmentations.
We introduce a somehow generalized view of segmentation, and we show how the asymptotic analysis can be used for measuring and improving the goodness of segmentation. This is a joint work with Alexey Koloydenko. |
| Date | 15 September 2009 |
| Speaker | Dr. Robin Adams - Department of Computer Science, Royal Holloway |
| Title | Type Theory and Proof Checkers |
| Abstract | A type theory is a formal language which deals with statements M:A. Remarkably, the same formal language can be read in three different ways: * M is an object of type A * M is a program that satisfies the specification A * M is a proof of the proposition A This minor miracle - the fact that the same formal rules govern all three interpretations - goes by the name of the Curry-Howard Isomorphism, and is a very useful fact that is still not fully understood. In this talk, I shall give a non-technical survey the history of type theories, and explain how they are useful for building proof checkers - systems that decide whether a proof of a mathematical theorem is correct. I shall describe my own research with logic-enriched type theories, which can be seen as hybrid systems between type theory and predicate logic. |
| Date | 29 September 2009 |
| Speaker | Prof. Dr. Vladimir V. Anisimov Director, Research Statistics Unit GlaxoSmithKline |
| Title | Statistical modelling in clinical trials (patient recruitment and drug supply) |
| Abstract | A large clinical trial for testing pharmaceutical drug usually
involves hundreds of patients to be recruited by many clinical
centres. Patients recruited into the trial are randomized to prescribed
medical treatments and at some stages, their responses are
statistically analysed for taking a decision on the effectiveness of
the drug. This process requires using various statistical techniques at
different stages of the trial.
In the first part of the talk, the basic statistical problems that appear in drug development process in pharmaceutical industry are briefly described. The second part is dealing with the patient recruitment stage. This stage is very costly and affected by various uncertainties in input information, variation in clinical centres and stochastic fluctuations of the recruitment over time. A large proportion of trials fail to complete recruitment before deadline. A novel statistical methodology for modelling and predicting patient recruitment and drug supply in multicentre clinical trials is proposed. Patient's flows in different centres are viewed as delayed Poisson processes with random unknown rates. The problems of modelling, estimating and predicting with credibility bounds the number of patients over time and the recruitment time are considered. The developed technique also allows re-assessing the number of clinical centres required to complete recruitment in time with a given confidence (adaptive adjustment), predicting study/centre performance, and evaluating the amount of drug supply which is needed to cover patient demand with a given risk of undersupply. The technique has been validated for many real trials and is on the way of implementation. Illustrative examples are considered. References: V. Anisimov, V. Fedorov, Modeling, prediction and adaptive adjustment of recruitment in multicentre trials, Statistics in Medicine, 26, 27, 2007, pp. 4958-4975. V. Anisimov, Recruitment modeling and predicting in clinical trials, Pharmaceutical Outsourcing, March/April 2009, pp 1-10. |
| Date | 4 December 2009 |
| Speaker | Dr.G.Martynov, The Institute for information transmission problems of the Russian Academy of Sciences (Kharkevich Institute). |
| Title | Karunen-Loeve decompositions for weighted Wiener process and for Brown bridge with applications to the goodness-of fit tests |
| Abstract | We will consider the Wiener process and Brown bridge with the weight fuction t^\alpha. The decomposition of weighted processes was fulfilled with usig of Bessel functions. It was found the eigen values and eigen fuctions for the Fredholm operator with the corresponding covariance functions as kernel. These results have the applications to the Kramer- von Mises goodness of fit test. The results were found in cooperation with P.Deheuvels (University Paris VI). |
Last updated
15 July 2010
/ JH
•
•
Department of Computer Science,
University of London,
Egham,
Surrey TW20 0EX
Tel/Fax : +44 (0)1784 443421 /439786
Tel/Fax : +44 (0)1784 443421 /439786