### Recent Comments

Philip Gibbs on Polymath10, Post 2: Homologica… Philip Gibbs on Polymath10, Post 2: Homologica… Philip Gibbs on Polymath10, Post 2: Homologica… Gil Kalai on Polymath10, Post 2: Homologica… Philip Gibbs on Polymath10, Post 2: Homologica… Gil Kalai on Polymath10, Post 2: Homologica… gowers on Polymath10, Post 2: Homologica… GFP on Polymath10, Post 2: Homologica… domotorp on Polymath10, Post 2: Homologica… GFP on Polymath10, Post 2: Homologica… Philip Gibbs on Polymath10, Post 2: Homologica… Gil Kalai on Polymath10, Post 2: Homologica… -
### Recent Posts

- Polymath10, Post 2: Homological Approach
- Polymath10: The Erdos Rado Delta System Conjecture
- Convex Polytopes: Seperation, Expansion, Chordality, and Approximations of Smooth Bodies
- Igor Pak’s collection of combinatorics videos
- EDP Reflections and Celebrations
- Séminaire N. Bourbaki – Designs Exist (after Peter Keevash) – the paper
- Important formulas in Combinatorics
- Updates and plans III.
- NogaFest, NogaFormulas, and Amazing Cash Prizes

### Top Posts & Pages

- The Kadison-Singer Conjecture has beed Proved by Adam Marcus, Dan Spielman, and Nikhil Srivastava
- Polymath10, Post 2: Homological Approach
- Polymath10: The Erdos Rado Delta System Conjecture
- Believing that the Earth is Round When it Matters
- New Ramanujan Graphs!
- Amazing: Peter Keevash Constructed General Steiner Systems and Designs
- Can Category Theory Serve as the Foundation of Mathematics?
- Why is Mathematics Possible: Tim Gowers's Take on the Matter
- Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun

### RSS

# Search Results for: erdos

## Cup Sets, Sunflowers, and Matrix Multiplication

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

## Discrepancy, The Beck-Fiala Theorem, and the Answer to “Test Your Intuition (14)”

The Question Suppose that you want to send a message so that it will reach all vertices of the discrete -dimensional cube. At each time unit (or round) you can send the message to one vertex. When a vertex gets the … Continue reading

## Around Borsuk’s Conjecture 1: Some Problems

Greetings to all! Karol Borsuk conjectured in 1933 that every bounded set in can be covered by sets of smaller diameter. In a previous post I described the counterexample found by Jeff Kahn and me. I will devote a few posts … Continue reading

## Tentative Plans and Belated Updates II

Elementary school reunion: Usually, I don’t write about personal matters over the blog, but having (a few weeks ago) an elementary school reunion after 42 years was a moving and exciting event as to consider making an exception. For now, … Continue reading

Posted in Updates
Tagged Cap set problem, Discrete Geometry, Influence, Quantum computation
6 Comments

## Polymath Reflections

Polymath is a collective open way of doing mathematics. It started over Gowers’s blog with the polymath1 project that was devoted to the Density Hales Jewett problem. Since then we had Polymath2 related to Tsirelson spaces in Banach space theory , an intensive Polymath4 devoted … Continue reading

## A Discrepancy Problem for Planar Configurations

Yaacov Kupitz and Micha A. Perles asked: What is the smallest number C such that for every configuration of n points in the plane there is a line containing two or more points from the configuration for which the difference between the … Continue reading

## Polymath5 – Is 2 logarithmic in 1124?

Polymath5 – The Erdős discrepancy problem – is on its way. Update (September 2015): Terry Tao have now solved Erdos discrepancy problem and proved that indeed the discrepancy tends to infinity. See also this blog post on Tao’s blog. Update: Gowers’s … Continue reading

## Four Derandomization Problems

Polymath4 is devoted to a question about derandomization: To find a deterministic polynomial time algorithm for finding a k-digit prime. So I (belatedly) devote this post to derandomization and, in particular, the following four problems. 1) Find a deterministic algorithm for primality 2) Find … Continue reading

Posted in Computer Science and Optimization, Probability
Tagged derandomization, polymath4, Randomness
5 Comments

## Vitali Fest

Last week I took part in a lovely and impressive conference on the state of geometry and functional analysis, celebrating Vitali Milman’s 70th birthday. The conference started in Tel Aviv, continued at the Dead Sea, and returned to Tel Aviv. I gave a … Continue reading

Posted in Conferences
5 Comments

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

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 Cap sets, Frankl-Rodl theorem, polymath1
Leave a comment