Seminars and Events Programme

Seminars take place on Tuesdays from 1300-1400, unless otherwise stated.
Tea and coffee are served after the seminars in Room 115, McCrea Building.
All are welcome.

How to find us

Other seminar series of interest

MINOS 2011

• 9-10 April 2011
  The Department of Computer Science hosts the eleventh weekend conference on micromouse design, including wall-following and full maze-solving competitions.

Forthcoming seminars 2011

• Monday 11 April 2011, 1300, Room 229, McCrea Building
  Dr Matthias Mnich, International Computer Science Institute, Berkeley

  Domination When the Stars Are Out

  We algorithmize the recent structural characterization for claw-free graphs by Chudnovsky and Seymour. Building on this result, we show that Dominating Set on claw-free graphs is (i) fixed-parameter tractable and (ii) even possesses a polynomial kernel. To complement these results, we establish that Dominating Set is not fixed-parameter tractable on the slightly larger class of graphs that exclude K_{1,4} as an induced subgraph. Our results provide a dichotomy for Dominating Set in K_{1,L}-free graphs and show that the problem is fixed-parameter tractable if and only if L ≤ 3. Finally, we show that our algorithmization can also be used to show that the related Connected Dominating Set problem is fixed-parameter tractable on claw-free graphs.
  (Joint work with Danny Hermelin, Erik Jan van Leeuwen and Gerhard Woeginger)

Recent seminars

• 23 March 2011 Prof Ming Chen, Zhejiang University, People's Republic of China

  The computational analysis of micro-RNA's using next generation sequencing data in plants

• 22 March 2011 Prof Michael Fellows, Charles Darwin University, Australia

  Parameters for fun and profit! Some new developments in parameter ecology

  The talk will motivate the research program in parameterized complexity and algorithmics that has loosely become known as "parameter ecology". What is generally going on is that as the field advances, we are becoming ever-more adept at rich parameterizations of NP-hard problems.
  There are good practical reasons to explore such things. The mathematical techniques required are often fresh and interesting. Some recent results that are leading this area forward will be surveyed.

• 15 March 2011 Prof Rajeev Raman, University of Leicester

  Random Access to Grammar-Compressed Strings and Trees

  Modern applications involving processing textual and semi-structured data need to do fairly complex computations on data held in the main memory of a computer, which is a limited resource in many contexts. While data compression can reduce the size of data, it presents significant obstacles to operating on the compressed data, and new data structuring techniques need to be developed to overcome these obstacles. After an introduction to the issues, we will focus on one particular recent result.
  Let S be a string of length N compressed into a context- free grammar S of size n. We present a representation of S achieving O(log N) random access time, and O(n) construction time and space on the RAM. We are able to generalize our results to navigation and other operations on grammar-compressed trees. To achieve these bounds, we introduce several new techniques and data structures of independent interest, including a predecessor data structure, two "biased" weighted ancestor data structures, and a compact representation of heavy-paths in grammars.
  [Although this will be summarizing some other papers, the main result above is joint with Bille, Landau, Satti, Sadakane and Weimann and some parts of this paper were presented at the ACM-SIAM SODA 2011.]
  Rajeev Raman, http://www.cs.le.ac.uk/~rraman

• Inaugural Lecture 10 March 2011 Professor Adrian Johnstone, Department of Computer Science, Royal Holloway, University of London

  The Language of Mechanism

  This lecture looks at the transition from visual to textual design in systems engineering, and gives an overview of new developments in language analysis that provide both greater flexibility and greater precision in the process of interpreting a design, be it software or a complete digital electronic system.

• 9 March 2011 Dr Joseph Reddington, Department of Computer Science, Royal Holloway, University of London

  Software Engineering the novel

  Last year, a group of undergraduate students at Royal Holloway College used computer science techniques to collectively write a 60,000 word novel, "The Shadow Hours", in seven days. Later, a second group produced a more complex novel "The Delivery", of the same length, in five and a half days. Of particular interest was the development of the volunteers. They were involved in the full workflow of novel writing from inception and structure to proofing and choosing a cover illustration, and this greatly increased their investment and focus on the work. The environment allowed great progress in both their subject skills of structuring, characterisation, and word choice, but also the softer skills of teamwork, communication, and feedback. Project TooManyCooks won Royal Holloway's Team Teaching Prize this summer and has attracted various small amounts of commercialisation and outreach funding. This talk is particularly intended for students and staff with an interest computer science, education, or creative writing. Works by Dan Brown, Stephanie Meyer and JK Rowling pop up as examples - familiarity isn't required but the talk will definitely spoil some plot twists.

