
Computer Science/Discrete Mathematics Seminar II
“Sharp” Selector Processes
Positive selector processes are natural stochastic processes driven by sparse Bernoulli random variables. They play an important role in the study of suprema of general stochastic processes, and in particular, Talagrand posed the selector process conjecture as a last missing piece in this endeavor. Interestingly Talagrand also drew a rich picture of connections between his conjecture and phenomena of fundamental interest in combinatorics and computer science. I will discuss the different perspectives around Talagrand’s selector process conjecture and its high-level connection to optimization problems under randomness, and the threshold phenomena.
Strengthening this connection, I will discuss a quantitative sharp version of Talagrand’s selector process conjecture, which provides a common strengthening of the selector process conjecture and the Kahn-Kalai conjecture. This can be viewed as a sharp description of the behavior of positive linear programs (or fractionally subadditive functions) under random sparsification. As an application, I will discuss progress towards another conjecture of Talagrand on the “integrality gap” of a wide class of integer linear programs involving “covers” of general set systems, relating the so-called expectation threshold and its fractional relaxation.
The principles underlying these results involve the key notion of minimum fragments in the proof of the selector process conjecture and the Kahn-Kalai conjecture, and the new notion of towers of minimum fragments required for the sharp version of the selector process conjecture.