LMS Computer Science Colloquium

 

The LMS Computer Science Colloquium is an annual day of themed talks on a topical issue at the interface of mathematics and computer science, usually held in November at De Morgan House, London. It is organised by the LMS Computer Science Committee. The event is aimed at PhD students and post-docs, although others are welcome to attend.

Next Computer Science Colloquium: 'Algorithms, Complexity and Logic'

The next colloquium will be held on Thursday 19th November 2020, 10am-4pm, and will be held online. The theme will be 'Algorithms, Complexity and Logic'. The speakers will be as follows:

Nobuko Yoshida (Imperial College London)

Kitty Meeks (Glasgow)

Anupam Das (Birmingham)

Igor Carboni Oliveira (Warwick)

 

Register here for the 2020 Computer Science Colloquium.

Programme

    Introduction to the day by Charlotte Kestner

    10:00 – 11:00 (brief intro from Prudence Wong)

    Anupam Das (Birmingham)

    Title: The size of proofs: from mathematical logic to computational complexity and back

    Abstract: In a nutshell, Proof Complexity is about the size of proofs: given a mathematical theorem, how long is its shortest proof? However, this simple question is intricately linked to fundamental concepts in both mathematical logic and computational complexity. In particular, there is a beautiful three-way correspondence between (weak) theories of arithmetic, complexity classes, and propositional proof systems. This allows us to reframe purely logical problems into algorithmic ones and vice versa. In this talk I will survey some of the key ideas behind Bounded Arithmetic and Proof Complexity, and explain some of the results and approaches that motivate me in these areas.

    11:00 – 11:30 break-out rooms

    11:30 – 12:30 (brief intro from Ornela Dardha)

    Nobuko Yoshida (Imperial College London)

    Title: Session Types: A History and Applications

    Abstract: Session types is a typing discipline for concurrent and distributed processes that can detect errors such as communication mismatches and deadlocks, statically or dynamically. This talk first gives a brief history of session types, along with a very gentle industry-friendly introduction of session types. I then talk how an extension of session types to multiparty interactions (multiparty session types) was discovered under the collaborations with industry. I then give a summary of our recent research developments on session types for verifying distributed, parallel and concurrent programs, and our collaborations with industry partners with demos.

    12:30 – 13:30 lunch break

    13:30 – 14:30 (brief intro from Barnaby Martin)

    Kitty Meeks (Glasgow)

    Title: From decision to approximate counting

    Abstract: Decision problems – those in which the goal is to return an answer of “YES" or “NO" – are at the heart of the theory of computational complexity, and remain the most studied problems in the theoretical algorithms community. However, in many real-world applications it is not enough just to decide whether the problem under consideration admits a solution: we often want to find all solutions, or at least count (either exactly or approximately) their total number. It is clear that finding or counting all solutions is at least as computationally difficult as deciding whether there exists a single solution, and indeed in many cases it is strictly harder even to count approximately the number of solutions than it is to decide whether there exists at least one (assuming P is not equal NP). 

    In this talk I will discuss a restricted family of problems, in which we are interested in solutions of a given size: for example, solutions could be k-vertex subgraphs in a large host graph G that have some specific property (e.g. being connected), or size-k solutions to a database query.  In this setting, although exact counting is strictly harder than decision (assuming standard assumptions in parameterised complexity), the methods typically used to separate approximate counting from decision break down. Indeed, I will describe two randomised approaches that, subject to some additional assumptions, allow efficient decision algorithms for problems of this form to be transformed into efficient algorithms to find or count all solutions. 

    This includes joint work with John Lapinskas (Bristol) and Holger Dell (Frankfurt).

    14:30 – 15:30 (brief intro from Arnold Beckmann)

    Igor Carboni Oliveira (Warwick)

    Title: Kolmogorov complexity, prime numbers, and complexity lower bounds 

    Abstract: Consider the following questions: 

    1. Are there large prime numbers with simple descriptions? 
    2. Is it computationally hard to detect patterns in data? 
    3. Is there a fast deterministic algorithm that, given an integer n, outputs an n-bit prime? 

    Despite the interest of mathematicians and computer scientists, these problems remain far from being solved. In this talk, I will explain how an emerging theory of probabilistic (time-bounded) Kolmogorov complexity leads to new insights and perspectives on some of these questions. 

    15:30 – 16:00 break-out rooms