Department of Computer Science and Information Systems

Research Seminars

The department hosts a programme of research seminars by invited speakers and departmental staff. The seminars are open to all. The following seminars will be taking place at the Department of Computer Science and Information Systems (DCSIS), Birkbeck College, or London Knowledge Lab (LKL), Birkbeck College and Institute of Education.

If you are interested in presenting a seminar please contact

• External seminars
• Seminars from previous years

Academic Year 2012/13

Abstracts

Ontology-Based Data Access and Non-Uniform Constraint Satisfaction

Professor Frank Wolter, Department of Computer Science, University of Liverpool.

Room 745, Birkbeck Main Building - Wednesday, 19th of March 2014, from 16:30 to 17:40

Ontology-based data access is concerned with querying incomplete data sources in the presence of domain-specific knowledge provided by an ontology. A central notion in this setting is that of an ontology-mediated query, which is a database query coupled with an ontology. In this talk, we discuss several classes of ontology-mediated queries, where the database queries are given as some form of conjunctive query and the ontologies are formulated in description logics or other relevant fragments of first-order logic, such as the guarded fragment and the unary-negation fragment.

We then establish intimate connections between ontology-mediated queries and constraint satisfaction problems (CSPs) and their logical generalization, MMSNP formulas. These connections are exploited to obtain results regarding first-order and datalog-rewritability of ontology-mediated queries and P/NP dichotomies for ontology-mediated queries.

[top of page]

What we talk about when we talk about graphs

Dr George Fletcher, Eindhoven University of Technology, The Netherlands.

Room 745, Birkbeck Main Building - Tuesday, 4th of March 2014, from 16:30 to 17:40

An old idea from the humanistic sciences has it that the language we use not only restricts the manner in which we view the world, but also, in a very real sense, shapes the world around us. Recently, my colleagues and I have been exploring the interesting ways in which this idea manifests itself in data management. In particular, we have been studying the expressive power of graph query languages with a focus on characterizing the ability of languages to restrict and shape concrete graph instances, purely in terms of the structure of the instances.

In this talk, I will start with a brief recap of the history of such structural characterizations of query languages. I will then introduce the theoretical framework we have been developing for reasoning over graph structured data, and discuss how we put the framework to work with the design of structural indexes for (RDF) graphs, to support efficient query evaluation over massive graphs. Finally, I will conclude with a discussion of broader applications of the framework in data management and indications for further research.

[top of page]

An introduction to quantum computing

Dr Ashley Montanaro, Department of Computer Science, University of Bristol.

Room 745, Birkbeck Main Building - Wednesday, 19th of February 2014, from 16:40 to 17:40

The model of quantum computation offers the prospect of using the principles of quantum mechanics to obtain dramatically faster algorithms for certain problems than are possible for any standard computer based only on the laws of classical physics. In this talk, I will give an introduction to the field and some of its principal results, as well as more recent work. In particular, I will discuss how ideas from quantum complexity theory can be used to prove hardness of many computational problems, some of which are apparently unconnected to quantum mechanics. This demonstrates that concepts from quantum computing can be useful even if large-scale quantum computers are never built.

[top of page]

Hunter, Cauchy Rabbit, and Optimal Kakeya Sets

Dr Ron Peretz, Mathematics department, London School of Economics (LSE).

Room 160, Birkbeck Main Building - Wednesday, 22nd of January 2014, from 16:30 to 17:30

A Cauchy random walk will take us from a Hunter-Rabbit search game on the circle to the famous Kakeya problem and back.

Joint work with Y. Babichenko, Y. Peres, P. Sousi and P. Winkler.

[top of page]

Planning Snow Plowing in Berlin: Solving Parameterized Rural Postman Problem

Professor Gregory Gutin, Department of Computer Science, Royal Hollaway, University of London.

Room 160, Birkbeck Main Building - Monday, 9th of December 2013, from 16:30 to 17:30

