For a fixed integer k > 1, the Boolean k-XOR problem consists of a system of linear equations mod 2 with each equation involving exactly k variables. We give an algorithm to strongly refute *semi-random* instances of the Boolean k-XOR problem on n...

#
Computer Science and Discrete Mathematics (CSDM)

This talk introduces a directed analog of the classical Laplacian matrix and discusses algorithms for solving certain problems related to them. Of particular interest is that using such algorithms, one can compute the stationary distribution of a...

A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours. The study of rainbow subgraphs goes back to the work of Euler on Latin squares in the 18th century. Since then rainbow structures were the focus of...

This talk gives an introduction on how to quickly solve linear systems where the matrix of the system is the Laplacian matrix of any undirected graph. No prior familiarity with optimization is assumed. In the process, we will cover:

- what positive...

### Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion

We consider the Glauber dynamics (also called Gibbs sampling) for sampling from a discrete distribution in high-dimensional space (e.g., selecting a uniformly random legal coloring or independent set in a given graph, or selecting a "typical" state...

Expander graphs are graphs which simultaneously are both sparse and highly connected. The theory of expander graphs received a lot of attention in the past half a century, from both computer science and mathematics. In recent years, a new theory of...

Valiant (1980) showed that general arithmetic circuits with negation can be exponentially more powerful than monotone ones. We give the first qualitative improvement to this classical result: we construct a family of polynomials P-n in n variables...

Expander graphs are graphs which simultaneously are both sparse and highly connected. The theory of expander graphs received a lot of attention in the past half a century, from both computer science and mathematics. In recent years, a new theory of...

Non-constructive existence proofs, which establish the existence of objects without furnishing an efficient algorithm to produce examples, abound in mathematics. How hard is it, computationally, to find objects whose existence is guaranteed non...

A polynomial with nonnegative coefficients is strongly log-concave if it and all of its derivatives are log-concave as functions on the positive orthant. This rich class of polynomials includes many interesting examples, such as homogeneous real...