September 24, Thursday, 13:00 (sharp!) - 15:00 in E:2116 (building E) SCHEDULE 13:00 Vladimir Podolskii (Tufts University, USA) Depth-2 threshold circuits and related models of computation 14:00 Johan Wästlund (Chalmers University of Technology) The random assignment problem: sampling and a central limit theorem 15:00 Coffee and discussions --------------------------------------------------- The workshop is organized in connection with the defence of Jonas Conneryd of his PhD Thesis "On the Algebraic Proof Complexity of Constraint Satisfaction" on Friday September 25th, at 01:00 p.m. in Lecture Hall E:1406 (building E) Opponent: Professor Alexander Razborov, USA.

13:00-14:00 

Depth-2 threshold circuits and related models of computation

Vladimir Podolskii 

(Tufts University, USA)

Low-depth Boolean threshold circuits play an important role in theoretical computer science. On one hand, they are central for some of the main current frontiers in Boolean circuit complexity, and on the other hand they form a Boolean version of feed-forward neural networks. It turns out that proving lower bounds for these Boolean circuits is notoriously hard: lower bounds for explicit functions are unknown even for depth-2 circuits. In other words, we do not understand well the expressibility of feed-forward neural networks with just one hidden layer.

In this talk we will discuss known approaches to this problem, subproblems that also remain open, and some recent progress on them. In particular, we will discuss other computational models that turn out to be related to this setting, including models based on decision lists and models based on nearest neighbour representation of Boolean functions.

The talk is based on joint work with Mason DiCicco, Morgan Prior and Daniel Reichman. I will also mention some older results of joint work with Kristoffer Arnsfelt Hansen.

------------------------------------------------------------------------

14:00 - 15:00

The random assignment problem: sampling and a central limit theorem

Johan Wästlund 

(Chalmers University of Technology)

In an $n$ by $n$ complete bipartite graph we give each of the $n^2$ edges independently a mean 1 exponential cost and ask for the minimum total cost $C_n$ of a perfect matching. It is known that $C_n$ converges in probability to $\pi^2/6$ with fluctutations of order $1/\sqrt{n}$. Recently Gilles Mordant has shown a central limit theorem, in other words that after rescaling, $C_n$ has a Gaussian limit distribution. Building on Mordant's work we establish a lattice path formula that exactly describes the distribution of $C_n$ and allows sampling from this distribution for very large $n$ as well as an alternative proof of the central limit theorem.