### Lunches

#### Fri May 11: Discrepancy upper bound

We worked through the proof that every hypergraph with sufficiently many edges has a 2-coloring with discrepancy at most sqrt( n log(m/n) ). Highlights of the proof included the use of entropy and Kleitman's theorem. |

#### Thu May 11: Sensitivity analysis of optimization problems

Abdullah explained how the Lagrange multipliers form the sub-gradient or gradient, respectively, of a parameterized continuous optimization problem. |

#### Wed May 10: Nash equilibria and sampling

Bahman continued his discussion of neural networks: a generator-discriminator pair sample from a given distribution. |

#### Mon May 8: Joint TCS Pizza Seminar

Dominique presented a problem related to quantum query complexity of random function inversions. |

#### Fri May 5: Problems related to edge coverings

Visiting PhD student Mahdi gave a survey over his research in edge coverings, vertex coverings: complexity, algorithms, combinatorics. He also discussed some of the problems he hopes to attach while in Tartu. |

#### Thu May 4: Lagrange duality

Abdullah explained Lagrange duality for optimization problems: The Lagrange dual function, the Lagrange dual, weak duality theorem, strong duality, ... |

#### Wed May 3: Training neural networks

Bahman explained how to train feed-forward neural networks by gradient descent, using backpropagation. |

#### June 15: Maximal m-free digraphs

Today, Janno Siim gave his seminar presentation on maximal m-free digraphs. He presented, for example, the proof for the fact every maximal m-free digraphs has an m-king. |

#### June 8: Zero-nonzero patterns of low-degree polynomials

On Monday, DOT will present a theorem of Ronyai, Babai, and Ganapathy which gives an upper bound to the number of zero / nonzero patterns of a sequence of n polynomials in m variables of degree at most d. The perhaps most interesting fact is that the bound does not depend on n---only on m, d, and the number of non-zeros in the pattern. We will then discuss an application, due to Leslie Hogben and coauthors, to random matrix theory: the minimum rank of a matrix with a prescribed, random, zero-nonzero pattern. |

#### May 25: Probabilistic recurrences II

This week, Abdullah continued the proofs of the Karp's tail bounds on probabilistic recurrence relations. |

1-10 of 41