[theory-seminar] TCS+ talk: Wednesday, October 2, Shachar Lovett, UCSD

[Clement Canonne]

Hi,

Due to a very bad case of "my having a doctor's appointment and not 
actually being on campus tomorrow morning" (which, admittedly, was 
entirely foreseeable), there won't be a live projection of Shachar's 
talk tomorrow. *However*, if any of you is interested in seeing it live 
(as opposed to later on YouTube), with the ability to ask questions, let 
me know -- it's very easy to join the online talk.

Best,

-- Clément

On 9/27/19 4:21 PM, Clément Canonne wrote:
> Hi all,
> 
> As mentioned at the end of today's seminar, this coming Wednesday, 
> October 2th, at 10am, Shachar Lovett from UCSD will speak on TCS+ about 
> "Towards the sunflower conjecture" (abstract below).
> 
> I have requested an online seat, meaning that, as usual, the speaker's 
> slides and face will be moving on the wall of Gates 463A, live, and we 
> can ask questions (there will also be breakfast).
> 
> See you there,
> 
> -- Clément
> 
> -------------------------------
> Speaker: Shachar Lovett (UCSD)
> Title: Towards the sunflower conjecture
> 
> Abstract: A sunflower with $r$ petals is a collection of $r$ sets so 
> that the intersection of each pair is equal to the intersection of all. 
> Erdos and Rado in 1960 proved the sunflower lemma: for any fixed $r$, 
> any family of sets of size $w$, with at least about $w^w$ sets, must 
> contain a sunflower. The famous sunflower conjecture is that the bound 
> on the number of sets can be improved to $c^w$ for some constant $c$. 
> Despite much research, the best bounds until recently were all of the 
> order of $w^{cw}$ for some constant c. In this work, we improve the 
> bounds to about $(log w)^w$.
> 
> There are two main ideas that underlie our result. The first is a 
> structure vs pseudo-randomness paradigm, a commonly used paradigm in 
> combinatorics. This allows us to either exploit structure in the given 
> family of sets, or otherwise to assume that it is pseudo-random in a 
> certain way. The second is a duality between families of sets and DNFs 
> (Disjunctive Normal Forms). DNFs are widely studied in theoretical 
> computer science. One of the central results about them is the switching 
> lemma, which shows that DNFs simplify under random restriction. We show 
> that when restricted to pseudo-random DNFs, much milder random 
> restrictions are sufficient to simplify their structure.
> 
> Joint work with Ryan Alweiss, Kewen Wu and Jiapeng Zhang.
> 
> _______________________________________________
> theory-seminar mailing list
> theory-seminar at lists.stanford.edu
> https://mailman.stanford.edu/mailman/listinfo/theory-seminar