Indo-UK workshop on Computational Complexity Theory

5-9 January, 2015

Venue: The Institute of Mathematical Sciences, Chennai

EPSRC-DST Indo-UK Initiative in Applied Mathematics

Link to Videos of Talks
Practical information

With computation in various forms having become ubiquitous in modern society, understanding fundamental limits to computability under various resource restrictions is becoming an increasingly relevant topic of study within theoretical computer science. Computational complexity, a field at the intersection of computer science and applied mathematics, aims to identify the precise complexity of computational problems in different computational models such as Turing machines, Boolean and algebraic circuits, random-access-memory machines, etc. Each model comes with its own set of relevant resources, and the connections between resources across models is often nuanced and complex. Attempts to understand these connections has often led to the identification and formulation of fundamental notions concerning computation. While these studies are driven by the need to understand computation, some of these notions are central to mathematics as well. The notion of what constitutes a proof, and in particular, what constitutes an easily verifiable proof, has evolved over the years in many ways, starting from the most conservative notion of a deterministic small-time (polynomial time) verifier, to that of randomized verification with low error probability, to verification with interaction, to probabilistically checkable proofs, locally checkable proofs, and so on. A central question in complexity theory is whether the complexity classes P and NP coincide. While we are quite far from resolving this question, there has been progress in the recent past on several fronts. For example:

There is a vibrant and growing community of complexity theorists in India, with research interests spanning most sub-areas of complexity theory. There is a a small but strong community of complexity theorists in the UK, working in diverse sub-areas of the field. Bringing these researchers together, against the backdrop of recent progress, has the potential to kickstart long-term-sustainable interactions between the groups, and help advance our understanding in the field. This workshop is being organised with the twin goals of


Participants from UK

Participants from India

Participants from India (graduate students)

From Chennai
From outside Chennai

Practical information

Venue for talks: Alladi Ramakrishnan Hall (Room 423)

Accommodation: at Hotel Asiana Place (UK participants) and at IMSc Guest House (Indian non-Chennai participants).

Workshop Dinner: Green Meadows Resort