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...
In many distributed systems, the cost of computation is
dominated by the cost of communication between the machines
participating in the computation. Communication complexity is
therefore a very useful tool in understanding distributed
computation...
On March 21, 2013, the most detailed map of the infant universe
to date was publicly released, showing relic radiation from the Big
Bang, imprinted when the universe was just 380,000 years old. This
was the first release of cosmological data from...
A continuous representation of a profinite group induces a
continuous pseudorepresentation, where a pseudorepresentation is
the data of the
characteristic polynomial coefficients. We discuss the geometry of
the resulting map from the moduli formal...