Navigating the Deletion Channel

Seminar

Speaker:

Ankur Kulkarni

Organisers:

Vinod M. Prabhakaran

Time:

Thursday, 6 June 2013, 11:00 to 12:00

Venue:

AG-80

Webpage:

https://sites.google.com/site/kulkarniankur/

A deletion channel is communication medium that takes a string of symbols as input, deletes a fixed number of them and outputs the remaining symbols by aligning them without changing their order.

Boolean Monotonicity Testing via an Isoperimetry Result on the Directed Hypercube

Seminar

Speaker:

Deeparnab Chakrabarty

Organisers:

Prahladh Harsha

Time:

Thursday, 2 May 2013, 15:30 to 16:30

Venue:

AG-80

Webpage:

http://research.microsoft.com/en-us/um/people/dechakr/

A Boolean function $f:\{0,1\}^n \to \{0,1\}$ is monotone if $f(x) \geq f(y)$ whenever $x > y$, that is, all coordinates of $x$ dominate those of $y$.

Local Search for Computationally Hard Constraint Satisfaction Problems

Seminar

Speaker:

Abdul Sattar

Organisers:

R K Shyamasundar

Time:

Monday, 29 April 2013, 10:30 to 11:30

Venue:

AG-80

Webpage:

http://www.griffith.edu.au/professional-page/abdul-sattar

Since the emergence of Artificial Intelligence (AI) as a new field of modern science and engineering about 6 decades ago, concerted efforts have been made on designing and developing expressively adequate languages to represent knowledge about re

Ramanujan Graphs of All Degrees

Seminar

Speaker:

Nikhil Srivastava

Organisers:

Prahladh Harsha

Time:

Monday, 6 May 2013, 16:30 to 17:30

Venue:

AG-80

Webpage:

http://research.microsoft.com/en-us/people/niksri/

We prove that there exist infinite families of bipartite Ramanujan graphs of every degree bigger than 2. We do this by proving a variant of a conjecture of Bilu and Linial about the existence of good 2-lifts of every graph.

A Survey on Uniform Hardness Amplification in NP

Project Seminar

Speaker:

Sagnik Mukhopadhyay, TIFR

Organisers:

Prahladh Harsha

Time:

Wednesday, 17 April 2013, 09:30 to 11:30

Venue:

AG-80

Webpage:

http://www.tcs.tifr.res.in/~sagnik_m/

We investigate the following question: If NP contains functions which are slightly hard to compute on average then does NP also contain function which is very hard to compute on average?

The Strahler Analysis of Binary Trees in Computer Science and in Other Sciences

Seminar

Speaker:

Xavier Viennot

Organisers:

Jaikumar Radhakrishnan

Time:

Wednesday, 27 February 2013, 16:00 to 17:00

Venue:

AG-80

Webpage:

http://www.labri.fr/perso/viennot/

Computer scientists defined the Strahler number of a binary tree in relation with the minimum number of registers needed for the computation of an arithmetical expression.