We consider here a large network of $n$ nodes which supports
only the following unreliable basic communication primitive:
when a node requests communication then this request
{\em may fail}, independently of other requests, with probability
$f<1$. Even if it succeeds, the request is answered by returning
a stable link to ... more >>>

We design a $0.795$ approximation algorithm for the Max-Bisection problem
restricted to regular graphs. In the case of three regular graphs our
results imply an approximation ratio of $0.834$.

more >>>

We initiate a general study of pseudo-random implementations
of huge random objects, and apply it to a few areas
in which random objects occur naturally.
For example, a random object being considered may be
a random connected graph, a random bounded-degree graph,
or a random error-correcting code with good ... more >>>

We study the Lovasz number theta along with two further SDP relaxations $\thetI$, $\thetII$
of the independence number and the corresponding relaxations of the
chromatic number on random graphs G(n,p). We prove that \theta is
concentrated about its mean, and that the relaxations of the chromatic
number in the case ... more >>>

We consider the resolution proof complexity of propositional formulas which encode random instances of graph $k$-colorability. We obtain a tradeoff between the graph density and the resolution proof complexity.
For random graphs with linearly many edges we obtain linear-exponential lower bounds on the length of resolution refutations. For any $\epsilon>0$, ... more >>>

A central open question of computational neuroscience is to identify the data structures and algorithms that are used in mammalian cortex to support successive acts of the basic cognitive tasks of memorization and association. This paper addresses the simultaneous challenges of realizing these two distinct tasks with the same data ... more >>>

We study the use of spectral techniques for graph partitioning. Let G=(V,E) be a graph whose vertex set has a ``latent'' partition V_1,...,V_k. Moreover, consider a ``density matrix'' E=(E_vw)_{v,w in V} such that for v in V_i and w in V_j the entry E_{vw} is the fraction of all possible ... more >>>

Kolaitis and Kopparty have shown that for any first-order formula with
parity quantifiers over the language of graphs there is a family of
multi-variate polynomials of constant-degree that agree with the
formula on all but a $2^{-\Omega(n)}$-fraction of the graphs with $n$
vertices. The proof yields a bound on the ... more >>>

Local algorithms on graphs are algorithms that run in parallel on the nodes of a graph to compute some global structural feature of the graph. Such algorithms use only local information available at nodes to determine local aspects of the global structure, while also potentially using some randomness. Recent research ... more >>>

A graph $G$ is called {\em self-ordered}\/ (a.k.a asymmetric) if the identity permutation is its only automorphism.
Equivalently, there is a unique isomorphism from $G$ to any graph that is isomorphic to $G$.
We say that $G=(V,E)$ is {\em robustly self-ordered}\/ if the size of the symmetric difference ... more >>>