Recent Comments

Recent Posts
 Next Week in Jerusalem: Special Day on Quantum PCP, Quantum Codes, Simplicial Complexes and Locally Testable Codes
 Happy Birthday Ervin, János, Péter, and Zoli!
 My Mathematical Dialogue with Jürgen Eckhoff
 Test Your Intuition (23): How Many Women?
 Happy Birthday Richard Stanley!
 Influence, Threshold, and Noise
 Erdős Lectures 2014 – Dan Spielman
 Answer to Test Your Intuition (22)
 Test your intuition (22): Selling Two Items in a Bundle.
Top Posts & Pages
 The KadisonSinger Conjecture has beed Proved by Adam Marcus, Dan Spielman, and Nikhil Srivastava
 Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun
 Test Your Intuition (23): How Many Women?
 Why is Mathematics Possible: Tim Gowers's Take on the Matter
 Believing that the Earth is Round When it Matters
 My Mathematical Dialogue with Jürgen Eckhoff
 Five Open Problems Regarding Convex Polytopes
 New Ramanujan Graphs!
 Why Quantum Computers Cannot Work: The Movie!
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 Grouptheoretic algorithms for matrix multiplication, by Henry Cohn, Robert Kleinberg, Balasz Szegedy, and Christopher Umans (CKSU05), … Continue reading
Discrepancy, The BeckFiala 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
5 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: Gowers’s theoretical post marking the official start of Polymath 5 appeared. Update (February 2014): Boris Konev and Alexei Lisitsa found a sequence of length 1160 of discrepancy 2 … Continue reading
Four Derandomization Problems
Polymath4 is devoted to a question about derandomization: To find a deterministic polynomial time algorithm for finding a kdigit 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
4 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 CapSet Problem and FranklRodl 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, FranklRodl theorem, polymath1
Leave a comment