Scope:

This conference plans to provide an exposure to the latest developments in Combinatorics and Theory of Computing where ideas and tools from Algebra and Probability Theory play an important role. In particular, we plan to focus on Algebraic Computation, Communication Complexity and Probabilistic Combinatorics. A brief description of each of these topics is given below.

Algebraic techniques in Computational Complexity

Over the last two decades algebraic techniques have played a central role in computational complexity and in our understanding of randomness in computation. For instance, these methods have led to a better understanding (and better explicit constructions) of codes, expander graphs, extractors, and pseudorandom generators and also contributed to the design of efficient algorithms for computational problems in algebra. They also play an important role in efficient list decoding and also in PCPs. One of the aims of this workshop is to invite leading experts in this area and give state-of-the-art lectures on this topic.

Probabilistic Combinatorics

The use of randomness and probabilistic arguments is one of the exciting developments in mathematics in the recent decades. This method has been impressively successful in Graph Theory, Combinatorics, Number Theory and Theoretical Computer Science. Some of the recent interesting results in combinatorics has been based on this method and no combinatorial argument is in sight for proving these results. This conference will have leading experts in this area speak on the current trends in applying randomness to solve combinatorial problems, study of random combinatorial objects and the application of randomness to the design and analysis of efficient algorithms.

Communication Complexity

Communication Complexity is the study of the information theoretic requirements for computations whose input is distributed over several cooperating agents. It is is a central tool for obtaining lower bounds in several areas, especially in circuit complexity and computation using bounded space. With the advent of quantum computation, a model of quantum communication has also been studied. Several communication models have been defined to handle different applications, and deep combinatorial, algebraic, probabilistic and geometric techniques play an important role in analysing these. Recently, deep combinatorial, algebraic and geometric techniques have been employed to understand communication problems,and there is emerging a set of powerful techniques that bring hitherto inaccessible problems tantalisingly close to resolution. Interestingly, these techniques apply to both the classical and the quantum models.

Conference Program:

The conference will consist of invited talks by eminent speakers. The list of speakers and talk details will appear once they are finalised.

Programme Organisers: