Theory Lunch

A platform for informal discussions about problems in theoretical computer science and discrete math. Maintained by Shengyu Zhang.

Next meeting: TBA.

• Time:     Every Tuesday, 12:30pm-2:00pm.

• Venue:   SHB 1027

• Others: 

  • Food: Bring your own.

  • People: Anyone is welcome. If you'd like to join the mailing list, send an email to Shengyu.

  • Topics: Right now it's very informal. Anyone can just bring up a question or talk about his/her favorite theorem at the moment.

  • Links: See other theory activities: theory reading group and ITCSC seminar.

Past meetings:

Dec 9, 2008

• Minghua Chen: A recent work on the minimum-cost Steiner tree problem on P2P overlay networks.

Nov 11, 2008

• Shengyu Zhang: Lower bounding communication complexity by dual polynomials. See here for a recent survey by Sherstov. In particular, his pattern matrix paper for the bounded-error quantum communication complexity is here and the block-composition paper by Shi and Zhu is here.

Oct 14, 2008

• Hongyi talked about a problem in double-channel coding.

Sep 30 2008

• Chandra asked a question about optimization version of the set partition problem on random inputs.

• We then discussed the future agenda for the PCP reading group.

Sep 23, 2008:

• Shengyu talked about a question asked by Qin, according to an email he sent to him right before the lunch.

• Lap Chi gave a short report on an upcoming paper at FOCS.

Sep 16, 2008:

• Jesse asked an interesting lower bound question about interval covering, which then took most of the time to discuss. It was happy to see that the short discussions then seemed to lead to pretty good lower and upper bounds already. More motivations (than pure discrete math fun) may be needed to let people push more.

• In the remaining 20 minutes, Lap Chi and Chandra mentioned some open questions in graph coloring and multi-channel coding, respectively. Chandra later wrote a surprising detailed description of his question. Thanks!

Sep 9, 2008:

• Minghua asked an interesting question about the power of two choices.

• Lap Chi briefly talked about Dvir's proof of lower bounds on the Kakeya sets in finite fields (following Tao's blog entry), and Andrej continued to discuss a recent application to mergers.

• Leizhen asked an interesting question about circle cutting.