13 January 2022

14:00 - 15:00

Paul Goldberg (Oxford)

Title: Complexity of total search problems

Abstract: There are many theorems of the form "for all, there exists" (such as all games have a Nash equilibrium, or all numbers have a prime factorisation).
They have corresponding computational search problems (e.g. given a number, find a prime factorisation), and the word "total" refers to the property that all inputs have solutions, not just some of them. They include some important problems that do not seem to have polynomial-time algorithms, even though some of them are easy in practice. In the talk, I give an overview of work on classifying their computational complexity.

Bio: Since 2013 I have been a professor at the Dept of Computer Science, University of Oxford. Previously I was a professor at the Dept of Computer Science, University of Liverpool, where I moved in 2006. I was founding head of the ECCO research group. At both Oxford and Liverpool, I’ve worked extensively on algorithmic game theory and related problems in algorithms and computational complexity. Prior to this I was at the Department of Computer Science, University of Warwick, from 1997. I have also worked at Aston University and Sandia National Labs (working on algorithmic problems from computational biology), USA. PhD (Edinburgh, ’92) in computational learning theory; BA in mathematics (Oxford, ’88).

10 February 2022

14:00 - 15:00

Yves-Alexandre de Montjoye (Imperial)

Title: TBD

Abstract: TBD

17 March 2022

14:00 - 15:00

Anuj Dawar (Cambridge)

Title: TBD

Abstract: TBD

07 October 2021

14:00 - 15:00

Mohamed Abdelfattah (Cornel Tech)

Title: Rethinking Deep Learning Computations: From AutoML to Hardware

Abstract: The explosion and availability of data has created a new computation paradigm based on deep learning. Consequently, we need to rethink both software and hardware to make these computations possible and to keep up with the ever-increasing computation demand. In this talk, I will describe how we use automated machine learning (AutoML) to enable on-device AI through neural architecture search, compression, hardware modelling and efficient search algorithms. Next, I will give an overview of my experience in designing hardware and compilers for deep learning acceleration – I will focus on a new automated co-design methodology that simultaneously improves efficiency and accuracy. Finally, I will focus on reconfigurable devices like FPGAs. I will describe how an embedded network-on-chip can transform FPGAs into a general-purpose computation platform well-suited for deep learning.

Bio: Mohamed is an incoming assistant professor of ECE at Cornell University and Cornell Tech. He is currently a research team lead at the Samsung AI Center in Cambridge UK, working on the codesign of deep learning algorithms and hardware. Before that, he was at Intel building an FPGA-based accelerator and compiler for deep neural networks. Mohamed did his PhD at the University of Toronto, during which he was awarded the Vanier Canada Graduate scholarship and three best paper awards for his work on embedded networks-on-chip for FPGAs.

21 October 2021

14:00 - 15:00

Milan Vojnovic (LSE)

Title: Learning to Schedule

Abstract: In this talk, I will present new results for two scheduling problems with unknown parameters that require using a learning algorithm along with a scheduling policy. The first problem is for a multi-class, multi-server queueing system with stochastic rewards of assignments of jobs to servers, with mean rewards depending on the features of jobs and servers according to a bilinear model. The goal is to maximize the expected reward of assignments while maintaining the queueing system stable. The second problem is scheduling jobs with stochastic holding costs with unknown mean values in a single server system. The goal in this problem is to minimize the expected total job holding cost. For both these problems, I will present new algorithms and regret bounds. The motivating application scenarios for these problems arise in data processing platforms, crowdsourcing systems, and other online platforms. Joint work with Jung-Hun Kim and Dabeen Lee

Bio: Milan Vojnovic is a Professor of Data Science, with the Department of Statistics at LSE. He was a Researcher at Microsoft Research from 2004 to 2016. He received a Ph.D. degree EPFL in 2003. He was an affiliated lecturer at the University of Cambridge, from 2014 to 2016. He held a visiting researcher position with Facebook from 2019 to 2021. Milan’s research interests are in optimisation, machine learning, and design of data-driven algorithms. His research work was recognised by various awards including a 2010 ACM Sigmetrics Rising Star Researcher award and a 2005 ERCIM Cor Baayen Award, and several best paper awards at various conferences. He received a Facebook Faculty Research Award in 2019 and a Criteo Faculty Research Award in 2018.

