Alladi Ramakrishnan Hall

The complexity of computation, of communication, and of proofs.

Meena Mahajan

IMSc

The notion of algorithmic computation is centuries old, as is the quest for efficient computation. A precise mathematical formulation of what can be considered efficient lies at the heart of the field of computational complexity.

The rules of logical reasoning, the art of debate, the nature of proof -- these too have been objects of study for centuries. The field of proof complexity seeks to understand how long a proof needs to be, if it adheres to the syntax and the rule set of a specific proof system.

When multiple agents are involved in computation, as is increasingly often the case, the exchange of information between agents merits closer attention. Communication complexity focuses exclusively on analysing the amount of commmunication required.

Three different themes - algorithmic computation, logical reasoning, and the sharing of information - all viewed from the lens of complexity. This talk will highlight some intriguing and sometimes unexpected interconnections between these areas.