The Directed Rural Postman Problem (DRPP) can be formulated as follows: given a strongly connected directed multigraph $D=(V,A)$ with nonnegative integral weights on the arcs, a subset $R$ of $A$ and a nonnegative integer $\ell$, decide whether $D$ has a closed directed walk containing every arc of $R$ and of total weight at most $\ell$. DRPP is NP-complete. Let $k$ be the number of weakly connected components in the the subgraph of $D$ induced by $R$. Sorge et al. (2012) asked whether the DRPP is fixed-parameter tractable (FPT) when parameterized by $k$, i.e., whether there is an algorithm of running time $O^*(f(k))$ where $f$ is a function of $k$ only and the $O^*$ notation suppresses polynomial factors. Sorge et al. (2012) noted that this question is of significant practical relevance (in Snow Plowing in Berlin, k is between 3 and 5) and has been open for more than thirty years. Using an algebraic approach, we prove that DRPP has a randomized algorithm with false negatives of running time $O^*(2^k)$ when $\ell$ is bounded by a polynomial in the number of vertices in $D$. We also show that the same result holds for the undirected version of DRPP, where $D$ is a connected undirected multigraph.

Joint work with Magnus Wahlstrom and Anders Yeo.

[top of page]

Animating the Coalition Planning Process

Dr Jitu Patel, Defence Science and Technology Laboratory (Dstl).

Room 160, Birkbeck Main Building - Wednesday, 27th of November 2013, from 16:30 to 17:30

The seminar will be on my research, which draws on both artificial intelligence and psychology, to make the coalition (UK with partner nations) planning process more agile and dynamic. Planning for military operations is a multifaceted, knowledge-intensive, and collaborative endeavour. It’s conducted before and during an operation by specialist military personnel, who still carry out the planning process with limited use of any decision support tools. In this seminar, I will outline the military planning process and summarise some of the key research efforts on designing decision support tools over the last two decades. Unfortunately, very little of this research has managed to win over the planners. I will summarise my research, over the last 10 years, in designing tools to support military planners. Finally, I will present some of the outstanding research issues that I would like to address over the next few years.

Jitu Patel is a principal scientist at the Defence Science and Technology Laboratory (Dstl). He has a PhD in artificial intelligence from the Open University, and is a fellow of IET. His research interests include knowledge representation, reasoning, learning and cross-cultural studies.

[top of page]

Cliques, Coloring and Satisfiability: from structure to algorithms

Dr Vadim Lozin, Mathematics Institute, University of Warwick.

Room 160, Birkbeck Main Building - Wednesday, 20th of November 2013, from 16:30 to 17:30

Cliques, coloring and satisfiability are three central problems of theoretical computer science each of which is generally NP-hard. On the other hand, each of them may become tractable when restricted to instances of particular structure. In this talk we analyze how the structure of the input can affect the computational complexity of these problems. We also discuss some algorithmic tools to solve the problems with a focus given to transformations of graphs and of CNF formulas.

[top of page]

Design by Contract for multiparty distributed interactions: static and dynamic validation

Dr Laura Bocchi, Department of Computing, Imperial College London.

Room 160, Birkbeck Main Building - Wednesday, 6th of November 2013, from 16:30 to 17:30

Multiparty session types (MPSTs) are a typing theory for protocols involving two or more participants communicating via asynchronous message passing (aka choreographies). MPSTs enable tractable and modular verification of properties on the types of exchanged data and on the causality of the interactions. This talk will centre on the extension of MPSTs with logical formulae, called multiparty session assertions (MPSAs), which yields an assertion method for session communication based on Design by Contract (DbC). DbC promotes reliable software development through the elaboration of type signatures with logical formulae. Trough the elaboration of MPSTs with predicates, we allow the verification of a richer set of properties (wrt MPSTs), namely on the contents of the exchanged messages, on the selected branches, and recursion invariants. I will talk about static verification of distributed applications against MPSAs, which works under the assumption that all endpoints are well-typed, and about a recent extensions of our framework to support run-time safety enforcement in presence of untrusted endpoints. This extension is motivated by its practical application to a large-scale infrastructure for ocean observation.

[top of page]

A simplified combinatorial treatment of constructions and threshold gaps of ramp schemes

Dr Maura Paterson, Department of Economics, Mathematics and Statistics, Birkbeck, University of London.