• 8 March 2011 Dr Jason Crampton, Information Security Group, Department of Mathematics, Royal Holloway, University of London

  Practical constructions for the efficient cryptographic enforcement of interval-based access control policies

  The enforcement of access control policies using cryptography has received considerable attention in recent years. Such enforcement schemes vary in the amount of storage and the number of key derivation steps that are required in the worst case. These parameters correspond, respectively, to the number of edges and the diameter of some graph that is used to represent the access control policy. In this talk we will consider a particular class of access control policies and the associated graphs. We then present a number of techniques for constructing a new graph that has a smaller diameter than the original graph but enforces the same access control policy.

• 4 March 2011 Dr Zakria Hussain, Department of Computer Science, University College London

  Conditional Generalisation Error Bounds using Inductive Conformal Predictors

  We use the ideas from the Inductive Conformal Predictor (ICP) framework to construct generalisation error bounds for classification. We show how we can fuse together d>1 different nonconformity measures to construct "p-values", and use sample compression bounds in order to bound the loss of falling into a specific region constructed by these d-dimensional p-values. Hence, after fixing the calibration set we can prove upper bounds on the loss of test points, once they fall into a predefined region. Given time, we will also show an approach to using nonconformity measures for model selection using, for instance, the SVM.

• 3 March 2011 Dr Shawn Douglas, Wyss Institute, Harvard University

  What to make with DNA origami

  The programmability of DNA makes it an attractive material for constructing intricate nanoscale shapes. The DNA origami method, in which a multiple-kilobase single-stranded "scaffold" is folded into a custom shape by interaction with hundreds of short oligonucleotide "staple" strands has proved to be extremely versatile for creating custom two- and three-dimensional shapes. The next challenge we aim to address is to apply our nanoscale building techniques to create tools and devices with demand-meeting applications. This talk will describe preliminary steps we've taken to develop a therapeutic nanostructure with selective targeting capability, as well as new CAD software tools to aid in future design efforts.

• 1 March 2011 Dr Colin Walter, Information Security Group, Department of Mathematics, Royal Holloway, University of London

  Dual addition chains and their application to exponentiation in different directions

  Location-aware addition chains are used to determine schemes for exponentiation in resource-constrained devices. A dual will be constructed for such addition chains. This reverses the order of an addition chain, and thereby provides a duality between left-to-right and right-to-left exponentiation schemes which preserves space requirements. The duality extends a previously known transformation between such schemes that preserves the time cost. All the usual algorithms for exponentiation have duals in the opposite direction. In particular, Yao's right-to-left scheme is derived as the dual of the normal table-based left-to-right m-ary scheme with an explicit pairing of registers between the two algorithms, and a new multi-base algorithm is obtained by taking the dual of the right-to-left division chain method.

• 1 February 2011 Dr Alex Clark, Department of Computer Science, Royal Holloway, University of London

  Exact Query Learning of Some Context Free Languages

  In many situations, we are interested in modeling sequence data: typically by constructing a representation of a formal language from a sequence of examples. For example in understanding how children might acquire their first language, we need to understand how richly structured representations can be constructed for languages that exhibit the sorts of structural dependencies typical of natural languages. Until quite recently, there were almost no algorithms for doing this except in the case where the languages are regular. In this talk, we will discuss recent algorithms which can model non-regular and indeed non context free languages. These approaches are based on distributional learning which models the relationship between contexts and substrings in a language. We will then present a simple algorithm for learning a class of context free grammars using Angluin's minimally adequate teacher model of exact query learning.

