Real Analysis Seminars

Short presentations:

Covering CSPs

Gillat Kol (Technion Israel Institute of Technology)

We study the covering complexity of constraint satisfaction problems (CSPs). The covering number of a CSP instance is the smallest number of assignments to the variables, such that each constraint is satisfied by at least one of the assignments. We give a partial characterization of covering-hard predicates. [Joint work with Irit Dinur.]

Average Sensitivity of narrow or short CNF formulas (and maybe depth-3 circuits)

Dominik Scheder (Aarhus University)

If your CNF formula is short (few clauses) or narrow (few literals per clause), what can you say about its average sensitivity (also known as total influence)? Li-Yang Tan and I found some surprisingly tight bounds. There are several open questions, ranging from probably easy to probably tough.

Applications of high-dimensional probability to coding theory

Mary Wootters (University of Michigan)

Much of my work has focused on showing that desirable properties of random objects continue to hold when some convenient structure is imposed and the objects aren't quite as random anymore.  In this short talk, I'll focus on a few recent examples from coding theory.

Gaussian Isoperimetry in Approximation Algorithms

Steven Heilman (Courant Institute, NYU)

We briefly motivate and state two problems in Gaussian isoperimetry.

1. The Propeller Conjecture of Khot and Naor (http://arxiv.org/abs/0807.4626)
2. The Symmetric Gaussian Problem of Chakrabarti and Regev (http://arxiv.org/abs/1009.3460)

Seminar:

Large deviations in sparse random graphs: a local weak convergence approach

Pietro Caputo (Roma Tre University)

Consider the Erdös-Renyi random graph on n vertices where each edge is present independently with probability p=c/n, with c>0 fixed. For large n, a typical realization locally behaves like the Galton-Watson tree with Poisson offspring distribution with mean c. We discuss large deviations from this typical behavior, within the framework of the local weak convergence introduced by
Benjamini-Schramm and Aldous-Steele. The associated rate function is expressed in terms of an entropy functional on unimodular measures and takes finite values only at measures supported by trees. Along the way, we present a new configuration model which allows one to sample uniform random graphs with a given finite neighborhood distribution, provided the latter is supported by trees. We also present a new class of unimodular random trees, which generalizes the Galton-Watson tree with given degree distribution to the case of neighborhoods of arbitrary finite depth. This is joint work with Charles Bordenave.