04 November 2021

17:00 - 18:00

Divyakant Agrawal (UC Santa Barbara)

Title: On the power of summary statistics in large-scale data management

Abstract: During the past two decades we have seen an unprecedented increase in the amount of data that is being generated from numerous internet-scale applications. Before this data can be subject to modelling and analysis, it becomes necessary to obtain summary statistics such as the cardinality of unique visitors, frequency counts of users from different states or countries, and in general finding the quantile and median information from the dataset. Efficient algorithms exist for computing the exact information over the data. Unfortunately, these algorithms require a considerable amount of time, scanning the data multiple times, or require additional storage that is linear to the size of the dataset itself. Approximation methods, with guaranteed error bounds, developed in the context of streaming data are extremely effective to extract useful and relatively accurate knowledge from big data. In this talk, we will start with a review of one such approximation technique for estimating frequency counts over streaming data where only insert operations are permitted. We will then present a refinement of this technique in the context of large datasets that need to handle both insert and delete operations.

Bio: Divyakant Agrawal is a Professor of Computer Science at the University of California at Santa Barbara. His research expertise is in the areas of distributed systems and databases. He is a fellow of the AAAS, ACM, and IEEE. He has also had visiting appointments at IBM Almaden Research Labs, NEC Research, ASK.com, Google, Qatar Computing Research Institute, and the National University of Singapore over the course of his professional career.

25 November 2021

14:00 - 15:00

Claus Brabrand (ITU Copenhagen)

Title: How to Increase the Diversity in Computer Science

Abstract: Women are widely underrepresented in Computing studies.
We will consider why this is a problem from various perspectives.
In 2015, only 10% of students on ITU’s Bachelor of Software Development were women. ITU decided to do something about this and a number of initiatives were launched. Now, the percentage of women has risen to more than 20%.
We will present an overview of ITU’s efforts to address this gender imbalance in Computing. Also, we will present recent research on how to change educational activities so that they appeal more to women and to students without prior programming experience. Finally, we will show the effect of ITU’s onboarding initiative BootIT and how this connects with increasing diversity.

Bio: Claus Brabrand holds a Ph.D. in Computer Science from the BRICS International Research Center at Aarhus University (January 2003). He is the writer, director, and co-producer of the award-winning educational short-film “Teaching Teaching & Understanding Understanding” (2006) used around the world for educational development. Since 2007, Claus Brabrand has been an Associate Professor at the IT University of Copenhagen, conducting research within the area of Programming Languages, Program Analysis, and Software Product Lines. Parallel to this, he has worked with Educational Development and "teaching teachers to teach", both at ITU, nationally, and internationally and has done a number of keynotes within this area.

13 May 2021

14:00 - 15:00

Eiko Yoneki (Cambridge)

Title: Optimising Computer Systems in Complex and Dynamic Parameter Space

Abstract: Performance tuning of computer systems is challenging for a variety of reasons. Modern computer systems expose many configuration parameters in a complex and massive parameter space. The systems are nonlinear and there is no method for quantifying or modelling such systems by performance tuning to the level of precision required. Auto-tuning has emerged using a black-box optimiser such as Bayesian Optimisation (BO). However, BO has limited scalability. Reinforcement Learning (RL) could be applied for combinatorial optimisation problems, but there is a gap between current research and practical RL deployments. I will introduce our framework to tackle these issues and demonstrate the potential of machine learning based methodologies for computer system optimisation.

Bio: Eiko Yoneki is a senior researcher in the Systems Research Group of the University of Cambridge Computer Laboratory and a Turing Fellow at the Alan Turing Institute. Her research interests span distributed systems, networking and databases, including large-scale graph processing. Her group’s current research focusses on auto-tuning of data processing/analytics framework to deal with complex parameter space using ML.

27 May 2021

14:00 - 15:00

Ueli Maurer (ETH)

Title: Constructive Cryptography