• 25 January 2011 Dr Igor Razgon, University of Leicester

  Parameterization of graph separation problems: current results and further challenges

  Fixed-parameter computation is a methodology of coping with NP-hardness that, under certain conditions, allows to solve hard optimization problems both precisely and efficiency. According to this methodology, a problem is associated with a parameter $k$ and solved by an exponential time algorithm whose exponential part solely depends on the parameter while dependnency on the input size $n$ is uniformly polynomial, i.e. the degree of the polynomial is a constant, usually not greater than 3. When the parameter is small, we get a low-polynomial algorithm solving an NP-hard problem to optimality. Problems that can be solved in this way are called fixed-parameter tractable (FPT). The parameter choice depends on the particular application and can be, for example, maximum or minimum allowed size of the output or some structural measure of the input, e.g. treewidth.
  This talk is related to parameterization of graph separation problems where the task is to find the smallest set of vertices separating some predefined pairs of terminals, possibly under additional constraints. In the first part of this talk, I will informally define a fixed-parameter algorithm and describe two fixed-parameter algorithms for the Vertex Cover problem. In the second part of the talk I will describe an algorithm for solving the multiway cut problem and show how the main idea of this algorithm has helped to show the fixed-parameter tractability of such challenging graph separation problems as Directed Feedback Vertex Set, minimum 2CNF deletion, and Multicut. In the final part of the talk I will outline the current challenges related to the parameterization of graph separation problems. The main challenge is kernelization of these problems, i.e. designing a polynomial-time procedure that squeezes the initial instance of the problem so that its size polynomially depends on the parameter. Such procedure being applied at the preprocessing stage can significantly enhance any algorithm solving the given problem and hence understanding kernelizability of parameterized problems is a research direction of a great practical importance.
  The talk is self-contained and assumes no prior familiarity with the area.

• 21 January 2011 Richard McEvoy, Information Security Group, Department of Mathematics, Royal Holloway, University of London

  PDF of seminar

  (Almost) 20/20 Foresight - A Predicted Model for Advanced Persistent Threats in Industrial Process Control Systems

  Stuxnet and similar threats are a visibly new trend in Information Security threats, in particular, threats to the critical infrastructure of nation-states. But the approach and techniques utilised -- including probable attack motivations -- have been predicted by researchers working in intrusion detection over the past decade. This seminar presents a predicted (and predictive) model for advanced persistent threats in SCADA and DCS (aka process control) networks and shows how closely Stuxnet fits to the predicted pattern. Further aspects of the model are explored. In addition, the seminar also touches on research efforts to detect, prevent and intervene in such attacks.

• 18 January 2011 Professor Simon Blackburn, Department of Mathematics, Royal Holloway, University of London

  $k$-radius sequences

  A $k$-radius sequence is a finite sequence over an alphabet of size $n$, with the property that every two alphabet symbols occur within a distance of $k$ of each other somewhere in the sequence. We write $f_k(n)$ for the shortest $n$-ary $k$-radius sequence. Jaromczyk and Lonc introduced this concept in 2004: they were interested in designing a (first-in first-out) caching strategy for computations involving pairs of large data objects such as medical images.
  In this talk, I will start by talking a little about the caching application. I'll then show how to prove that $f_k(n)$ grows like
  \[
  \frac{1}{k} \binom{n}{2}
  \]
  when $k$ is fixed and $n\rightarrow\infty$.
  This talk is based on the following papers:
  S.R. Blackburn, 'The existence of k-radius sequences'. See http://arxiv.org/abs/1101.1172
  S.R. Blackburn and J.F. McKee, 'Constructing k-radius sequences', Mathematics of Computation, to appear. See http://arxiv.org/abs/1006.5812
  Joint work with James McKee.

• 7 December 2010 Dr Jackie Daykin, Royal Holloway, University of London (et al)
  

  Combinatorics and algorithmics of UMFFs

  A string or word over an alphabet is a Lyndon word if it is the least in lexicographic order amongst the set of its rotations. In 1958, Chen, Fox and Lyndon showed that any given string can be uniquely factored, that is partitioned into substrings, over the set of Lyndon words. Hence Lyndon words form an UMFF "unique maximal factorization family". In 1983, Duval designed an elegant factorization algorithm for Lyndon decomposition in linear time. Subsequently, a wide range of applications of this string decomposition have arisen, both in theory and practice.
  In this talk we describe generalizations of Lyndon structures. First we introduce Hybrid Lyndon words, which are defined using the lexicographic method together with a distinct total order applied to substrings. Next we define sets of strings known as circ-UMFFs, over which every string can be uniquely factored, a special case of these sets being Lyndon words.
  Commencing with structural properties of circ-UMFFs, we establish patterns of order for string concatenation and the reciprocal operation of factorization. We introduce Type Flight Deck, Type Acrobat and some binary circ-UMFFs. Hybrid Lyndons are illustrated with lexicographic order together with V-order, which yields the V-word circ-UMFF. Combinatorial results on V-words lead to a linear V-word factorization algorithm, which is derived from the framework of Duvalâ's Lyndon algorithm. It will also be shown how to parallelize these factorization algorithms under the PRAM model.
  This work is joint with W.F. Smyth and D.E. Daykin.

