# Simons Collaboration on Algorithms and Geometry Monthly Meeting, February 2020

Date & Time

• 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 quad-meshing
• Abstracts

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.

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