Abstract: Modularization is a key principle in any constructive discipline. One wants to obtain complex constructions as the composition of simpler
construction steps, where each step constructs an object satisfying a certain specification from other objects satisfying certain (weaker) specifications. Constructive cryptography is a framework in which cryptographic methods are understood (and defined) as such construction steps. For example, a secure encryption scheme constructs a secure channel from an authenticated channel and a shared secret key. The design of cryptographic protocols corresponds to the composition of such construction steps, where for example the shared secret key needed in the above construction can itself be constructed, e.g. by a key agreement protocol. The security proof for the protocol is then simply a consequence of the security proofs of the individual steps. In this talk we give a self-contained introduction to constructive cryptography suitable for a non-specialist audience and present some recent new developments.

Bio: Ueli Maurer is Full Professor of Computer Science at ETH Zurich. His research interests include the theory and applications of cryptography, information security, theoretical computer science, information theory, and discrete mathematics. One of his long-term research goals is to establish a constructive theory of cryptography and to apply it to the modular design of provably-secure cryptographic protocols. He has served as Editor-in-Chief of the Journal of Cryptology from 2002 to 2010. He is an IEEE Fellow, an ACM Fellow, an IACR Fellow, and a member of the German Academy of Sciences (Leopoldina). He received the 2013 Vodafone Innovation Award for Mobile Communications, the 2016 RSA Award for Excellence in Mathematics, and the 2016 Theory of Cryptography (TCC) Test-of-Time Award. Maurer has served many companies and start-ups as board member and consultant and has advised many government organsations. In 2018 he co-founded the Concordium project and foundation aiming at creating a global, universally trusted, provably incorruptible and secure transaction platform.

24 June 2021

14:00 - 15:00

Tobias Weinzierl (Durham)

Title: Stop talking to me (again): some communication-avoiding programming patterns

Abstract: In this talk, we generalise the term communication-avoiding. Beyond its well-established meaning from linear algebra, we make it comprise (i) the reduction of data volume, (ii) the elimination of (meta) data generation, (iii) the reduction of data exchange frequency, (iv) the homogenisation of data access, (v) data access hiding and (vi) the localisation of data transfers. These criteria apply to both classic data exchange between compute nodes as well as data movements on the chip. Communication-avoiding then tackles the problematic divergence sketched above.

Bio: Tobias Weinzierl is Professor in the Department of Computer Science at Durham University, Durham, UK. He has served at the Munich Centre for Advanced Computing (see the Springer edited book, Advanced Computing) before, and holds a PhD and habilitation from the Technical University Munich.

21 January 2021

14:00 - 15:00

Arthur Gervais (Imperial College; Liquidity Network)

4 February 2021

14:00 - 15:00

Ronitt Rubinfeld (MIT)

Title: Local computation algorithms

Abstract: Consider a setting in which inputs to and outputs from a computational problem are so large, that there is not time to read them in their entirety. However, if one is only interested in small parts of the output at any given time, is it really necessary to solve the entire computational problem? Is it even necessary to view the whole input? We survey recent work in the model of "local computation algorithms" which for a given input, supports queries by a user to values of specified bits of a legal output. The goal is to design local computation algorithms in such a way that very little of the input needs to be seen in order to determine the value of any single bit of the output. Though this model describes sequential computations, techniques from local distributed algorithms have been extremely important in designing efficient local computation algorithms. In this talk, we describe results on a variety of problems for which sublinear time and space local computation algorithms have been developed -- we will give special focus to finding maximal independent sets and generating random objects.

Bio: Ronitt Rubinfeld is a Edwin Sibley Webster Professor of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology, and is on the faculty at the University of Tel Aviv. Her research interests include sublinear time algorithms, local algorithms and algorithms for testing discrete distributions over large domains. Ronitt Rubinfeld has been an ONR Young Investigator, a Sloan Fellow, an invited speaker at the Internal Congress of Mathematics (2006) and an ACM Fellow.

15 March 2021

15:00 - 16:00

Amanda Prorok (Cambridge)

Title:
Learning to Communicate in Multi-Agent Systems