• 7 December 2010 Dr Tamas Nepusz, Royal Holloway, University of London
  

  Denoising protein-protein interaction networks with random graph models

  One of the most important challenges of the post-genomic era is to understand the complex networks of protein-protein interactions (PPIs). In these networks, each vertex represents a protein, and pairs of vertices are connected by an edge if the corresponding proteins interacted with each other in some experiment. Such networks are usually used to draw further inferences about cellular processes; for instance, it was shown that dense regions in a protein interaction network often correspond to protein complexes. However, PPI experiments are usually noisy, with false positive and false negative rates reaching 60-70%. Therefore it is of primary importance to enhance the quality of PPI datasets by computational methods. My talk will present how random graph models such as stochastic blockmodels and hierarchical random graphs can be used to pinpoint false positives and false negatives in protein interaction datasets and to predict novel interactions in PPI networks.

• 30 November 2010 Dr David Barber, University College London
  

  Variational Methods for Approximate Inference

  Structured probabilistic models are widespread in statistics, machine learning and related subjects.  Such models are popular due their ease of construction and ability to incorporate of domain knowledge. However, these models often result in computational intractabilities. In this talk I will give an overview of variational methods, as applied to probabilistic modelling,  and discuss approximate inference applications thereof to some simple models, including generalised linear models. If time permits I will also discuss how to address solving Markov Decision Processes and Reinforcement Learning from a variational inference perspective.

• 23 November 2010 Dr Daniel Paulusma, University of Durham
  

  On coloring graphs without induced forests

  The l-Coloring problem is the problem to decide whether a graph can be colored with at most l colors. The Vertex Coloring problem is the problem to determine the chromatic number of a graph. We study the computational complexity of these two problems for graph classes characterized by one or two forbidden induced subgraphs.
  A graph G is H-free if G contains no induced subgraph isomorphic to H. In particular, we study the case when H is a linear forest (disjoint union of a collection of paths) of small size. Our results combined with known results lead to the following two theorems:

  1. Let H be a fixed graph on at most 6 vertices. Then 3-Coloring for H-free graphs is polynomial-time solvable if H is a linear forest; otherwise it is NP-complete.
  2. Let H be a fixed graph on at most 6 vertices. Then Vertex Coloring for triangle-free H-free graphs is polynomial-time solvable if H is a forest not equal to the six-vertex star; otherwise it is NP-hard.
  In addition, we present an updated overview on the l-Coloring problem for P_k-free graphs, where P_k denotes the path on k vertices. The computational complexity of this problem depends on the (fixed) values of k and l, and a full complexity classification is still open.
  Joint work with: Hajo Broersma, Petr Golovach and Jian Song.

• 16 November 2010 Professor John Shawe-Taylor, University College, London
  

  PAC-Bayes analysis and data distribution dependent priors

  A short review of the application of PAC-Bayes analysis to SVMs will be given highlighting the cost of the KL divergence term. We then present methods for controlling this term. The simplest approach is that of 'learning the prior' with part of the data. Catoni introduced a more sophisticated 'localised analysis'. We review this work and show more recent extensions of these ideas with an emphasis on their application to SVMs.

