Simons Collaboration on Algorithms and Geometry Monthly Meeting, February 2020

Agenda
Friday, February 28, 2020
9:30  10:30 AM Breakfast 10:30  11:30 AM Nathan Keller: Local tail inequalities, biased halfspaces, and noise sensitivity, Part I 11:30  11:45 AM Break 11:4 5 AM  12:45 PM Nathan Keller: Local tail inequalities, biased halfspaces, and noise sensitivity, Part II 12:45  2:00 PM Lunch 2:00  3:00 PM Chris Bishop: Fast conformal mapping 3:00  3:15 PM Break 3:15  4:15 PM Chris Bishop: Optimal triangulation and quadmeshing 
Abstracts
Nathan Keller
Local tail inequalities, biased halfspaces, and noise sensitivityWeighted 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 firstlevel 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 mappingBoth 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 SchwarzChristoffel 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 quadmeshing of planar domains.
Chris Bishop
Optimal triangulation and quadmeshingPicking up where the last talk ended, I will discuss what is known about optimal quadmeshing 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 (wellshaped 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 quadmeshes 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 (nonobtuse 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 3space. The triangle flow introduced in the proof is apparently a new object and its properties also remain to be investigated.

Contacts
General Meeting Assistance
Emily Klein
MPS Event Coordinator, Simons Foundation
eklein@simonsfoundation.org
(646) 7511262