We show that it is possible to encode any communication protocol between two parties so that the protocol succeeds even if a (1/4 − epsilon) fraction of all symbols transmitted by the parties are corrupted adversarially, at a cost of increasing th
<p><a href="http://www.cs.duke.edu/~bsayan/">Sayan Bhattacharya</a><br />
Duke University<br />
Department of Computer Science<br />
N303, North Building<br />
304 Research Drive<br />
Durham, NC 27708<br />
United States of America</p>
Suppose we want to cluster scientists into different groups such that in each group scientists have some research interest in common. The data available to us is the coauthor relationships. How do we classify using spectral clustering ?
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$).
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>
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.
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.
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.