Room 160, Birkbeck Main Building - Wednesday, 23rd of October 2013, from 16:30 to 17:30

A (t_1,t_2,n)-ramp scheme is a method for a dealer to distribute shares to n players such that any subset of t_2 players can combine their shares to recover a unique secret, whereas the shares belonging to any set of t_1 or fewer players reveal no information about the secret. In this talk we describe how a combinatorial approach yields straightforward proofs of recent results involving the threshold gap t_2-t_1, and we exploit the connection between error-correcting codes and ramp schemes to derive a new explicit bound on the minimum length of a code having a specified distance and dual distance.

[top of page]

Gap theorems in Proof Complexity

Dr Barnaby Martin, School of Science and Technology, Middlesex University, London.

Room 160, Birkbeck Main Building - Wednesday, 9th of October 2013, from 16:30 to 17:30

The origins of Proof Complexity lie largely in the program of Cook and Reckow, who aimed to separate P and NP (actually, coNP and NP) by proving that no propositional proof system is polynomially bounded. Having failed to obtain such a general result, students of Proof Complexity have instead focused on proving that stronger and stronger proof systems are not polynomially bounded. Such lower bounds are known for systems such as Resolution and Bounded-depth Frege.

Resolution is in fact a refutation system in which one proves that a propositional formula in CNF is a contradiction. A classic result from the area concerns the tree-like restriction of Resolution. Riis proved that contradictions that uniformly encode a first-order principle without finite models over a universe of size n either 1.) have refutations of size n^{O(1)} or 2.) require size 2^{en} for some positive e. The latter case prevails precisely when the first-order principle has an infinite model.

We will give an introduction to Riis's celebrated result and go on to consider more recent gap theorems in refutation systems based on Integer Linear Programming, such as Lovasz-Schrijver and Sherali-Adams.

[top of page]

Learning from multi-modal data: integration, fusion, and data translation

Professor Samuel Kaski, Helsinki Institute for Information Technology HIIT Aalto University and University of Helsinki

Room 160, Birkbeck Main Building - Wednesday, 27th of July 2013, from 16:30 to 17:30

In data analysis tasks, across fields from genomics to multimodal interfaces, one of the most needed operations is data integration or data fusion. For the goal of making sense of the data, the different very high-dimensional data sources give different but complementary information. In a case study in genomics, the sources include gene expression in different diseases and under different treatments, metabolite concentrations, DNA copy number variation etc. Given the large number of data sources with mostly unknown connections, it may be more appropriate to talk about data translation than integration, with the goal being to find, characterize, and utilize the unknown connections between data sources. In machine learning this task has been called unsupervised multi-view machine learning, for which we have introduced Bayesian canonical correlation analysis-based methods, and recently Group Factor Analysis (GFA) which generalizes factor analysis from analysing relationships of univariate variables to analysis of multiple data sources each consisting of multivariate observations. I will discuss the methods and present case studies in metabolomics and in analysing genome-wide effects of drugs.

Brief Bio: Samuel Kaski is director of Helsinki Institute for Information Technology HIIT, a joint research instute of Aalto University and University of Helsinki, and a profesor of computer science at the Aalto University. His research field is machine learning and probabilistic modeling, with applications in computational biology and medicine, proactive interfaces, information visualization, and brain signal analysis.

[top of page]

The Power of Prediction: Cloud Bandwidth and Cost Reduction

Dr Osnat Mokryn, School of Computer Science, Academic College of Tel Aviv-Yafo, Israel

Room 160, Birkbeck Main Building - Thursday, 23rd of May 2013, from 16:30 to 17:30

In this paper we present PACK (Predictive ACKs), a novel end-to-end Traffic Redundancy Elimination (TRE) system, designed for cloud computing customers. Cloud-based TRE needs to apply a judicious use of cloud resources so that the bandwidth cost reduction combined with the additional cost of TRE computation and storage would be optimized. PACK’s main advantage is its capability of offloading the cloud-server TRE effort to end-clients, thus minimizing the processing costs induced by the TRE algorithm. Unlike previous solutions, PACK does not require the server to continuously maintain clients’ status. This makes PACK very suitable for pervasive computation environments that combine client mobility and server migration to maintain cloud elasticity. PACK is based on a novel TRE technique, which allows the client to use newly received chunks to identify previously received chunk chains, which in turn can be used as reliable predictors to future transmitted chunks. We present a fully functional PACK implementation, transparent to all TCP-based applications and network devices. Finally, we analyze PACK benefits for cloud users, using traffic traces from various sources.