Abstract:
Effective communication is key to successful multi-agent coordination. Yet it is far from obvious what, how and when information needs to be shared among agents that aim to solve cooperative tasks. In this talk, I discuss our recent work on using Graph Neural Networks (GNNs) to solve multi-agent coordination problems. In my first case-study, I show how we use GNNs to find a decentralized solution to the multi-agent path finding problem, which is known to be NP-hard. I demonstrate how our policy is able to achieve near-optimal performance, at a fraction of the real-time computational cost. Secondly, I show how GNN-based reinforcement learning can be leveraged to learn inter-agent communication policies. In this case-study, I demonstrate how non-shared optimization objectives can lead to adversarial communication strategies. Finally, I address the challenge of learning robust communication policies, enabling a multi-agent system to maintain high performance in the presence of anonymous non-cooperative agents that communicate faulty, misleading or manipulative information.

Bio:
Amanda Prorok is an Assistant Professor (University Lecturer) in the Department of Computer Science and Technology, at Cambridge University, UK, and a Fellow of Pembroke College. Her mission is to find new ways of coordinating artificially intelligent agents (e.g., robots, vehicles, machines) to achieve common goals in shared physical and virtual spaces. Amanda Prorok has been honored by an ERC Starting Grant, an Amazon Research Award, an EPSRC New Investigator Award, an Isaac Newton Trust Early Career Award, and the Asea Brown Boveri (ABB) Award for the best thesis at EPFL in Computer Science.

29 October 2020

14:00 - 15:00

Video of the colloquium

Benjamin Guedj (UCL)

Title: A primer on PAC-Bayesian learning, followed by News from the PAC-Bayes frontline

Abstract: PAC-Bayes is a generic and flexible framework to address generalisation abilities of machine learning algorithms. It leverages the power of Bayesian inference and allows to derive new learning strategies. I will briefly present the key concepts of PAC-Bayes and illustrate a few of its recent successes, for deep neural networks, for coherent risk measures, contrastive learning and robust learning.

Bio: Benjamin Guedj is a Principal Research Fellow (~Associate professor) at University College London (Centre for Artificial Intelligence and Department of Computer Science). He is also a tenured research scientist at Inria, the top French research institute in mathematics and computer science, and a visiting researcher with the Alan Turing Institute. Since Sept. 2020, he is the founder and scientific director of The Inria London Programme, a joint lab between France and the UK. He holds a PhD in mathematics from Sorbonne Université (Paris, France) and focuses on statistical learning theory, PAC-Bayes, computational statistics, theory for deep learning, among other topics.

19 November 2020

17:00 - 18:00

Rocco Servedio (Columbia University)

Title: Testing noisy linear functions for sparsity

Abstract: This talk explores a question at the intersection of two well-studied topics: (1) sparse recovery, and (2) property testing. Consider the following basic sparse recovery problem: An algorithm is given noisy input-output examples of a linear function over a high-dimensional space. Given the promise that the linear function is sparse, breakthrough work of Candes, Romberg and Tao shows that the linear function can be recovered from a number of examples that scales logarithmically in the dimension (and this dependence is required). We look at this problem from the vantage point of property testing, by studying the complexity of merely determining whether the unknown linear function is sparse versus "far from" sparse. We show that this decision problem can be solved with a number of samples which is completely independent of the dimension if the background high-dimensional distribution of samples has i.i.d. components that are not Gaussian.

Bio: Rocco Servedio is a professor and chair of the Department of Computer Science at Columbia University. His research is in theoretical computer science, and his main research interests lie in computational complexity theory, computational learning theory, property testing, and the role of randomness in computation.

26 November 2020

14:00 - 15:00

John Daugman (University of Cambridge)

Title: Neural Computing, Identity, and Visual Recognition of Persons

Abstract: Brains and computers have long been used as metaphors for each other. In recent years the link has grown stronger, with the explosion of results in machine learning based on big multi-layer networks, and with data from wet neurobiology showing that each cubic millimeter (mm^3) of brain tissue contains about 3 kilometers of "wiring" (neural connections). This talk discusses vision both in machines and in mammals, focusing on pattern encoding mechanisms and their efficiency. The main application areas discussed are face recognition and the IrisCode, which has recently been used to enroll the entire 1.3 billion population of India in a national ID system. Unifying theoretical ideas are entropy, and visual encoders that are optimal under the Uncertainty Principle.

