Computer Science Colloquium
Organiser: Tom Gur
Colloquia currently take place online. Additional titles and abstracts will be added as details become available.
Next Colloquium
4 February 202114:00 - 15:00 |
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. |
Current Term
Second term, 2020-2021:
21 January 202114:00 - 15:00 |
Arthur Gervais (Imperial College; Liquidity Network) Title: Flash Loans for Fun and Profit
Abstract: Credit allows a lender to loan out surplus capital to a borrower. In the traditional economy, credit bears the risk that the borrower may default on its debt, the lender hence requires upfront collateral from the borrower, plus interest fee payments. Due to the atomicity of blockchain transactions, lenders can offer flash loans, i.e., loans that are only valid within one transaction and must be repaid by the end of that transaction. This concept has lead to a number of interesting attack possibilities, some of which were exploited in February 2020. In this talk we will explore the implication of transaction atomicity and flash loans for the nascent decentralized finance (DeFi) ecosystem. We will analyze two existing attacks with ROIs beyond 500k% and formulate finding the attack parameters as an optimization problem over the state of the underlying Ethereum blockchain and the state of the DeFi ecosystem. We will show how malicious adversaries can efficiently maximize an attack profit and hence damage the DeFi ecosystem further. Specifically, we will present how two previously executed attacks can be “boosted” to result in a profit of 829.5k USD and 1.1M USD, respectively, which is a boost of 2.37× and 1.73×, respectively. Bio: Arthur Gervais is a Lecturer (equivalent Assistant Professor) at Imperial College London, and the founder of Liquidity Network. He's passionate about information security and worked since 2012 on blockchain related topics, with a recent focus on Decentralized Finance (DeFi). |
4 February 202114:00 - 15:00 |
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. |
4 March 202114:00 - 15:00 |
Title: TBA |
15 March 202115:00 - 16:00 |
Title: TBA |
Past terms
First term, 2020-2021:
29 October 202014:00 - 15:00 |
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 202017: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 202014: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 202014:00 - 15:00 |
Ava Khamseh (University of Edinburgh) Title: Higher-order interactions in statistical physics, machine learning and biomedicine |
Third term, 2019-2020:
2 July 202014:00 - 15:00 |
Title: Blockchain Scalability and Privacy via Scalable and Transparent zk-STARKs
Abstract: Two of the biggest challenges of blockchains like Bitcoin and Ethereum are (1) scalability - growing thoughput 10x, 100x, 1000x, ... and (2) maintaining privacy. Scalable ZK proof systems can solve both problems. This talk will recount the theory-to-practice journey of ZK proofs and describes questions in algebraic coding theory whose resolution will help improve scalability and privacy even more. Bio: Eli is a co-founder and president of StarkWare, and Chairman of its Board of Directors. Eli has been passionate about the theory (“moon math”) and realization of transparent computational integrity since 2001, when he was a post-doctoral researcher at MIT and Harvard University, after completing his PhD in CS at the Hebrew University. Prior to co-founding StarkWare, Eli was a Professor of Computer Science at Technion – Israel Institute of Technology, which he joined in 2005. He is also a co-inventor of the Zerocash decentralized anonymous payment system and a founding scientist of the Electric Coin Company (aka the Zcash company). |
18 June 202015:00 - 16:00 |
Title: Are All Features Created Equal? |
Second term, 2019-2020:
16 January 202014:00 - 15:00 MSB2.22 |
Title: Automated Fact Checking: a natural language processing perspective Abstract: |
4 February 202010:00 - 11:00 |
Hanan Samet (University of Maryland) -- ACM Distinguished Speaker Title: Reading News with Maps by Exploiting Spatial Synonyms Abstract: |
6 February 202014:00 - 15:00MSB2.22 |
Title: Multiparty Privacy and AI Security & Privacy Abstract: |
27 February 202014:00 - 15:00 |
Title: Modulated Bayesian Optimisation Abstract: |
12 March 202014:00 - 15:00 |
Title: Testing Discrete Distributions -- a CS Retrospective Abstract: Making inferences about the distributional properties of data is arguably one of the most fundamental classes of data analysis tasks. The study of such inferences has been a scientific endeavour for a long time, typically, by statistics and information theory. In the last two decades, testing problems for distributions, especially, on discrete domains have been studied also in the theoretical computer science community, often from a slightly different perspective. The primary objective in this line of research is characterising the number of samples needed, in terms of the domain size or some function of the distributions involved, to perform a given inference task reliably. In this talk, I will present an overview of this very active field of research, describing some basic models and problems, landmark results, and future directions. |
First term, 2019-2020:
10 October 201914:00 - 15:00 |
Sunil Prabhakar (Purdue University) |
24 October 201914:00 - 15:00 |
Evangelia Kalyvianaki (Cambridge)Title: THEMIS -- Fairness in Federated Stream Processing under Overload Abstract: |
7 November 201914:00 - 15:00 |
Ata Kaban (Birmingham)Title: Uncovering structure with randomness for learning in high dimensions Abstract: |
21 November 201914:00 - 15:00 |
Samson Abramsky (Oxford)Title: Non-classicality, quantum resources and quantum advantage (slides) Abstract: Our focus here is on quantum resources which take the form of non-local, or more generally \emph{contextual}, correlations. Contextuality is one of the key signatures of non-classicality in quantum mechanics and has been shown to be a necessary ingredient for quantum advantage in a range of information processing tasks. We will describe a notion of simulation between quantum resources, and more generally between resources described in terms of contextual correlations, in the ``sheaf-theoretic'' framework for contextuality (Abramsky-Brandenburger). The talk will be essentially self-contained, introducing the various notions we will discuss. |
3 December 201915:00 - 16:00 |
Jakob Nikolas Kather (University Hospital Aachen)Title: Deep Learning for Precision Oncology Abstract: |
Third term, 2018-2019:
Thu 2 May, '1914: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, '1914: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, '1914:00 - 15:00 |
Andreas Damianou (Amazon, Cambridge)(This talk will take place in CS1.04) Title: Probability and uncertainty in Deep Learning Abstract: |
Thu 20 Jun, '1914:00 - 15:00 |
Mario Berta (Imperial College London)Title: Quantum Technologies for Cryptography Abstract: |
Thu 11 Jul, '1911:00 - 12:00 |
Radu Calinescu (University of York)Title: Learning, synthesis and efficient analysis of probabilistic models Abstract: |