Yuval Peres (Microsoft research) will visit Moscow for two days, June 28 and 29, and will give two talks
.
The first one
the general interest talk – will take place on
June 28, 2018 at 15:00, in the Skoltech Cohort Space (Blue building, 4-th floor (3 Nobel street)
Title :
Gravitational allocation to uniform points on the sphere
Speaker :
Yuval Peres / Microsoft Research
Abstract :
Given n uniform points on the surface of a two-dimensional sphere, how can we partition the sphere fairly among them? “Fairly” means that each region has the same area. It turns out that if the given points apply a two-dimensional gravity force to the rest of the sphere, then the basins of attraction for the resulting gradient flow yield such a partition ─ with exactly equal areas, no matter how the points are distributed. (See the cover of
the AMS Notices.
Our main result is that this partition minimizes, up to a bounded factor, the average distance between points in the same cell. I will also present an application to almost optimal matching of n uniform blue points to n uniform red points on the sphere, connecting to a classical result of Ajtai, Komlos and Tusnady (Combinatorica 1984). I will emphasize three open problems on the diameters of the basins and the behavior of greedy and electrostatic matching schemes / Joint work with Nina Holden and Alex Zhai
The second talk
will happen at Independent University of Moscow (11 Bolshoy Vlasyevskiy Pereulok) on
June 29, 2018 at 14:40
Two topics will be covered:
Title:
Rigidity and Tolerance for Perturbed Lattices
Speaker:
Yuval Peres / Microsoft Research
Abstract:
Consider a perturbed lattice {v+Y_v} obtained by adding IID d-dimensional Gaussian variables {Y_v} to the lattice points in Z^d.
Suppose that one point, say Y_0, is removed from this perturbed lattice; is it possible for an observer, who sees just the remaining points, to detect that a point is missing?
In one and two dimensions, the answer is positive: the two point processes (before and after Y_0 is removed) can be distinguished by counting points in a large ball and averaging over its radius (cf. Sodin-Tsireslon (2004) and Holroyd and Soo (2011) ). The situation in higher dimensions is more delicate, as this counting approach fails; our solution depends on a game-theoretic idea, in one direction, and on the unpredictable paths constructed by Benjamini, Pemantle and the speaker (1998), in the other.
Title:
Trace reconstruction for the deletion channel
Speaker:
Yuval Peres / Microsoft Research
Abstract:
In the trace reconstruction problem, an unknown string x of n bits is observed through the deletion channel, which deletes each bit with some constant probability q, yielding a contracted string. How many independent outputs (traces) of the deletion channel are needed to reconstruct x with high probability?
The best lower bound known is linear in n. Until 2016, the best upper bound was exponential in the square root of $n$. In earlier work with F. Nazarov (STOC 2017), we improved the square root to a cube root using statistics of individual output bits and some inequalities for Littlewood polynomials on the unit circle. This bound is sharp for reconstruction algorithms that only use this statistical information. (Similar results were obtained independently and concurrently by De, [UTF-8?]OБ─≥Donnellб═and Servedio). Our main new result: If the string x is random, then a subpolynomial number of traces suffices; the proof relies on comparison to a random walk / Joint works with Alex Zhai, FOCS 2017 and with Nina Holden & Robin Pemantle, COLT 2017
Look here
yuvalperes.com
wikipedia/Yuval Peres
to find more about scientific interests of Yuval