New York University, USA
The analysis of algorithm performance in the worst-case has long been the gold standard of theoretical computer science: it provides a simple, compelling, and robust model, which can often be predictive as well as descriptive. That said, in recent years we have seen an exciting surge in analyzing algorithms using models that go beyond the worst case. Particularly, how can we use ideas from machine learning to inform algorithm design?
In this talk we will discuss some of the results and techniques that come out of this endeavor, in both offline and online settings. For example, we will study covering problems like set cover, load balancing problems like scheduling jobs of machines, and cut problems. We will see some of the modeling decisions in beyond worst-case frameworks, as well as the algorithmic ideas---some old, some new---that can be used to give more nuanced guarantees for these classical problems, complementing our understanding of these problems in the worst-case settings.
Tel Aviv Univeristy, Israel
A property testing algorithm is required to accept objects that have a prespecified property P and reject those that are relatively far from having P. To this end it is given query (or sampling) access to the object, and is allowed a small failure probability. Its query/sample complexity is required to be sublinear in the size of the object. A tolerant testing algorithm is required to also accept objects that are relatively close to having the property (while still rejecting those that are far), and a distance-approximation algorithm is required to approximate the distance to having a property. In this talk I will present several tolerant testing / distance approximation algorithms for a variety of object-types and properties as well as discuss some hardness results. Examples include monotonicity of functions, connectivity of graphs and subsequence freeness.
Stanford University, USA
Coding theory is the study of error-correcting codes, a fundamental tool used to protect data from noise. In coding theory, list-recovery refers to the ability to correct from a certain type of uncertainty, where multiple possibilities are received for each symbol that is sent. List-recovery has found many applications throughout computer science (and not just for protecting data from noise), for example in algorithm design, group testing, pseudorandomness, and cryptography. In this lecture, I'll give an overview of list-recovery in coding theory and discuss some constructions as well as some applications. I'll also discuss open problems and mention some motivating non-applications: That is, things that would be applications, if only we could solve some open problems about list-recovery!
Korea Advanced Institute of Science & Technology (KAIST), Korea
A few years ago, during a sabbatical visit to a discrete mathematics group, I was encouraged by experts in combinatorics to study Razborov’s flag algebras. They highlighted the power of the flag algebras as a computational method for solving problems in extremal combinatorics — a field where the flag algebras have yielded some of the best-known results for undirected graphs, directed graphs, hypergraphs, and permutations. They also explained that the flag algebras had deep connections to logic and optimisation, encoding finite combinatorial objects and constraints as finite structures and universally-quantified formulas, and exploiting semidefinite programming to generate bounds in extremal combinatorics automatically. They conjectured that the flag algebras could suggest effective ways to use logic, programming languages, and machine learning for generating mathematical results automatically.
In this talk, I will describe what I have learnt by following this recommendation for about a year. My goal is to introduce the key ideas behind the flag algebras and their achievements in a way that is accessible to a non-expert audience in theoretical computer science. If time permits, I will also discuss our ongoing work on formalising the flag algebras in the Lean theorem prover.