Joint work with Eyal Zohar and Israel Cidon. The work was presented at SigComm'11, and extended to a ToN paper 2013.

[top of page]

Datalog containment and hidden web queries

Professor Michael Benedikt, Department of Computer Science, Oxford

Room 160, Birkbeck Main Building - Tuesday, 14th May 2013, from 16:30 to 17:30

The implication/containment problem for the basic recursive query language Datalog has been studied in the database literature for decades. It is known to be undecidable in general, but several decidable subclasses were identified, for example, Monadic Datalog. However, the exact complexity of the problem is not fully understood. In this talk I will overview new techniques for pinpointing how hard containment is for some important subclasses of Datalog, including those that arise from querying the "hidden web" -- data hidden behind web forms.

Time permitting, I will also discuss other work being done in Oxford on querying the hidden web, including, generating query plans and discovering access patterns.

This talk includes joint work with Pierre Bourhis, Georg Gottlob, and Pierre Senellart.

[top of page]

Lower Bounds for Streaming Problems

Dr Markus Jalsenius, Department of Computer Science, University of Bristol

Room 160, Birkbeck Main Building - Wednesday, 20th March 2013, from 16:30 to 17:30

Time lower bounds for dynamic data structures have historically proven hard to show. The very first log(n) lower bound was obtained as recently as in 2004. Building on the lower bound techniques from data structures, we have proved the very first time lower bounds for streaming problems. In this talk I will consider the following fundamental streaming problems: computing the convolution/cross-correlation (i.e. the inner product) between a fixed vector of length n and the last n numbers of a stream, computing the Hamming distance between a fixed string of length n and the last n symbols of a stream, as well as multiplication of two n digit numbers (here the digits arrive one at a time and the corresponding digit of the product has to be outputted before the next digit arrives). For these problems we obtain lower bounds of log(n) time on average per output. The lower bounds are given in the cell-probe model (hence hold in the RAM model) and hold under randomisation and amortisation. The lower bounds are unconditional, in particular there are no space constraints. I will argue why our lower bounds are unlikely to be improved and how they relate to the currently known upper bounds.

It is joint work with Raphael Clifford and Benjamin Sach.

[top of page]

ORGANIZING AND FINANCING NEW TECHNOLOGY VENTURES

Dr Pierre Nadeau, Department of Management, Birkbeck, University of London

Room 160, Birkbeck Main Building - Tuesday, 5th of March 2013, from 12:00 to 13:00

In this session, we focus on organizing new ventures, protecting intellectual property, and financing in the early stage. We start with some background on entrepreneurship, its opportunities and risks. We briefly describe proprietorship, partnership, and corporate forms of business organization and contrast benefits, risks, and basic tax aspects of various organizational forms. We discuss the use of patents, trademarks and copyrights and other methods to protect intellectual property and highlight factors that can affect the performance of university spinouts. Then we explain how different types of early-stage financing can be obtained from various sources (e.g. government programs, crowdfunding, angels and venture capitalists) throughout the life cycle of a new venture firm. The interactive session will include short video clips from leading professionals and academics in the fields of technology entrepreneurship and venture capital finance.

Biography of Speaker

Pierre Nadeau is a lecturer in finance at Birkbeck University of London where he received a PhD in Entrepreneurial Finance. He graduated with a B.Eng. (Electronics and Telecoms) in 1981 from the University of Sherbrooke and received a MBA (Finance) in 1984 from the University of Ottawa. He is a member of the American Finance Association, the UK Society for Investment Professionals, Birkbeck Centre for Innovation Management Research and the Editorial Board of Briefings in Entrepreneurial Finance (Wiley). His research interests include: entrepreneurial finance, venture capital and private equity, the finance of innovation and risk management.

