Association Schemes, Non-Commutative Polynomials and Lasserre Lower Bounds for Planted Clique
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 polynomial-time algorithms only solve the problem for k ~ sqrt(n). Here we show that beating sqrt(n) would require substantially new algorithmic ideas, by proving a lower bound for the problem in the Lasserre hierarchy, the most powerful class of semi-de finite programming algorithms we know of.
Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers
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 concludes that the t-fold direct product F^t is "extremely hard" against probabilistic circuits of only polynomially smaller size s'(n) . The main advantage of these results compared with previous DPTs is the strength of the size bound in our conclusion.
Planar Ising Model: Discrete and Continuous Structures
Tight Bounds for Set Disjointness in the Message-Passing Model
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, and communication complexity lower bounds have been used extensively to obtain lower bounds on various distributed problems. However, almost all applications of communication complexity lower bounds in distributed computing use two-party lower bounds, despite the fact that distributed computation usually involves many players.
A Non-Isotropic Mechanism for the Formation of Trapped Surfaces
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 (possibly flat everywhere else) whose future development contains a trapped surface. This extends considerably the previous result of Christodoulou which required instead a uniform condition along all null geodesic generators.
Combinatorial Walrasian Equilibrium
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 natural relaxation of Walrasian equilibrium, an appealing and robust notion of market pricing equilibrium. The only difference between a CWE and a (non-combinatorial) WE is the ability for the seller to pre-bundle the items prior to sale. This innocuous and natural bundling operation opens up a plethora of algorithmic challenges and opportunities.
Cryptography and Preventing Collusion in Second Price (Vickery) Auctions
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 preventing collusion in second-price auctions.
Integrable Stochastic Particle Systems and Macdonald Processes
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 be universal statistics and phenomena. In this talk we focus on two different integrable exclusion processes: q-TASEP and ASEP.
On the Existence of Global Solutions of Certain Fluid Models
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).
Conformal Invariants from Nodal Sets
We study conformal invariants that arise from nodal sets and negative eigenvalues of conformally covariant operators, which include the Yamabe and Paneitz operators. We give several applications to curvature prescription problems. We establish a version in conformal geometry of Courant's Nodal Domain Theorem. We also show that on any manifold of dimension n >=3, there exist many metrics for which our invariants are nontrivial. We prove that the Yamabe operator can have an arbitrarily large number of negative eigenvalues on any manifold of dimension n >=3.