## Time:

## Venue:

Determining the chromatic number of a graph is known to be NP-hard. We will consider the problem of coloring a $k$-colorable graph on n vertices with $n^{\alpha}$ colors (where $\alpha < 1$).

Speaker:

Girish Varma, TIFR

Monday, 14 November 2011, 16:00 to 17:00

Determining the chromatic number of a graph is known to be NP-hard. We will consider the problem of coloring a $k$-colorable graph on n vertices with $n^{\alpha}$ colors (where $\alpha < 1$).

Monday, 24 October 2011, 16:00 to 17:00

Considering the large volume of sequence data that many computational biology applications must deal with, proper organization of the data to facilitate fast access is important to achieve desirable run-times.

<p>Pinaki Mazumder<br />
University of Michigan<br />
Department of Electrical Engineering<br />
and Computer Science<br />
2260 Howard Avenue<br />
Ann Arbor, MI 48109-2121<br />
United States of America</p>

Thursday, 20 October 2011, 11:30 to 12:30

Conventional shrinking methods to improve VLSI chip performance by continual scaling of device and interconnect geometries may allow CMOS juggernaut to reach about 22 nm nodes.

Ehud Shapiro
Department of Computer Science and
Applied Math and Department of
Biological Chemistry
Weizmann

Monday, 3 October 2011 (All day)

The cell lineage tree of a person captures the history of the personâ€™s cells since conception.

<p>Chien-Chung Huang<br />
Humboldt-UniversitÃ¤t zu<br />
Berlin Institut fÃ¼r Informatik 10099<br />
Berlin Germany</p>

Monday, 26 September 2011 (All day)

Our input is a graph $G = (V, E)$ where each vertex ranks its neighbors in a strict order of preference. The problem is to compute a matching in $G$ that captures the preferences of the vertices in a popular way.

Devendra Desai
Rutgers University
Department of Computer Science
110 Frelinghuysen Road
Piscataway, NJ 08854-

Friday, 12 August 2011 (All day)

The 'bisection width' of a graph is defined as the minumum number of edges that need to be removed to partition the graph into two equal halves. If the graph is 'sparse', then we don't expect this quantity to be large.

Shaunak Sen
California Institute of Technology
Computing and Mathematical Sciences
Pasadena, CA
United States

Thursday, 11 August 2011 (All day)

Diverse engineering functions can be generated when simple modules are connected in different configurations. Similar modules also exist in biology, for example, within circuits of interacting molecules that map to diverse cellular behavior.

Venkat Anantharam
University of California, Berkeley
Department of Electrical Engineering
and Computer Science
<br

Tuesday, 9 August 2011 (All day)

Insurance transfers losses associated with risks to the insurer for a price, the premium. We adopt the collective risk approach. Namely, we abstract the problem to include just two agents: the insured and the insurer.

Bodhayan Roy
Tata Institute of Fundamental Research
School of Technology and Computer Science
Homi Bhabha Road
<br

Thursday, 4 August 2011 (All day)

We explore the visibility graph of a point set. We list some classical works on configurations of points and straight lines on the plain and then proceed to deduce some combinatorial properties of point visibility graphs.

Ratnik Gandhi
Tata Institute of Fundamental Research
School of Technology and Computer Science
Homi Bhabha Road
<b

Wednesday, 3 August 2011 (All day)

We present approaches for constructing finite normal form games that ensure constructed games have desirable outcomes.