Skip to main content Skip to navigation

Computer Science Colloquium

Organiser: Tom Gur

Colloquia take place fortnightly on Thursdays 14:00-15:00, Lecture Room CS1.01. They are directed towards a general computer science audience. After the talk, we convene in the staff common room for coffee/tea and informal discussions with the speaker.

Additional colloquia, titles and abstracts will be added as details become available.

Current term

First term, 2019-2020:

10 October 2019

14:00 - 15:00

Sunil Prabhakar (Purdue University)
Title: Database Fidelity Without Trust

Abstract:
Ensuring the trustworthiness of data retrieved from a database is of utmost importance to users. Databases are typically subjected to updates from multiple clients, often at very high rates. The correctness of data stored in a database is defined by the faithful execution of only valid (authorized) transactions. In this talk we address the question of whether it is necessary to trust a database server in order to trust the data retrieved from it? The lack of trust arises naturally if the database server is owned by a third party, as in the case of cloud computing, or if it is likely that the server may have been compromised, or there is a malicious insider.

24 October 2019

14:00 - 15:00

Evangelia Kalyvianaki (Cambridge)

Title: THEMIS -- Fairness in Federated Stream Processing under Overload

Abstract:
Federated stream processing systems, which utilise nodes from multiple
independent domains, can be found increasingly in multi-provider cloud
deployments, internet-of-things systems, collaborative sensing
applications and large-scale grid systems. To pool resources from several
sites and take advantage of local processing, submitted queries are split
into query fragments, which are executed collaboratively by different
sites. When supporting many concurrent users, however, queries may exhaust
available processing resources, thus requiring constant load shedding.
Given that individual sites have autonomy over how they allocate query
fragments on their nodes, it is an open challenge how to ensure global
fairness on processing quality experienced by queries in a federated
scenario.

7 November 2019
14:00 - 15:00
Ata Kaban (Birmingham)

Title: Uncovering structure with randomness for learning in high dimensions

Abstract:
Random projection (RP) is a simple, computationally efficient linear
dimensionality reduction technique with interesting theoretical
properties for learning from data. For instance, it can regularise
ill-conditioned covariance matrices, and it preserves dot products
between vectors and their signs to an extent that depends on their
cosine similarity. It can speed up computations when dealing with high
dimensional data sets, while retaining control of generalisation
performance. Furthermore, in this talk we discuss how RP can also be
used as an analytic tool to better understand why learning from high
dimensional data is not always as difficult as it looks. We present
generalisation bounds where the use of RP highlights how learning can
take advantage of the presence of certain benign geometric structures
in the problem, and yields conditions that reduce
dimensional-dependence of error-guarantees in settings where such
dependence is known to be essential in general. When instantiated in
several examples of learning problems, our analysis ties together
various regularisation schemes in parametric models, and a notion of
intrinsic dimension in the non-parametric case, quantified by the
Gaussian width of the input support or a bounded subset of it.
Finally, we briefly discuss implications for algorithm development,
for both learning and optimisation.

21 November 2019
14:00 - 15:00
Samson Abramsky (Oxford)
5 December 2019
14:00 - 15:00
Tugkan Batu (London School of Economics)
Past terms

Third term, 2018-2019:

Thu 2 May, '19

14:00 - 15:00

Sarah Meiklejohn (UCL)
Title: Anonymity in Cryptocurrencies
(This talk will take place in CS1.04)
Abstract: A long line of recent research has demonstrated that existing cryptocurrencies often do not achieve the level of anonymity that users might expect they do, while at the same time another line of research has worked to increase the level of anonymity by adding new features to existing cryptocurrencies or creating entirely new cryptocurrencies. This talk will explore both of these lines of research, demonstrating both de-anonymization attacks and techniques for anonymity that achieve provably secure guarantees.
Thu 9 May, '19
14:00 - 15:00
Edith Elkind (Oxford)

Title: Fair Division of a Graph

Abstract: We consider fair allocation of indivisible items under an additional constraint: there is an undirected graph describing the relationship between the items, and each agent's share must form a connected subgraph of this graph. This framework captures, e.g., fair allocation of land plots, where the graph describes the accessibility relation among the plots. We focus on agents that have additive utilities for the items, and consider several common fair division solution concepts, such as proportionality, envy-freeness and maximin share guarantee.In particular, we prove that for acyclic graphs a maximin share allocation always exists and can be computed efficiently. We also discuss a continuous variant of this problem, where agents need to divide a collection of interconnected "cakes" and each agent's piece has to be connected, or, more generally, have a small number of connected components.

Based on joint work with Sylvain Bouveret, Katarina Cehlarova, Ayumi Igarashi, Dominik Peters, Xiaohui Bei and Warut Suksompong

Thu 6 Jun, '19

14:00 - 15:00

Andreas Damianou (Amazon, Cambridge)

(This talk will take place in CS1.04)

Title: Probability and uncertainty in Deep Learning

Abstract:
In this talk I motivate deep learning from the perspective of probability and uncertainty. The resulting models can maintain and, crucially, communicate their degree of belief regarding their states (e.g. how certain they are in their predictions) using Bayesian inference. I will also highlight the deep Gaussian process family of approaches, which can be seen as a means of performing probabilistic, Bayesian deep learning directly in the space of functions, rather than in the space of finite parameters. Prior knowledge of deep learning is not essential to follow this talk, in fact I will offer a quick overview in the beginning.

Thu 20 Jun, '19
14:00 - 15:00
Mario Berta (Imperial College London)

Title: Quantum Technologies for Cryptography

Abstract:
The rise of quantum technologies opens exciting possibilities for performing cryptographic tasks, but it also poses new threats. On the one hand, quantum mechanical devices are the basis of a variety of novel cryptographic protocols like key distribution or secure identification, which offer a significant advantage over standard routines. On the other hand, quantum computers will render some existing cryptographic schemes insecure. The interplay between these two aspects is best understood by analysing the power of adversaries which have access to a quantum computer - quantum adversaries. In my talk, I will discuss methods to analyse the power of quantum adversaries which shine light on both aspects.

Thu 11 Jul, '19

11:00 - 12:00

Radu Calinescu (University of York)

Title: Learning, synthesis and efficient analysis of probabilistic models

Abstract:
Probabilistic modelling is a powerful tool for establishing performance, dependability and other quantitative properties of systems and processes during design, verification and at runtime. However, the usefulness of this tool depends on the accuracy of the models being analysed, on the efficiency of the analysis, and on the ability to find models corresponding to effective system and process architectures and configurations. This talk will describe how recent approaches to probabilistic model learning, analysis and synthesis address major challenges posed by these prerequisites, significantly advancing the applicability of probabilistic modelling.