### Discrete Lunch

#### 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. |

#### May 18: Probabilistic recurrences

Today, Abdullah will talk about random recursive relations, and what can be said about expectation and upper tail based on very general assumptions. The main results go back to a paper of Karp from the 1990s. The motivation behind studying these relations lies in the analysis of randomized algorithms. |

#### May 11: Randomness extractors

In today's Discrete Lunch, we'll discuss randomness extractors. A randomness extractor is a function which maps the points of a probability space to bit strings in such a way that, for all k, all length k strings are produced with equal probability (i.e., either 0 or 2.) One is then interested in the average length of the strings produced by the extractor.^{-k}We will first prove the easy upper bound on the average length of the strings produced by an extractor: the entropy of the probability space. After that, we'll look at a few constructions of randomness extractors. |

#### May 4: Third TCS joint seminar

This Monday, as on every first Monday of a month, we'll hold the joint TCS seminar. Probably Dominique will finish up his presentation of his quantum query complexity problem. After that, it's open stage. Post scriptum, added after the meeting. The following problems were discussed. DOT presented a probability/hypergraph problem connected to random k-SAT instances which he couldn't solve. Nobody had any useful ideas. Abdullah talked about an algorithmic problems on strings with applications in bioinformatics, which spawned a lively discussion. |

#### April 27: Superboolean rank & largest triangular submatrix of a random matrix

Mozhgan will present the contents of that paper. Here's the abstract: We explore the size of the largest (permuted) triangular submatrix of a random matrix, and more precisely its asymptotical behavior as the size of the ambient matrix tends to infinity. The importance of such permuted triangular submatrices arises when dealing with certain combinatorial algebraic settings in which these submatrices determine the rank of the ambient matrix, and thus attract a special attention. |

#### Aril 20: Hypergraph recoloring

An assignment of one of two colors, red or blue, to every vertex of a hypergraph is called a proper 2-coloring, if no edge is monochromatic. Hypergraphs which have a proper 2-coloring are sometimes said to have Property B (as in "bipartite", maybe?).Unlike for usual graphs, where deciding whether it is bipartite can easily done in polynomial time, deciding whether a given hypergraph has a proper 2-coloring is an NP-complete problem. In today's Discrete Lunch, we'll discuss a smart re-coloring procedure, which finds a proper 2-coloring for every r-uniform hypergraph which does not have too many edges. |

#### April 13: Random k-SAT with other domains than {0,1}

Today, for Discrete Lunch, we'll discuss a hypergraph coloring problem which arises from a question about thresholds for the satisfiability of random SAT instances. |

#### 2nd TCS Joint Seminar

Tomorrow, April 6, 14:15, room 225, we'll hold the 2nd all-of-TCS seminar. Since the meeting is more "spontaneous" than the Discrete Lunch, I'll summarize it when it's over. -- Now here's the summary: Dominique continued presenting his problem about quantum interactive proofs. |

1-10 of 34