Pierre is an experienced technology investment and management executive. He was formerly a general partner at Frontiers Capital where he was responsible for a variety of venture capital fundraising, private placements, investments, restructuring and successful exits in the information and communication technology (ICT) sector in Europe. Notable investments and exit transactions include Synad Technologies, Elata, Volantia, Digital Route, Pervasic and Budget Telecom. Prior to that he was CEO, managing director or general manager of a number of leading public and private technology companies in North America and in Europe including Mitel Semiconductor, LSI Logic, Lucent and Nortel.

[top of page]

Using Mega Events to Cultivate Innovation Events - Cisco and London 2012

Tom Kneen, Business Development Lead

Room B04, Birkbeck Main Building - 26th February, at 12.30, in Main Building

CISCO seminar

[top of page]

DIADEM: Self-supervised Extraction of Complex Web Objects.

Dr Giorgio Orsi, Department of Computer Science, Oxford.

Room 160, Birkbeck Main Building - Wednesday, 6th of February 2013, 16:30 to 17:30

Abstract: Search engines are the sinews of the web. These sinews have become strained, however: Where the web's function once was a mix of library and yellow pages, it has become the central marketplace for information of almost any kind. We search more and more for objects with specific characteristics, a car with a certain mileage, an affordable apartment close to a good school, or the latest accessory for our phones. Search engines all too often fail to provide reasonable answers, making us sift through dozens of websites with thousands of offers--never to be sure a better offer isn't just around the corner. What search engines are missing is understanding of the objects and their attributes published on websites.

Automatically identifying and extracting these objects is akin toalchemy: transforming unstructured web information into highly structured data with near perfect accuracy. With DIADEM we present a formula for this transformation, but at a price: we need to provide DIADEM with extensive knowledge about the ontology and phenomenology of the domain, i.e., about entities (and relations) and about the representation of these entities in the textual, structural, and visual language of a website of this domain. We will demonstrate that, in contrast to alchemists, DIADEM has developed a viable formula.

Bio: Giorgio Orsi is a post-doctoral research fellow at the Department of Computer Science of the University of Oxford and a junior James Martin fellow at the Institute for the Future of Computing of the Oxford-Martin School. His research is concerned with the investigation of problems in “Big Data” management on the Web. In particular, large-scale web data extraction and ontological reasoning.

[top of page]

Analysing Spatial Point Patterns in Nuclear Biology using Aggregate Maps

Dr David Weston, Department of Computer Science and Information Systems, Birkbeck, University of London.

Room 160, Birkbeck Main Building - Wednesday, 23rd of January 2013, 16:30 to 17:30

