Tag Archives: Cap sets

Mind Boggling: Following the work of Croot, Lev, and Pach, Jordan Ellenberg settled the cap set problem!

Posted on May 15, 2016 by Gil Kalai

A quote from a recent post from Jordan Ellenberg‘s blog Quomodocumque: Briefly:  it seems to me that the idea of the Croot-Lev-Pach paper I posted about yesterday (GK: see also my last post) can indeed be used to give a new bound … Continue reading →

Posted in Combinatorics, Open problems, Updates | Tagged , , , , , | 25 Comments

Cap Sets, Sunflowers, and Matrix Multiplication

Posted on December 9, 2011 by Gil Kalai

This post follows a recent paper On sunflowers  and matrix multiplication by Noga Alon, Amir Spilka, and Christopher Umens (ASU11) which rely on an earlier paper Group-theoretic algorithms for matrix multiplication, by Henry Cohn, Robert Kleinberg, Balasz Szegedy, and Christopher Umans (CKSU05), … Continue reading →

Posted in Combinatorics, Computer Science and Optimization, Open problems | Tagged , , , , , , | 9 Comments

The Cap-Set Problem and Frankl-Rodl Theorem (C)

Posted on May 18, 2009 by Gil Kalai

Update: This is a third of three posts (part I, part II) proposing some extensions of the cap set problem and some connections with the Frankl Rodl theorem. Here is a post presenting the problem on Terry Tao’s blog (March 2007). Here … Continue reading →

Posted in Combinatorics, Open problems | Tagged , , | 2 Comments

Around the Cap-Set problem (B)

Posted on May 11, 2009 by Gil Kalai

Part B: Finding special cap sets This is a second part in a 3-part series about variations on the cap set problem that I studied with Roy Meshulam. (The first post is here.)  I will use here a different notation than in part … Continue reading →

Posted in Combinatorics, Open problems | Tagged , , | 4 Comments

An Open Discussion and Polls: Around Roth’s Theorem

Posted on March 25, 2009 by Gil Kalai

Suppose that  is a subset of of maximum cardinality not containing an arithmetic progression of length 3. Let . How does behave? We do not really know. Will it help talking about it? Can we somehow look beyond the horizon and try to guess what … Continue reading →

Posted in Combinatorics, Open discussion, Open problems | Tagged , , , | 29 Comments

Frankl-Rodl’s Theorem and Variations on the Cap Set Problem: A Recent Research Project with Roy Meshulam (A)

Posted on February 7, 2009 by Gil Kalai

Voita Rodl I would like to tell you about a research project in progress with Roy Meshulam. (We started it in the summer, but then moved to other things;  so far there are interesting insights, and perhaps problems, but not substantial … Continue reading →

Posted in Combinatorics, Open problems | Tagged , , , | 10 Comments