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

  • 10am: Introduction to the day by Charlotte Kestner
  • 10 – 11: Anupam Das: The size of proofs: from mathematical logic to computational complexity and back (introduction from Prudence Wong)
  • 11 – 11:30: break-out rooms
  • 11:30 – 12:30: Nobuko Yoshida: Session Types: A History and Applications (introduction from Ornela Dardha)
  • 12:30 – 13:30: lunch break
  • 13:30 – 14:30: Kitty Meeks: From decision to approximate counting (introduction from Barnaby Martin)
  • 14:30 – 15:30: Igor Carboni Oliveira: Kolmogorov complexity, prime numbers, and complexity lower bounds (introduction from Arnold Beckmann)
  • 15:30 – 16:00: break-out rooms

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.

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.

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

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.  


Register here for the 2020 Computer Science Colloquium.


Previous Computer Science Colloquiums

The most recent colloquium was held on 13 November 2019 and the topic was Mathematics of Security. The programme for the day, including abstracts, can be accessed here. The speakers and their talks were as follows (links to the presentations are included where available):

Details of the next Computer Science Colloquium will be posted to this page in due course.