IndoUK workshop on Computational Complexity Theory
59 January, 2015
EPSRCDST
IndoUK Initiative in Applied Mathematics




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, randomaccessmemory
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
smalltime (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:
 Boolean circuit complexity: Results in the recent past show that
exact algorithms for wellchosen restrictions of some of the hardest
problems in NP (in particular, SATsolvers for special classes of
formulas) can be exploited to obtain lower bounds against small
circuit classes.
 Algebraic circuit complexity: Obtaining lower bounds in this
framework is an essential step in the journey towards obtaining
lower bounds in the Boolean framework. There has been a flurry of
results in this area in the last few years, and it appears that we
are tantalisingly close to a major breakthrough.
 Proof complexity: This area focuses on the power and limitations
of theorem proving procedures. Recent work ais leading to a better
understanding of why certain SATsolving heuristics perform well in
practice.
There is a vibrant and growing community of complexity theorists in
India, with research interests spanning most subareas of complexity
theory. There is a a small but strong community of complexity
theorists in the UK, working in diverse subareas of the
field. Bringing these researchers together, against the backdrop of
recent progress, has the potential to kickstart longtermsustainable
interactions between the groups, and help advance our
understanding in the field. This workshop is being organised with the
twin goals of
 providing the space for intensive dialogues during the workshop,
possibly leading to some problemsolving advances during the
workshop itself, and also
 fostering collaborations between researchers especially across
the two countries.
Participants from UK
Participants from India
Participants from India (graduate students)
From Chennai
 Sudeshna Kolay (IMSc)
 Diptapriyo Majumdar (IMSc)
 Pranabendu Misra (IMSc)
 P Fahad (IMSc)
 Ashutosh Rai (IMSc)
 S Raja (IMSc)
 Gaurav Rattan (IMSc)
 Nitin Saurabh (IMSc)
 Anil Shukla (IMSc)
 Anuj Tawari (IMSc)
 Nikhil Balaji (CMI)
 Suryajith Chillara (CMI)
 Anish Mukherjee (CMI)
 Aditya Potukuchi (CMI)
 Ramya C. (IITM)
 Ankit Chauhan (IITM)
 Anant Dhayal (IITM)
 Purnata Ghosal (IITM)
 Balagopal Komarath (IITM)
 Sajin Koroth (IITM)
 Dinesh Krishnamoorthy (IITM)
 Saurabh Sawlani (IITM)
From outside Chennai
 Vineet Nair (IISc)
 Anup Bhattacharya (IITD)
 Shubham Sahai (IITK)
 Rohit Gurjar (IITK)
 Arpita Korwar (IITK)
 Anurag Pandey (IITK)
 Rishabh Vaid (IITK)
 Nikhil Mande (TIFR)
 Tulasi Mohan Molli (TIFR)
 Sagnik Mukhopadhyay (TIFR)
 Swagato Sanyal (TIFR)
Venue for talks: Alladi Ramakrishnan Hall (Room 423)
Accommodation: at
Hotel Asiana Place (UK participants) and at IMSc Guest House
(Indian nonChennai participants).
Workshop Dinner: Green
Meadows Resort