Computer Science Colloquia
Print versionWelcome to the Colloquia Website
Colloquia take place on Monday afternoons in Room S3.31. If you are coming from outside the College, please call Nir Oren (+44 20 7848 1967) for confirmation of details.
Next colloquium
Wednesday 25 November, 15.00, Room K4.31
Daniel Paulusma, Durham University
Title: Fast exact algorithms for hamiltonicity in claw-free graphs
Abstract: The Hamiltonian Cycle problem asks if an n-vertex graph G has a cycle passing through all vertices of G. This problem is a classic NP-complete problem. So far, finding an exact algorithm that solves it in O*(a^n) time for some constant a<2 is a notorious open problem. For a claw-free graph G, finding a hamiltonian cycle is equivalent to finding a closed trail (eulerian subgraph) that dominates the edges of some associated graph H. Using this translation we obtain two exact algorithms that solve the Hamiltonian Cycle problem for the class of claw-free graphs: one algorithm that uses O*(1.6818^n) time and exponential space and one algorithm that uses O*(1.8878^n) time and polynomial space.
Monday 23 November, 12.00, Room S3.31
Kostas Stathis, Royal Holloway, University of London
Title: Distributed Agent Environments in the Ambient Event Calculus
Abstract: We study the development of distributed agent environments as distributed event-based systems specified in the Ambient Event Calculus (AEC). The AEC is a logic-based formalism that is developed here to support the representation of a distributed agent environment as a persistent composite structure evolving over time. Such a complex structure supports the interaction between agents, objects, and containers, entities that have their own external observable state and can be distributed over a network. Interactions between these entities are specified in terms of events that represent actions executed by agents on objects and other agents in the environment. When events happen they are stored in containers and are notified to agent sensors that subscribe to event descriptions and as a result perceive the interactions. The AEC formalism also allows changes caused by events to be delivered across distributed containers, according to the topology of the application environment. We illustrate the use of AEC and we show how to specify interactions within the GOLEM agent platform applied to a specific agent scenario.
Monday 16 November, 12.00, Room S3.31
Jan Reichelt, Mendeley Research Networks
Title: Mendeley - A Last.fm for Research?
Abstract: Mendeley (http://www.mendeley.com) is two things: Free academic desktop software (available for Windows, Mac and Linux) for managing & sharing research papers, and a website where you can back up and manage your research papers, discover research trends, and connect to like-minded researchers. Based on the users’ paper collections, Mendeley Web anonymously aggregates research statistics and also connects like-minded researchers and academics. In the future, Mendeley hopes to build a large and open semantic database of research papers, similar to a “Last.fm for research”.
Mendeley's first public beta was released at the end of 2008, and there are now over 50,000 users from universities and research institutions globally. The top three user bases are Stanford, Cambridge and Imperial College. Jan Reichelt - one of the 3 founders of Mendeley - will talk about the idea behind the software, how the software can help researchers, and the future for Mendeley.
Monday 2 November, 12.00, Room S3.31
Katie Atkinson, University of Liverpool
Title: Arguments, Values and Baseballs
Abstract: One approach to handling non-monotonic reasoning is through modelling arguments that agents can exchange in order to decide what to believe or how to act. One popular method for achieving this is the use of argumentation frameworks in which arguments are evaluated against how well they defend themselves from the attack of other arguments. However, such arguments are defined to be of an abstract, structureless nature and the question arises as to where the arguments come from. One answer is that they can be generated from instantiations of argumentation schemes, which represent stereotypical patterns of reasoning and supply contextual information about a topic under consideration. In this talk I show how these two argumentation techniques – argumentation schemes and argumentation frameworks - can be linked to model scenarios where agents need to make decisions about what to do. I demonstrate the approach with an application that models the reasoning in a particular legal case and distinguishes the justification of facts, based on the reliability of their sources, from the justification of choices about the interpretation of the law, based on qualitative value preferences. The legal case concerns a dispute over ownership of a baseball and I show how the formal analysis can provide the outcome as given in the actual case.
Monday 26 October, 12.00, Room S3.31
Mohammed Abdullah, King's College London
Title: The cover time of a random graph with a given degree distribution
Abstract: The cover time of a graph is the expected number of steps it takes a random walk on the graph to visit every vertex. This parameter, though simple to state, is quite difficult to determine for most types of graphs often requiring the employment of sophisticated techniques. In this talk I will outline a how we were able to give tight asymptotic bounds for the cover time of a random graph with a given degree sequence, that is, a graph chosen uniformly at random from the space of all simple graphs having vertices with degrees matching the chosen degree sequence.
Monday 19 October, No seminar
Wednesday 14 October, 16.00, Room K4.31
Gregory Kucherov, CNRS LIlle (France) and J.-V.Poncelet Lab, Moscow (Russia)
Title: Efficient seeding techniques for protein similarity search"
Abstract: In this talk, I first present the concept of spaced seeds for
approximate string matching and sequence local alignment. Since about 2002, spaced seeds and their different generalizations became an efficient tool for improving the performance of DNA sequence search. However, very little work has been done on applying spaced seeds to protein sequences, and it was not even clear if such an application could be beneficial. In this work, we show that an appropriate type of seeds, that we call subset seeds, can indeed be advantageous to use in protein sequence search. This conclusion is validated by computations made on probabilistic models as well as by experiments on real data.
Monday 12 October, 12.00, Room S3.31
William Langdon, King's College London
Title:
Interpreting a genetic programming population with nVidia C++ CUDA
Abstract: The GPU Single Instruction Multiple Thread hardware allows the whole of a genetic programming population consisting of quarter of a million small but different program to be run in parallel. Combined with sub-machine code GP, a single Tesla card inserted into a desk top PC can deliver an average sustained performance of 57 billion GP operations per second. This is demonstrated on benchmarks never attempted before let alone solved.
Wednesday 7 October, 14.30, Room K.23D
Diane Donovan, University of Queensland
Title: Change Detection via Spectral Analysis in Dynamic Enterprise Networks
Abstract: In the present global environment, enterprise communication networks are continually expanding, both in terms of size and complexity. Consequently, an important aspect of network management is the development of efficient tools that ensure robust network performance, and monitor changes in both network topology and complexity. We are specifically interested in detecting changes which are the result of abnormal events or trends. By representing networks as combinatorial graphs we gain access to a rich mathematical environment that facilitates a rigorous study the dynamical aspects of these structures. In this talk we will compare different distance measures which have been developed to detect changes in network traffic. In particular, we will define a metric based on vertex clustering through spectral analysis and other techniques.
Monday 5 October 2009, 12.00, Room S3.31
Simon Miles, King's College London
Title: Contract-based Systems for Cross-Organisational Applications
Abstract: Mirroring the paper versions exchanged between businesses today, electronic contracts offer the possibility of dynamic, automatic creation and enforcement of restrictions and compulsions on behaviour that are designed to ensure that business objectives are met. However, when there are many contracts within a particular application, it can be difficult to determine whether the system can reliably fulfil them all; computer-parsable electronic contracts may allow such verification to be automated. In this presentation, I will introduce the role of norms in electronic contracting, and will describe the work of a recent project which sought to develop frameworks, components and tools that make it possible to model, build, verify and monitor distributed electronic business systems on the basis of dynamically generated, cross-organisational contracts. In particular, I will describe the conceptual framework and architecture specification, illustrated with an aerospace after-market example.
Daniel Paulusma, Durham University
Title: Fast exact algorithms for hamiltonicity in claw-free graphs
Abstract: The Hamiltonian Cycle problem asks if an n-vertex graph G has a cycle passing through all vertices of G. This problem is a classic NP-complete problem. So far, finding an exact algorithm that solves it in O*(a^n) time for some constant a<2 is a notorious open problem. For a claw-free graph G, finding a hamiltonian cycle is equivalent to finding a closed trail (eulerian subgraph) that dominates the edges of some associated graph H. Using this translation we obtain two exact algorithms that solve the Hamiltonian Cycle problem for the class of claw-free graphs: one algorithm that uses O*(1.6818^n) time and exponential space and one algorithm that uses O*(1.8878^n) time and polynomial space.
Monday 23 November, 12.00, Room S3.31
Kostas Stathis, Royal Holloway, University of London
Title: Distributed Agent Environments in the Ambient Event Calculus
Abstract: We study the development of distributed agent environments as distributed event-based systems specified in the Ambient Event Calculus (AEC). The AEC is a logic-based formalism that is developed here to support the representation of a distributed agent environment as a persistent composite structure evolving over time. Such a complex structure supports the interaction between agents, objects, and containers, entities that have their own external observable state and can be distributed over a network. Interactions between these entities are specified in terms of events that represent actions executed by agents on objects and other agents in the environment. When events happen they are stored in containers and are notified to agent sensors that subscribe to event descriptions and as a result perceive the interactions. The AEC formalism also allows changes caused by events to be delivered across distributed containers, according to the topology of the application environment. We illustrate the use of AEC and we show how to specify interactions within the GOLEM agent platform applied to a specific agent scenario.
Monday 16 November, 12.00, Room S3.31
Jan Reichelt, Mendeley Research Networks
Title: Mendeley - A Last.fm for Research?
Abstract: Mendeley (http://www.mendeley.com) is two things: Free academic desktop software (available for Windows, Mac and Linux) for managing & sharing research papers, and a website where you can back up and manage your research papers, discover research trends, and connect to like-minded researchers. Based on the users’ paper collections, Mendeley Web anonymously aggregates research statistics and also connects like-minded researchers and academics. In the future, Mendeley hopes to build a large and open semantic database of research papers, similar to a “Last.fm for research”.
Mendeley's first public beta was released at the end of 2008, and there are now over 50,000 users from universities and research institutions globally. The top three user bases are Stanford, Cambridge and Imperial College. Jan Reichelt - one of the 3 founders of Mendeley - will talk about the idea behind the software, how the software can help researchers, and the future for Mendeley.
Monday 2 November, 12.00, Room S3.31
Katie Atkinson, University of Liverpool
Title: Arguments, Values and Baseballs
Abstract: One approach to handling non-monotonic reasoning is through modelling arguments that agents can exchange in order to decide what to believe or how to act. One popular method for achieving this is the use of argumentation frameworks in which arguments are evaluated against how well they defend themselves from the attack of other arguments. However, such arguments are defined to be of an abstract, structureless nature and the question arises as to where the arguments come from. One answer is that they can be generated from instantiations of argumentation schemes, which represent stereotypical patterns of reasoning and supply contextual information about a topic under consideration. In this talk I show how these two argumentation techniques – argumentation schemes and argumentation frameworks - can be linked to model scenarios where agents need to make decisions about what to do. I demonstrate the approach with an application that models the reasoning in a particular legal case and distinguishes the justification of facts, based on the reliability of their sources, from the justification of choices about the interpretation of the law, based on qualitative value preferences. The legal case concerns a dispute over ownership of a baseball and I show how the formal analysis can provide the outcome as given in the actual case.
Monday 26 October, 12.00, Room S3.31
Mohammed Abdullah, King's College London
Title: The cover time of a random graph with a given degree distribution
Abstract: The cover time of a graph is the expected number of steps it takes a random walk on the graph to visit every vertex. This parameter, though simple to state, is quite difficult to determine for most types of graphs often requiring the employment of sophisticated techniques. In this talk I will outline a how we were able to give tight asymptotic bounds for the cover time of a random graph with a given degree sequence, that is, a graph chosen uniformly at random from the space of all simple graphs having vertices with degrees matching the chosen degree sequence.
Monday 19 October, No seminar
Wednesday 14 October, 16.00, Room K4.31
Gregory Kucherov, CNRS LIlle (France) and J.-V.Poncelet Lab, Moscow (Russia)
Title: Efficient seeding techniques for protein similarity search"
Abstract: In this talk, I first present the concept of spaced seeds for
approximate string matching and sequence local alignment. Since about 2002, spaced seeds and their different generalizations became an efficient tool for improving the performance of DNA sequence search. However, very little work has been done on applying spaced seeds to protein sequences, and it was not even clear if such an application could be beneficial. In this work, we show that an appropriate type of seeds, that we call subset seeds, can indeed be advantageous to use in protein sequence search. This conclusion is validated by computations made on probabilistic models as well as by experiments on real data.
Monday 12 October, 12.00, Room S3.31
William Langdon, King's College London
Title:
Interpreting a genetic programming population with nVidia C++ CUDA
Abstract: The GPU Single Instruction Multiple Thread hardware allows the whole of a genetic programming population consisting of quarter of a million small but different program to be run in parallel. Combined with sub-machine code GP, a single Tesla card inserted into a desk top PC can deliver an average sustained performance of 57 billion GP operations per second. This is demonstrated on benchmarks never attempted before let alone solved.
Wednesday 7 October, 14.30, Room K.23D
Diane Donovan, University of Queensland
Title: Change Detection via Spectral Analysis in Dynamic Enterprise Networks
Abstract: In the present global environment, enterprise communication networks are continually expanding, both in terms of size and complexity. Consequently, an important aspect of network management is the development of efficient tools that ensure robust network performance, and monitor changes in both network topology and complexity. We are specifically interested in detecting changes which are the result of abnormal events or trends. By representing networks as combinatorial graphs we gain access to a rich mathematical environment that facilitates a rigorous study the dynamical aspects of these structures. In this talk we will compare different distance measures which have been developed to detect changes in network traffic. In particular, we will define a metric based on vertex clustering through spectral analysis and other techniques.
Monday 5 October 2009, 12.00, Room S3.31
Simon Miles, King's College London
Title: Contract-based Systems for Cross-Organisational Applications
Abstract: Mirroring the paper versions exchanged between businesses today, electronic contracts offer the possibility of dynamic, automatic creation and enforcement of restrictions and compulsions on behaviour that are designed to ensure that business objectives are met. However, when there are many contracts within a particular application, it can be difficult to determine whether the system can reliably fulfil them all; computer-parsable electronic contracts may allow such verification to be automated. In this presentation, I will introduce the role of norms in electronic contracting, and will describe the work of a recent project which sought to develop frameworks, components and tools that make it possible to model, build, verify and monitor distributed electronic business systems on the basis of dynamically generated, cross-organisational contracts. In particular, I will describe the conceptual framework and architecture specification, illustrated with an aerospace after-market example.
Upcoming colloquia
Recent colloquia
Further information
More talks will be added as details become available.
If you would like to be put on our mailing list, please enter your details here.
Past programmes (since spring 2000) are archived in the Past Colloquia section. We also maintain a list of related seminar series in the London area.
If you would like to be put on our mailing list, please enter your details here.
Past programmes (since spring 2000) are archived in the Past Colloquia section. We also maintain a list of related seminar series in the London area.