• 2 November 2010 Professor Marek Sergot, Department of Computing, Imperial College London
  

  Norms, action and agency in distributed multi-agent systems

  An idea that has been around for some time is that complex interactions between multiple, independently acting agents (or system components) can be managed without centralised control by formulating norms (or `social laws') which, if respected, allow the agents to co-exist in a shared environment. It is difficult to find any concrete examples in the literature however. The question of what happens to system behaviour when `social laws' are not respected, moreover, has received little or no serious attention.
  I will present some simple experiments to construct norm-regulated systems of this kind, and a formal (modal-logical) language for specifying and analysing them. The emphasis will be on motivation and illustrative examples rather than technical details. Several different categories of non-compliant behaviour can be characterised and classified: there are various forms of unavoidable or inadvertent non-compliance, behaviour where an agent does `the best that it can' to comply with its individual norms but nevertheless fails because of the actions of other agents, and behaviour where an agent could have complied with its individual norms but did not. The formal language is termed `a logic of unwitting collective agency' --- `agency' because the focus is on the consequences of actions and the agents responsible for them, and `unwitting' because no assumptions are made at all about the reasoning or perceptual capabilities of the agents. They could be deliberative agents, simple reactive devices, or components of a computer system.

• 26 October 2010 Professor Leszek Gasieniec, University of Liverpool
  

  Location aware asynchronous rendezvous in discrete 2D-spaces

  We discuss efficient rendezvous of two anonymous robots located in a discrete Euclidean 2D-space represented by an infinite 2D-grid with integer coordinates. We assume that each robot knows its own initial location. The robots, however, are not aware of positions of one another. This model is equivalent to a standard geometric model in which the robots possess: coherent compasses, the same unit of length, and a limited visibility allowing them to encounter one another at a fixed range.
  We present an efficient explicit construction of "space-covering sequences" embedded into a discrete 2D-space, a novel concept that allows two robots located at a distance of d to meet after adopting a trajectory of a length of $O(d^{2+e})$, for any constant e > 0. Further, we provide an improvement that leads to an almost optimal asynchronous rendezvous of length $O(d^2 \log^7 d)$. Finally, we show how to adopt our rendezvous methods to efficient gathering of a larger number of robots and we provide a list of related open problems.
  Joint work with: Evangelos Bampas, Andrew Collins, Jurek Czyzowicz, David Ilcinkas, and Arnaud Labourel.

• 21 October 2010 Dr Thorsten Altenkirch, School of Computer Science, University of Nottingham
  

  Higher Order Container

  Containers are a semantic way to talk about strictly positive types. In previous work it was shown that containers are closed under various constructions including products, coproducts, initial algebras and terminal coalgebras. In the present talk we discuss our recent result that, surprisingly, the category of containers is cartesian closed, giving rise to a full cartesian closed subcategory of endofunctors. The result has interesting applications in generic programming and representation of higher order abstract syntax and seems to be related to the de Paiva's dialectica category. We also show that the category of containers has finite limits, but it is not locally cartesian closed.
  (based in joint work with Sam Staton and Paul Levy)

• 28 Sept 2010 Professor Gregory Gutin, Royal Holloway, University of London

  Complexity of Permutation Constraint Satisfaction Problems Parameterized Above Average

  In the Max Acyclic Subdigraph problem we are given a digraph D and ask whether D contains an acyclic subdigraph with at least k arcs. The problem is NP-complete and it is easy to see that the problem is fixed-parameter tractable, i.e., there is an algorithm of running time f(k)n^{O(1)} for solving the problem, where f is a computable function of k only and n=|V(D)|. The last result follows from the fact that the average number of arcs in an acyclic subdigraph of D is m/2, where m is the number of arcs in D. Thus, it is natural to ask another question: does D have an acyclic subdigraph with at least m/2 + k arcs? It was an open problem [Mahajan, Raman and Sikdar (2006, 2009)] to establish parameterized complexity of this problem and we can show that the problem is fixed-parameter tractable and has a quadratic kernel.
  In fact, the Max Acyclic Subdigraph problem is the only nontrivial binary Permutatation CSP parameterized above average. There are 62 nontrivial ternary Permutation CSPs parameterized above average and we can show that all of them are fixed-parameter tractable and have kernels with quadratic number of variables. The 62 problems include Betweenness parameterized above average whose complexity was stated as an open problem in the 2006 book by Niedermeier (where it is attributed to Benny Chor).
  These results were obtained in joint papers with L. van Iersel, E.J. Kim, M. Mnich, S. Szeider, and A. Yeo. The tools we use include probabilistic inequalities and Hypercontractive Inequality.

• 23 July 2010 Dr Liu Yuan, Beijing Genomics Institute (BGI)

  Overview of the research at BGI

• 22 July 2010 Aleksandra Skirycz, Department of Plant Systems Biology, Flanders Institute for Biotechnology, Ghent University

  More from less - plant growth under limited water

  When subjected to abiotic stresses, plants actively re-program their growth by modulating cell division and cell expansion. Growth decreases rapidly upon stress onset but it recovers and adapts once stress conditions become stable. The aim of the presented work is to decipher the molecular mechanisms underlying both short-term growth inhibition and long-term growth adaptation of Arabidopsis leaves subjected to osmotic and drought stresses. Using transcript and metabolite profiling we could show that the response to prolonged osmotic stress strongly depends on the leaf developmental stage (Skirycz at al., 2010). At the hormone level ethylene and DELLA signaling appear crucial for acquiring stress tolerance but also for growth inhibition. In support ethylene insensitive mutants succumb to prolonged stress treatment but their growth is less affected by short-term stress. In proliferating leaves activation of ethylene signaling occurs rapidly after stress onset followed by reduction of cell division rates that can be mimicked by addition of the ethylene precursor ACC. Our working hypothesis on how ethylene and DELLA signaling regulate cell cycle activity upon environmental stress will be presented.

• 13 July 2010 Valia Mitsou (CUNY, New York)

  Parameterized Modal Satisfiability

  We investigate the parameterized computational complexity of the satisfiability problem for modal logic and attempt to pinpoint relevant structural parameters which cause the problem's combinatorial explosion, beyond the number of propositional variables $v$. To this end we study the modality depth, a natural measure which has appeared in the literature, and show that, even though modal satisfiability parameterized by $v$ and the modality depth is FPT, the running time's dependence on the parameters is a tower of exponentials (unless P=NP). To overcome this limitation we propose possible alternative parameters, namely diamond dimension and modal width. We show fixed-parameter tractability results using these measures where the exponential dependence on the parameters is much milder (doubly and singly exponential respectively) than in the case of modality depth thus leading to FPT algorithms for modal satisfiability with much more reasonable running times. We also give lower bound arguments which prove that our algorithms cannot be improved significantly unless the Exponential Time Hypothesis fails.

• 13 July 2010 Michael Lampis (CUNY, New York)

  Algorithmic Metatheorems for Restrictions of Treewidth

  Possibly the most famous algorithmic meta-theorem is Courcelle's theorem, which states that all MSO-expressible graph properties are decidable in linear time for graphs of bounded treewidth. Unfortunately, the running time's dependence on the formula describing the problem is in general a tower of exponentials of of unbounded height, and there exist lower bounds proving that this cannot be improved even if we restrict ourselves to deciding FO logic on trees. We investigate whether this parameter dependence can be improved by focusing on two proper subclasses of the class of bounded treewidth graphs: graphs of bounded vertex cover and graphs of bounded max-leaf number. We prove stronger algorithmic meta-theorems for these more restricted classes of graphs. More specifically, we show it is possible to decide any FO property in both of these classes with a singly exponential parameter dependence and that it is possible to decide MSO logic on graphs of bounded vertex cover with a doubly exponential parameter dependence. We also prove lower bound results which show that our upper bounds cannot be improved significantly, under widely believed complexity assumptions. Our work addresses an open problem posed by Michael Fellows.

• 2 July 2010 Mark Gerstein, Yale University

  Analysis of Molecular Networks

  My talk will be concerned with understanding protein function on a genomic scale. My lab approaches this through the prediction and analysis of biological networks, focusing on protein-protein interaction and transcription-factor-target ones. I will describe how these networks can be determined through integration of many genomic features and how they can be analyzed in terms of various topological statistics. In particular, I will discuss a number of recent analyses: (1) Improving the prediction of molecular networks through systematic training-set expansion; (2) Showing how the analysis of pathways across environments potentially allows them to act as biosensors; (3a) Analyzing the structure of the regulatory network indicates that it has a hierarchical layout with the "middle-managers" acting as information bottlenecks; (3b) Showing these middle managers tend be arranged in various "partnership" structures giving the hierarchy a "democratic character"; (4) Showing that most human variation occurs at the periphery of the protein interaction network; (5) Comparing the topology and variation of the regulatory network to the call graph of a computer operating system; and (6) Developing useful web-based tools for the analysis of networks (TopNet and tYNA).

• 24 June 2010 Dr Paul Davies, Thales UK

  The De-interleaving problem

  The talk will explain the concept of radar interception de-interleaving, and the history of current approaches. It can be considered as the separation of multiple time-interleaved window functions with multidimensional parameters, into their constituent source descriptors. The talk will discuss several problems associated with the current approaches. Ideas for novel methods in treating the problem will be solicited and debated.

• 4 May 2010 Artur Czumaj, University of Warwick

  Sublinear-time algorithms for testing graph properties

  The design of algorithms operating on massive data sets, has received a lot of attention in recent years. The practical motivation of this study is that polynomial algorithms that are efficient in relatively small inputs, may become impractical for input sizes of several gigabytes. Managing and analyzing such data sets forces us to revisit the traditional notions of efficient algorithms. Constructing a sublinear time algorithm may seem to be an impossible task since it allows one to read only a small fraction of the input. However, in recent years, we have seen development of sublinear time algorithms for optimization problems arising in such diverse areas as graph theory, geometry, algebraic computations, and computer graphics. In this talk, we will present a few examples of sublinear algorithms for problems on graphs. Our main focus will be on sublinear-time algorithms to approximately test basic graph parameters (e.g., for testing if a graph is bipartite or is "far" from being bipartite, is a tree, is an expander, etc).

• 17 May 2010 Laszlo Gyorfi, Budapest University of Technology and Economics

  Portfolio Games, including Kelly games, Horse-racing and St Petersburgh games

• 23 February 2010 Dave Cohen, RHUL

  How hard is optimisation?

  The Constraint Satisfaction Problem (CSP) is concerned with the feasibility of satisfying a collection of constraints. The CSP paradigm has proven to be useful in many practical applications. In a CSP instance a set of variables must be assigned values from some domain. The values allowed for certain (ordered) subsets of the variables are restricted by constraint relations. The general CSP is NP-hard. However there has been considerable success in identifying tractable fragments of the CSP. In particular, the tractability of the CSP fragments obtained by limiting the allowed set of constraint relations is characterised by an algebraic property: the clone of polymorphisms. The extension of this framework, called the Valued CSP (VCSP), which allows optimisation, is now also being investigated. In this extended framework, for some ordered subsets of the variables, each possible tuple is given a (possibly infinite) desirability weighting, or cost. The goal is to find the most desirable (or least cost) total assignment. We have replaced constraint relations, which define feasible tuples, with cost functions, which give desirability values to tuples. In this talk we will show that, when the costs are rational numbers or infinite, the complexity of the VCSP fragments obtained by limiting the cost functions is determined by certain algebraic properties: feasibility polymorphisms and fractional polymorphisms. As an immediate application of these results, we show that the existence of a non-trivial fractional polymorphism is a necessary condition for tractability (assuming P != NP).

• 2 March 2010 Alexey Chernov, RHUL

  Multiobjective prediction with expert advice?

  Prediction with Expert Advice is a popular model for sequence prediction. At each step, Experts give their predictions, then Learner gives his prediction that may depend on Experts' opinions, and then the outcome is revealed. The difference between predictions and outcomes is evaluated by some loss function. Learner's goal is to keep his accumulated loss small compared to the accumulated losses of each Expert. We consider a new framework, where the quality of predictions is evaluated not by a single loss function but by a (finite) set of them. Accordingly, Learner has a set of losses, and his new goal is to keep all his losses small. We construct a strategy for Learner that achieves this goal if the loss functions are mixable and proper. This is a joint work with Volodya Vovk.

• 16 March 2010 Richard Morris, John Innes Centre

  Biological information processing: Unravelling the control logic of the floral transition

  I will present the computational approaches (network modeling, parameter space sampling, machine learning) we developed to model flowering time. The floral transition involves the switch from vegetative to reproductive growth and is an important adaptive trait in plants. After the floral transition, groups of cells on the flanks of the shoot apex (primordia) are specified to form flowers instead of leaves. Arabidopsis thaliana integrates environmental and endogenous signals to determine the correct timing of flowering. Once initiated, the floral transition is rapid and irreversible on the flanks of the shoot, while nearby cells in the centre of the shoot are maintained in an undifferentiated state to support future meristematic growth. The regulatory logic that enables simultaneous irreversible switching in floral primordia and the maintenance of undifferentiated cells in the shoot is not understood. We have developed a mathematical model that captures important features of the floral transition with which we can quantitatively account for all known mutants. The model makes valuable predictions for novel genotypes that have recently been validated and explains a known phenotype that was described many years ago but was poorly understand.

Other seminar series of interest:

• Information Security Group
  
• Department of Mathematics
  
• Department of Physics
  
• School of Biological Sciences
  
• Gatsby Institute, UCL
  
• Imperial College Bioinformatics Seminars