EPSRC Reference: 
EP/V050842/1 
Title: 
Algorithms, Dynamics and Connections with Phase Transitions 
Principal Investigator: 
Efthymiou, Dr C 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Computer Science 
Organisation: 
University of Warwick 
Scheme: 
New Investigator Award 
Starts: 
01 July 2021 
Ends: 
30 June 2024 
Value (£): 
309,801

EPSRC Research Topic Classifications: 
Fundamentals of Computing 
Mathematical Physics 

EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 
Panel Date  Panel Name  Outcome 
23 Mar 2021

EPSRC ICT Prioritisation Panel March 2021

Announced


Summary on Grant Application Form 
The project focuses on an interplay between algorithms and phase transitions.
We consider computational problems in the class NP. These are abstractions of a tremendous wealth of important practical problems in communication networks, biology, coding theory and many others. Here, we focus on random instances of problems in NP, rather than worst case ones. This approach is motivated in many ways. For example, dealing with random instances can be a part of the problem like in coding theory. In other cases, random instances give rise to what we call statistical  computational tradeoffs. That is, adjusting the parameters of the problem we generate families of instances whose tractability varies from efficiently solvable to (what is believed to be) computationally hard. Here we particularly consider instances of problems known as random Constraint Satisfaction Problems (rCSP). These are random instances of classical combinatorial, or algebraic problems such as the graph colouring, ksatisfiability etc.
Physicists, have been studying rCSPs as models of disordered systems. They have developed ingenious alas mathematically nonrigorous ideas which over the past decade have grown into a toolkit called the Cavity Method. Cavity's predictions are related to the size and the geometry of the solution space of a rCSP. This allows us to understand and appreciate the challenges we have to deal in our algorithmic problems.
In this project we plan to study sampling algorithms for Gibbs distributions in rCSPs. These distributions are defined over the solution space of the rCSP, e.g. for graph colourings this is the uniform distribution over the kcolourings of the underlying graph. We focus on two different approaches for sampling. The first one is based on the Markov Chain Monte Carlo (MCMC) method. The natural question there is how fast the MCMC dynamics mixes for a given set of the parameters. The MCMC algorithms are simple to implement Markov chains and usually they have a notable empirical performance. However, analysing them can be challenging.
We also intend to study a nonMCMC approach to sampling. The plan is to use the approach introduced in [Efthymiou SODA2012]. This algorithm is very different than the MCMC ones. iIt is very simple to implement and describe, with a provably notable performance. There are a lot of very interesting directions that worth exploring with this approach.
Furthermore, we plan to investigate the soundness of certain predictions from the Cavity method.
Gibbs distributions: The natural way of studying Gibbs distributions is in terms of spatial correlation decay. There are several, different, notions of spatial mixing which arise naturally in the study. Some of these notions seem to be related to the performance of algorithms. We plan to study spatial mixing for nonsymmetric distributions on random graphs with focus on the socalled reconstruction threshold. We also intend to study nonreconstruction problem for spinglasses, e.g., the EdwardsAnderson model. We focus on nonreconstruction because the onset of reconstruction signifies that sampling and search algorithms for rCSP stop being polynomial.
Free Energy: Many natural inference and learning problems are cast naturally as rCSP, e.g., Stochastic Block Model (SBM) for networks inference, models of neurones like Ising Perceptron, the committee machine. It a natural to study these models in terms of their free energy. We intend to use the formalism of free energy to establish information lower bounds for inference algorithms for the nonsymmetric SBM and study basic properties of physics' models of neural networks, including capacity estimates, or finding their energy landscape.

Key Findings 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Potential use in nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

Date Materialised 


Sectors submitted by the Researcher 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Project URL: 

Further Information: 

Organisation Website: 
http://www.warwick.ac.uk 