Discrete Lunch

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
  • somebody's favorite algorithmic/combinatorial research problem, or
  • a hot result he recently encountered, or
  • a cool proof technique he came across, or
  • a theorem he recently proved, or
  • a conjecture of his own he couldn't figure out yet, or
  • progress or comments on any of the previous weeks' topics.
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.

Below are announcements for upcoming discrete lunches and TCS Joint Seminars.

June 15: Maximal m-free digraphs

posted Jun 15, 2015, 5:50 AM by Dirk Oliver Theis

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

posted Jun 7, 2015, 4:01 AM by Dirk Oliver Theis

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

posted May 31, 2015, 9:48 PM by Dirk Oliver Theis

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

May 18: Probabilistic recurrences

posted May 18, 2015, 3:20 AM by Dirk Oliver Theis

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

posted May 11, 2015, 2:20 AM by Dirk Oliver Theis

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.

May 4: Third TCS joint seminar

posted May 2, 2015, 4:35 AM by Dirk Oliver Theis   [ updated May 11, 2015, 2:25 AM ]

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

posted Apr 24, 2015, 3:30 AM by Dirk Oliver Theis

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

posted Apr 20, 2015, 2:05 AM by Dirk Oliver Theis   [ updated Apr 24, 2015, 3:30 AM ]

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}

posted Apr 12, 2015, 11:28 PM by Dirk Oliver Theis   [ updated Apr 24, 2015, 3:31 AM ]

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

posted Apr 5, 2015, 3:54 AM by Dirk Oliver Theis   [ updated Apr 24, 2015, 3:33 AM ]

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