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...
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...
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...
I present a new, fully anisotropic, criterion for formation of
trapped surfaces in vacuum obtained in collaboration with J. Luk
and I. Rodnianski. We provide conditions on null data, concentrated
in a neighborhood of a short null geodesic segment...
We study algorithms for combinatorial market design problems,
where a collection of objects are priced and sold to potential
buyers subject to equilibrium constraints. We introduce the notion
of a combinatorial Walrasian equilibium (CWE) as a...
We present practically efficient methods for proving correctness
of announced results of a computation while keeping input and
intermediate values information theoretically secret. These methods
are applied to solve the long standing problem of...
A large class of one dimensional stochastic particle systems are
predicted to share the same universal long-time/large-scale
behavior. By studying certain integrable models within this
(Kardar-Parisi-Zhang) universality class we access what
should...
I will discuss recent work on the global stability of the
Euler-Maxwell equations in 3D (joint work with Guo and Pausader),
and of the gravity water-wave system in 2D (joint work with
Pusateri).