There have been many investigations into identifying possible relationships between the location of bodies within a cell nucleus and their function. Interesting relationships are identified by comparing how different the locations of the bodies are to what is expected if the locations were chosen at random. However, the number of bodies involved is often very low and this has consequences on the effectiveness of quantitative analysis procedures. It becomes increasingly difficult to distinguish between bodies whose locations have been chosen at random and bodies whose locations have a biologically interesting preference, with decreasing number of bodies involved. Therefore a commonly used approach, which is to analyse cells individually, has the potential to overlook interesting structures. An alternative approach is to aggregate the locations of bodies from multiple cells using simple normalization, but this requires care to choose the appropriate normalization. It is to address this issue that `Aggregate aps' has been proposed. An aggregate map for a collection of cells is constructed simply by fusing the images of individual cells using standard methods for image registration. This talk will be split into two parts. In the first part I will describe how to construct an aggregate map. The second part of the talk will be devoted to the important issue of how to interpret the result.

[top of page]

The Future of Search and Discovery in Big Data Analytics: Ultrametric Information Spaces

Professor Fionn Murtagh, Department of Computer Science, Royal Holloway, University of London.

Room 160, Birkbeck Main Building - Wednesday, 21st of November 2012, 16:30 to 17:30

In considering hierarchical clustering for structuring and orienting search and retrieval, I will describe a new linear time hierarchical clustering method. The hierarchy is induced from the Baire distance. This is applied to astronomy data, using Sloan Digital Sky Survey (SDSS) spectroscopic data, and to a large database of chemical compounds. This work is motivated, firstly, by the knowledge that as spatial dimensionality becomes very large so too does spatial sparsity and ultrametricity. The latter expresses the property of hierarchically embedded clusters. The second motivation for this work is to benefit computationally from these findings, for the tasks of search, discovery, and data understanding, in massive and possibly very high dimensional data. A major current application field is that of text analysis.

[top of page]

A Shapley-value approach for influence attribution

Dr Panagiotis Papapetrou

Room 160, Birkbeck Main Building - Wednesday, 7th of November 2012, 16:30 to 17:30

Finding who and what is important is an ever-occurring question. Many methods that aim at characterizing important items or influential individuals have been developed in areas such as bibliometrics, social-network analysis, link analysis, and web search.

In this talk, I will present the problem of attributing influence scores to individuals who accomplish tasks in a collaborative manner. Individuals are assumed to build small teams, in different and diverse ways, in order to accomplish atomic tasks. For each task an assessment of success or importance score is given, and the goal is to attribute those team-wise scores to the individuals. The challenge we face is that individuals in strong coalitions are favoured against individuals in weaker coalitions, so the objective to find fair attributions that account for such biasing.

I will describe an iterative algorithm for solving this problem that is based on the concept of Shapley value. The method is applicable to a variety of scenarios, for example, attributing influence scores to scientists who collaborate in published articles, or employees of a company who participate in projects. The method has been evaluated on two real datasets: ISI Web of Science publication data and the Internet Movie Database.

[top of page]

A Very Brief Overview of Theories of Consciousness

Dr Steve Minett

Room 160, Birkbeck Main Building - Wednesday, 24th of October 2012, 16:30 to 17:30

What is consciousness? Why do we have it? What’s it for? This presentation is an attempt to survey the ways in which people have tried to answer these questions. It’s a journey through the most prominent theories of consciousness. It starts with every-day ‘Folk Psychology’, stops briefly at Modernism’s de-construction of Folk Psychology, introduces Minsky’s ‘suitcase of consciousness’ and compares this with Deutsch’s ‘sky-scrapper of Reductionism’. Opening the suitcase, the presentation considers; computationalism, Functionalism and biological naturalism, including Searle’s ‘Chinese Room’. It next turns to theories that question Realism, including Velman’s ‘Reflexive Model’ and Varela & Maturana on embodiment. It considers theories of the function of the sentient self from Wegner & Humphrey, and finally takes a very brief look at Penrose & Hammerhoff’s quantum theory of consciousness.

The presentation is a condensation of a four-unit course, the entire content of which is available in the form of multiple, audio-visual clips (totalling about four and a half hours) on the following website:

http://consciousnesstheories-minett.com/

[top of page]

Learning in Exploratory Environments: Freedom, Control, Research

Dr Sergio Gutierrez-Santos

Room 160, Birkbeck Main Building - Thursday, 11th of October 2012, 16:30 to 17:30

Exploratory Learning Environments (ELE) aim at empowering students to learn while they explore a given domain on their own terms. ELE can make the learning experience more engaging, fun, and productive. On the other hand, they require a lot of support for learners (and teachers), which is very challenging to provide when you are a computer and not a human being. This seminar will introduce the importance of exploratory learning, both pedagogically and technically, and the open research challenges in the field from a technical point of view

[top of page]

---

Quick links

Seminars Menu

• Seminars Home
• London Knowledge Lab Seminars

Previous Seminars

Select... Year 2009/10 Year 2008/9 Summer 2008 Spring 2008 Autumn 2007 Summer 2007 Spring 2007 Autumn 2006 Summer 2006 Spring 2006 Autumn 2005 Summer 2005 Spring 2005 Autumn 2004 Summer 2004 Spring 2004 Autumn 2003 Summer 2003 Spring 2003 Autumn 2002 Summer 2002 Spring 2002 Autumn 2001 Summer 2001 Spring 2001 Autumn 2000 Summer 2000 Spring 2000 Autumn 1999 Go