Simons Collaboration on Algorithms and Geometry Monthly Meeting, February 2020

Nathan Keller
Local tail inequalities, biased halfspaces, and noise sensitivity

Weighted sums of Rademacher random variables (namely, \(X= \sum a_i x_i\), where \(\sum a_i^2=1\) and \(\{x_i\}\) are i.i.d. random variables such that \(\Pr[x_i=1]=\Pr[x_i=-1]=1/2\)), were studied extensively. Local tail inequalities for such variables compare the tail probabilities \(\Pr[X>t]\) and \(\Pr[X>t+\delta]\). An example is the following inequality (Devroye & Lugosi, 2008): If \(\Pr[X>t]=\epsilon\), then \(\Pr[X>t+\delta] \leq \epsilon/2\) holds for \(\delta \leq c/\sqrt{ \log{1/\epsilon}}\), where \(c\) is a universal constant.

We present new inequalities of this type and apply them to obtain results on biased (Boolean) halfspaces, noise sensitivity of Boolean functions, and correlation inequalities. In particular, we determine the exact asymptotic order of the first-level Fourier weight and of the maximal influence of a Boolean halfspace \(1\{\sum a_i x_i >t\}\), providing a sharp generalization of theorems of Matulef, O’Donnell, Rubinfeld, and Servedio. We discuss possible extensions and applications of our methods.

Joint work with Ohad Klein.
 

Chris Bishop
Fast conformal mapping

Both this and the following talk are colloquium style overviews, aiming to show how disparate areas come together in certain computational problems. I will start with the definition of harmonic measure and its connection to conformal mappings. I plan to discuss a few methods for computing conformal maps including my own ‘fast mapping algorithm’ whose formulation uses ideas from computational geometry (the medial axis), and ideas from quasiconformal mapping and hyperbolic manifolds to measure and prove convergence. In particular, this gives a linear time method to approximate the parameters in the Schwarz-Christoffel formula (linear in the number of vertices of the image polygon, with multiplicative constant that depends on the desired accuracy). At the end I will mention an application to optimal quad-meshing of planar domains.
 

Chris Bishop
Optimal triangulation and quad-meshing

Picking up where the last talk ended, I will discuss what is known about optimal quad-meshing and optimal triangulation of planar domains. Here optimal refers to both the number of elements needed and the quality of these elements in terms of keeping angles bounded away from 0 and 180 degrees (well-shaped mesh elements are important in various applications). Also important is the difference between meshing a domain whose boundary is a simple polygon (the easy case) or a planar straight line graph (harder, since there can be holes, omitted points, slits,…). For quad-meshes the optimal lower and upper angle bounds are 60 and 120 degrees and the optimal size is O(n) or O(n^2) for simply polygons and PSLGs respectively. Sharp algorithms are known in both cases. For triangulations, the situation is less complete. It is easy to see that 90 degrees (non-obtuse triangulation) is the best possible upper angle bound and that no positive lower bound is possible, but only recently has a polynomial time algorithm achieving this bound been discovered (the NOT theorem). The method involves a flow associated to any triangulation, and perturbing this flow to form closed loops (a sort of discrete version of Pugh’s closing lemma). Sharpness of the algorithm remains open, as do analogous questions for triangulated surfaces and for polyhedra in 3-space. The triangle flow introduced in the proof is apparently a new object and its properties also remain to be investigated.

General Meeting Assistance
Emily Klein
MPS Event Coordinator, Simons Foundation
[email protected]
(646) 751-1262