The "Discrete Lunch" is our main weekly event. It is intended to be a low-stress high-fun meeting for those in the CS institute who are interested in discrete mathematics research in the broadest sense. Bring your dessert & coffee, and enjoy discussions on
Occasionally, there may be actual "talks".
Joins us on
Mondays, room 611, 2pm c.t.
On the first Monday of every month, instead of the Discrete Lunch, there's the new
Theoretical Computer Science Joint Seminar,
where all of the CS institute's theorists meet and exchange problems and ideas. It takes place in room 225.
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.
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.
This week, Abdullah continued the proofs of the Karp's tail bounds on probabilistic recurrence relations.
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.
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-k.) One is then interested in the average length of the strings produced by the extractor.
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.
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.
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.
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.
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.
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