# Workshop on Algorithms and Randomness

Monday, May 14 - Thursday, May 17, 2018

Georgia Tech, Klaus Building, Room 1116

**Speaker:** Nikhil Bansal (Eindhoven)

**Title:**An algorithmic version of Banaszczyk's discrepancy theorem

**Abstract**: In the 90's Banaszczyk developed a very powerful method for discrepancy problems, that goes beyond the partial coloring method. His result was based on deep results from convex geometry and was non-constructive. In this talk, I will present an alternate proof of this result, which is based on elementary techniques and also gives an efficient algorithm. This leads to the first efficient algorithms for several previous results in discrepancy.

Based on joint work with Daniel Dadush, Shashwat Garg and Shachar Lovett.

**Speaker:** Alan Frieze (CMU)

**Title:** Random Walk Cuckoo Hashing Abstract: We consider the expected insertion time of Cuckoo Hashing when clashes are resolved randomly. We prove O(1) expected time insertion in two cases.

(i) d choices of location and location capacity one: joint with Tony Johansson.

(ii) 2 choices of location and location capacity d: joint with Samantha Petti

**Speaker: **Mark Jerrum (Queen Mary)

**Title:** A polynomial-time approximation algorithm for all-terminal network reliability

**Abstract**: Let G be an undirected graph in which each edge is assigned a failure probability. Suppose the edges fail independently with the given probabilities. We are interested in computing the probability that the resulting graph is connected, the so-called all-terminal reliability of G. As this is an #P-hard problem, computing an exact solution is infeasible. Karger gave an efficient approximation algorithm, in the sense of FPRAS or Fully Polynomial Randomised Approximation Scheme, for all-terminal unreliability (the probability of the network being disconnected). However, the existence of an FPRAS for unreliability does not imply an FPRAS for reliability, as the operation of subtracting from 1 does not preserve relative error.

I shall present an FPRAS for all-terminal reliability or, equivalently, evaluating the Tutte polynomial T(G;x,y) on the semi-infinite line x = 1 and y ≥ 1. This is the first good news on approximating the Tutte polynomial of unrestricted graphs for a long time. The main contribution is to confirm a conjecture by Gorodezky and Pak (Random Structures and Algorithms, 2014), that the expected running time of the "cluster-popping" algorithm in so-called bi-directed graphs is bounded by a polynomial in the size of the input. Surprisingly, the cluster popping algorithm on bi-directed graphs solves a disguised version of the all-terminal reliability problem on undirected graphs, a fact that was known to researchers in network reliability in 1980, but seems to have been forgotten in the meantime.

Joint work with Heng Guo (Edinburgh)

**Speaker**: Fabio Martinelli (Roma Tre)

**Title:** ON THE INFECTION TIME OF STOCHASTIC SPIN MODELS WITH CONSTRAINTS: UNIVERSALITY IN TWO DIMENSIONS

**Abstract:** Recent years have seen a great deal of progress in understanding the behavior of bootstrap percolation models, a particular class of monotone cellular automata. In the two dimensional lattice, there is now a quite satisfactory understanding of their evolution starting from a random initial condition, with a strikingly beautiful universality picture for their critical behavior (length and time scales). Much less is known for their non-monotone stochastic counterpart, namely kinetically constrained models (KCM). In KCMs the state of each vertex which could be infected by the bootstrap percolation rules is resampled (independently among the vertices) at rate one by tossing a p-coin. In particular, the infection can also heal, hence the non-monotonicity. Besides their connection with bootstrap percolation, KCMs have a strong interest in their own: as p ↓ 0 they display some of the most striking features of the liquid/glass transition, a major and still largely open problem in condensed matter physics. In this talk, I shall discuss (i) some recent conjectures relating the universality behavior of critical KCMs to their bootstrap percolation counterpart and (ii) some very recent progress towards proving the above conjectures.

Joint project with C. Toninelli (Paris VII) and R. Morris (IMPA)

**Speaker:**Will Perkins (Birmingham)

**Title:** Sphere packings, codes, and kissing numbers via hard core models

**Abstract:** We prove a lower bound on the expected size of a spherical code drawn from a "hard cap" model and the expected density of a packing drawn from the hard sphere model in high dimensions. These results allows us to improve the lower bound on the kissing number in high dimensions by a factor d and to prove new lower bounds on the entropy of sphere packings of density \Theta(d 2^{-d}) in R^d. Joint work with Matthew Jenssen and Felix Joos.

**Speaker: **Daniel Stefankovic (Rochester)

**Title: **Inapproximability of the Independent Set Polynomial in the Complex Plane

**Abstract: **Hard-core model (also known as independent set polynomial) is one of the simplest models in statistical physics. The complexity of approximating the value of the partition function of the model on max-degree-Delta graphs (and also sampling from the Gibbs distribution) is now understood for positive values of the parameter (Weitz'2005, Sly'2009)---the complexity threshold aligns with the uniqueness/non-uniqueness threshold for the existence of multiple Gibbs measures on Delta-regular tree.

In the case of complex parameter the complexity of approximating the partition function is not yet understood---the complexity threshold appears to align with the existence of zeros of the partition function on trees of max-degree-Delta. We show that outside of the conjectured zero-free region the problem of approximating the value of the partition function is hard (#P-hard). Joint work with Ivona Bezakova, Andreas Galanis, and Leslie Ann Goldberg.

**Speaker: ** Yufei Zhao (MIT)

**Title:** Large deviations in random graphs

**Abstract**: What is the probability that the number of triangles in an Erd\H{o}s–R\'enyi random graph exceeds its mean by a constant factor?

This problem has been a useful litmus test for concentration bound techniques. Even the order of the log-probability was considered a difficult problem until its resolution a few years ago by Chatterjee and DeMarco--Kahn. I will discuss the problem of determining the exponential rate of the tail probability, and survey some recent developments and open problems.