A property of finite graphs is called nondeterministically
testable if it has a "certificate'' such that once the certificate
is specified, its correctness can be verified by random local
testing. In this talk we consider certificates that consist...
A blue mushroom cloud fills the page, its contour traced by the
comet-like tails of shrieking heads whose gaping mouths spew out
furious curses in a rain of profanity over needle-stiff bodies
littering the ground. This lecture by Mignon Nixon...
The goal of the Balanced Separator problem is to find a balanced
cut in a given graph G(V,E), while minimizing the number of edges
that cross the cut. It is a fundamental problem with applications
in clustering, image segmentation, community...
We study the list-decodability of multiplicity codes.
These codes, which are based on evaluations of high-degree
polynomials and their derivatives, have rate approaching 1 while
simultaneously allowing for sublinear-time error-correction. In
this...
Heegaard Floer homology groups were recently introduced by
Ozsvath and Szabo to study properties of 3-manifolds and knots in
them. The definition of the invariants rests on delicate
holomorphic geometry, making the actual computations
cumbersome...
Heegaard Floer homology groups were recently introduced by
Ozsvath and Szabo to study properties of 3-manifolds and knots in
them. The definition of the invariants rests on delicate
holomorphic geometry, making the actual computations
cumbersome...
