Finding cliques in random graphs and the closely related
"planted" clique variant, where a clique of size k is planted in a
random G(n,1/2) graph, have been the focus of substantial study in
algorithm design. Despite much effort, the best known...
In this talk I will describe nondeterministic reductions which
yield new direct product theorems (DPTs) for Boolean circuits. In
our theorems one assumes that a function F is "mildly hard" against
*nondeterministic* circuits of some size s(n) , and...
Galaxies are the visible building blocks of the Universe,
astrophysical laboratories that have profoundly informed our
knowledge of cosmology and nature. Black holes—once a bizarre
mathematical consequence of Einstein’s relativity theory—are
now...
