ICTS

Theoretical computer science in general, and computational complexity theory in particular, offers a new lens to look at the other natural and mathematical sciences, and is having a significant impact in those other fields. The main goal of computational complexity theory is the study of the (in)feasibility of  efficient computation. Proof complexity, originating from mathematical logic, examines the strength of logical reasoning approaches rather than directly reasoning with computation. The Cook-Reckhow program aims to ultimately show that in every propositional proof system, there exist true statements that do not have short efficiently verifiable proofs; this is equivalent to separating NP from coNP, an even  harder problem than the notorious P=?NP problem.  The modern networked world with shared resources drives home the point that both computation and communication are equally valued resources.  Complexity theorists have increasingly realized that the study of communication bottlenecks, in a simple model proposed by Yao 40 years ago, often holds the key to proving the non-existence of efficient algorithms. This happens in a remarkable variety of situations.

The strands of circuit complexity, query/communication complexity, and proof complexity have a lot to offer each other in terms of tools, techniques, and questions. In the last decade, the interplay between these strands has really flourished – communication complexity theoretic techniques have been heavily used in propositional proof complexity; lower bounds on the sizes of proofs, via communication complexity arguments, have implied lower bounds on size of monotone circuits; lifting theorems have allowed non-trivial transfer of lower bounds across models, etc. 

In this 2-week program, the first week will be in the form of a boot camp, with a series of lectures on each of the three strands mentioned above. The second week will feature research talks, giving participants exposure to current developments in the areas.

Eligibility Criteria: Applicants are expected to be researchers, post-doctoral and doctoral research scholars, and masters  students, with adequate grounding in computational complexity and /or proof complexity. In exceptional cases, and subject to availability of space, undergraduate students with exposure to these topics may also be considered.

Accommodation will be provided for outstation participants at our on-campus guest house.

ICTS is committed to building an environment that is inclusive, non-discriminatory and welcoming of diverse individuals. We especially encourage the participation of women and other under-represented groups.