Bio: John Daugman received his degrees at Harvard University and then taught at Harvard before coming to Cambridge University, where he is Professor of Computer Vision and Pattern Recognition. His areas of research include computer vision, information theory, neuro computing and statistical pattern recognition. Awards for his work in science and technology include the Information Technology Award and Medal of the British Computer Society, the "Time 100" Innovators Award, and the OBE, Order of the British Empire. He is the founder and benefactor of the Cambridge Chrysalis Trust.

10 December 2020

14:00 - 15:00

Ava Khamseh (University of Edinburgh)

Title: Higher-order interactions in statistical physics, machine learning and biomedicine

Abstract: The problem of inferring pairwise and higher-order interactions in complex systems involving large numbers of interacting variables, from observational data, is fundamental to many fields. Known to the statistical physics community as the inverse problem, it has become accessible in recent years due to real and simulated big data being generated. In the first part of this talk, we discuss extracting interactions form data using a neural network approach, namely the Restricted Boltzmann Machine. In the second part, we discuss a model-independent and unbiased estimator of symmetric interactions for any system of binary and categorical variables, be it magnetic spins, nodes in a neural network, or gene networks in biology. The generality of this technique is demonstrated analytically and numerically in various examples.

Bio: Ava Khamseh received her PhD in Theoretical Particle Physics from the University of Edinburgh in 2017. She then became a Cross-Disciplinary Fellow (XDF) at the Institute of Genetics and Molecular Medicine at the University of Edinburgh. She is currently a Lecturer in Biomedical Artificial Intelligence, joint between the School of Informatics and IGMM. Her research involves designing experiments and developing causal mathematical, statistical and machine learning methods for applications to cancer biology and large-scale population biomedicine.

2 July 2020

14:00 - 15:00

Video of the colloquium

Eli Ben-Sasson (StarkWare)

18 June 2020

15:00 - 16:00

Video of the colloquium

Aleksander Madry (MIT)

Title: Are All Features Created Equal?

Abstract: Our machine learning models have attained impressive accuracy on many benchmark tasks. Yet, these models remain remarkably brittle---small perturbations of natural inputs can completely degrade their performance. Why is this the case? In this talk, we show that this brittleness can, in part, be attributed to the fact that our models often make decisions in a very different way than humans do. Viewing neural networks as feature extractors, we study how features extracted by neural networks may diverge from those used by humans, and how adversarially robust models seem to make progress towards bridging this gap.

Bio: Aleksander Madry is a Professor of Computer Science in the MIT EECS Department and a principal investigator in the MIT Computer Science and Artificial Intelligence Laboratory (CSAIL). He received his PhD from MIT in 2011 and, prior to joining the MIT faculty, he spent some time at Microsoft Research New England and on the faculty of EPFL. Aleksander’s research interests span algorithms, continuous optimization, science of deep learning and understanding machine learning from a robustness perspective. His work has been recognized with a number of awards, including an NSF CAREER Award, an Alfred P. Sloan Research Fellowship, an ACM Doctoral Dissertation Award Honorable Mention, and 2018 Presburger Award.

16 January 2020

14:00 - 15:00

MSB2.22

Andreas Vlachos (Cambridge)

Title: Automated Fact Checking: a natural language processing perspective

Abstract:
Fact checking is the task of verifying a claim against sources such as knowledge bases and text collections. While this task has been of great importance for journalism, it has recently become of interest to the general public as it is one of the weapons against misinformation. In this talk, I will first discuss the task and what should be the expectations from automated methods for it. Following this, I will present our approach for fact checking simple numerical statements which we were able to learn without explicitly labelled data. Then I will describe how we automated part of the manual process of the debunking website emergent.info, which later evolved into the Fake News Challenge with 50 participants. Finally, I will present the Fact Extraction and Verification shared task, which took place in 2018, as well as the recent second edition which conducted an adversarial evaluation of the proposed approaches.

4 February 2020

10:00 - 11:00
Unusual room: R0.21

Hanan Samet (University of Maryland) -- ACM Distinguished Speaker

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)

Thu 2 May, '19

14:00 - 15:00

Sarah Meiklejohn (UCL)

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 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.