Let be the -dimensional cube. Turn into a torus by identifying opposite facets. What is the minumum -dimensional volume of a subset of which intersects every non-trivial cycle in .

Advertisements

Let be the -dimensional cube. Turn into a torus by identifying opposite facets. What is the minumum -dimensional volume of a subset of which intersects every non-trivial cycle in .

Advertisements

This entry was posted in Geometry, Test your intuition and tagged Test your intuition. Bookmark the permalink.

Advertisements

### Recent Comments

Matthew Cory on My Argument Against Quantum Co… Matthew Cory on My Argument Against Quantum Co… vznvzn on My Argument Against Quantum Co… Matthew Cory on My Argument Against Quantum Co… Matthew Cory on My Argument Against Quantum Co… Gil Kalai on Monday February 19: Quantum Co… anonymous on Monday February 19: Quantum Co… Gil Kalai on The Semester Break activities… perringu on Lovasz’s Two Families… vznvzn on My Argument Against Quantum Co… vznvzn on My Argument Against Quantum Co… Futureseek Daily Lin… on My Argument Against Quantum Co… -
### Recent Posts

- Monday February 19: Quantum Coding and High Dimensional Expanders
- Alef’s Corner: There is Still a Small Gap in the Proof
- My Argument Against Quantum Computers: An Interview with Katia Moskvitch on Quanta Magazine
- The Semester Break activities of the High Dimensional Combinatorics and Expanders Special Year
- Akshay Venkatesh Lectures at HUJI – Ostrowski’s Prize Celebration, January 24&25
- Hardness of Approximating Vertex Cover, Polytope-Integrality-Gap, the Alswede-Kachatrian theorem, and More.
- Jacob Fox, David Conlon, and Benny Sudakov: Vast Improvement of our Knowledge on Unavoidable Patterns in Words
- Subhash Khot, Dor Minzer and Muli Safra completed the proof of the 2-to-2 Games Conjecture
- Interesting Times in Mathematics: Enumeration Without Numbers, Group Theory Without Groups.

### Top Posts & Pages

- Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun
- Believing that the Earth is Round When it Matters
- After-Dinner Speech for Alex Lubotzky
- Elchanan Mossel's Amazing Dice Paradox (your answers to TYI 30)
- TYI 30: Expected number of Dice throws
- If Quantum Computers are not Possible Why are Classical Computers Possible?
- My Argument Against Quantum Computers: An Interview with Katia Moskvitch on Quanta Magazine
- Subhash Khot, Dor Minzer and Muli Safra completed the proof of the 2-to-2 Games Conjecture
- Can Category Theory Serve as the Foundation of Mathematics?

### RSS

### Categories

- Academics (9)
- Algebra and Number Theory (16)
- Analysis (5)
- Applied mathematics (3)
- Art (9)
- Blogging (12)
- Book review (4)
- Combinatorics (187)
- Computer Science and Optimization (91)
- Conferences (58)
- Controversies and debates (21)
- Convex polytopes (52)
- Convexity (24)
- Economics (23)
- Education (1)
- Elections 2015 (7)
- Games (31)
- Geology (2)
- Geometry (29)
- Gina Says (7)
- Guest blogger (22)
- Happy birthday (3)
- Information theory (2)
- Law (6)
- Logic and set theory (1)
- Mathematical logic and set theory (2)
- Mathematics over the Internet (20)
- Mathematics to the rescue (12)
- Movies (4)
- Music (2)
- Nostalgia (1)
- Number theory (6)
- Obituary (9)
- Open discussion (16)
- Open problems (86)
- personal (3)
- Philosophy (17)
- Physics (27)
- Poetry (5)
- Polymath10 (8)
- Polymath3 (10)
- Probability (55)
- Quantum (24)
- Rationality (24)
- Riddles (7)
- Sport (7)
- Statistics (3)
- Taxi-and-other-stories (18)
- Teaching (14)
- Test your intuition (46)
- Uncategorized (14)
- Updates (88)
- What is Mathematics (18)
- Women in science (9)

### Blogroll

- A CS Professor Blog
- A Hitchhiker's Guide to the Ivory Tower (Tony Feng)
- Accidental Mathematician
- Algorithmic Game Theory
- Analysis of Boolean functions
- Andreas Caicedo’s teaching pages
- Annoying Precision
- Anurag's math blog
- Area777
- Asaf Karagila
- Asymptotia
- Bits of DNA
- Computational complexity
- David Mumford
- Erdos problems on graphs
- Frank Morgan
- Freedom Math Dance
- Geomblog
- Geometry and the Imagination
- God Plays Dice
- Godel's lost letter and P=NP
- Gowers’s blog
- http://prelive.tricki.org/
- I am a Bandit (Sébastien Bubeck)
- Igor Pak's blog
- In theory
- John Baez
- Konard Swanepoel's Blog
- Kowalski’s Blog
- Low dimensional topology
- Machine learning (theory)
- Math Overflow
- Math with bad drawings
- Mathbabe
- Mathemata
- Mathematical Musing
- Mathematics without apologies by Michael Harris
- Matt Baker Math Blog
- Michael Nielsen
- My Biased Coin
- My Qstate
- n-category cafe
- NeverEndingBooks
- Noncommutative analysis
- Noncommutative geometry
- Oded Goldreich's choices
- Open Problems Garden
- OXdE
- Persiflage – Galois representations and more
- Peter Cameron's Blog
- Peter Sarnak’s letters (and more)
- Piece of mind
- Quantum Frontiers
- Quomodocumque
- Rigorous Trivialities
- Secret blogging seminar
- Shtetl Optimized
- Some plane truths (Adam Sheffer)
- Statistical Modeling
- Tanya Khovanova Math Blog
- TCS Math
- TCS stackexchange
- The Geometry Junkyard
- The Polymath Blog
- The Quantum Pontiff
- The Unapologetic Mathematician
- Theory of computing blog aggregator
- Thoughts by Emanuele Viola
- Thoughts by Emanuele Viola
- Tobias J. Osborne's research notes
- Todd’s and Vishal’s Blog
- Tricky wiki
- What’s new (Terry Tao)
- Windows on Theory
- xkcd
- דוד אסף על עניני מדינה ספרות ומדע – עונג שבת
- הבלוג של יעקב ריטוב
- נסיכת המדעים

### Archives

- February 2018 (3)
- January 2018 (8)
- December 2017 (5)
- November 2017 (6)
- October 2017 (11)
- September 2017 (6)
- August 2017 (3)
- June 2017 (1)
- May 2017 (3)
- April 2017 (4)
- March 2017 (4)
- February 2017 (5)
- January 2017 (6)
- December 2016 (1)
- November 2016 (1)
- October 2016 (2)
- September 2016 (1)
- August 2016 (1)
- July 2016 (2)
- May 2016 (5)
- April 2016 (5)
- March 2016 (1)
- January 2016 (2)
- December 2015 (1)
- November 2015 (2)
- October 2015 (3)
- September 2015 (1)
- August 2015 (4)
- May 2015 (2)
- April 2015 (4)
- March 2015 (7)
- February 2015 (4)
- January 2015 (2)
- December 2014 (8)
- November 2014 (2)
- October 2014 (2)
- September 2014 (1)
- August 2014 (4)
- July 2014 (3)
- June 2014 (3)
- May 2014 (3)
- March 2014 (2)
- February 2014 (2)
- January 2014 (3)
- November 2013 (2)
- October 2013 (3)
- September 2013 (9)
- August 2013 (3)
- July 2013 (3)
- June 2013 (3)
- May 2013 (10)
- April 2013 (8)
- March 2013 (9)
- February 2013 (2)
- January 2013 (4)
- December 2012 (5)
- November 2012 (3)
- October 2012 (1)
- August 2012 (2)
- July 2012 (2)
- June 2012 (5)
- May 2012 (2)
- April 2012 (5)
- March 2012 (4)
- February 2012 (2)
- January 2012 (2)
- December 2011 (4)
- November 2011 (3)
- October 2011 (2)
- September 2011 (2)
- August 2011 (3)
- July 2011 (3)
- June 2011 (4)
- April 2011 (1)
- February 2011 (3)
- January 2011 (6)
- November 2010 (8)
- October 2010 (9)
- September 2010 (1)
- August 2010 (1)
- July 2010 (1)
- June 2010 (4)
- May 2010 (3)
- April 2010 (1)
- March 2010 (3)
- February 2010 (10)
- January 2010 (9)
- December 2009 (7)
- November 2009 (5)
- October 2009 (1)
- September 2009 (3)
- August 2009 (9)
- July 2009 (12)
- June 2009 (11)
- May 2009 (12)
- April 2009 (12)
- March 2009 (10)
- February 2009 (10)
- January 2009 (11)
- December 2008 (13)
- November 2008 (12)
- October 2008 (5)
- September 2008 (8)
- August 2008 (6)
- July 2008 (8)
- June 2008 (13)
- May 2008 (11)
- April 2008 (1)

- Algebra and Number Theory Blogging Combinatorics Computer Science and Optimization Conferences Controversies and debates Convexity Convex polytopes Economics Games Geometry Guest blogger Mathematics over the Internet Mathematics to the rescue Obituary Open discussion Open problems Philosophy Physics Polymath3 Probability Quantum Rationality Taxi-and-other-stories Teaching Test your intuition Uncategorized Updates What is Mathematics Women in science

- Alex Lubotzky
- Aram Harrow
- Avi Wigderson
- Blogs
- Boolean functions
- Borsuk's conjecture
- Cap set problem
- Cap sets
- Codes
- Combinatorics
- Conferences
- Controversies
- Convex polytopes
- cryptography
- Debates
- Discrepancy
- Dorit Aharonov
- Economics
- Ehud Friedgut
- Endre Szemeredi
- Eran Nevo
- Extremal combinatorics
- Fault-tolerance
- g-conjecture
- Games
- Game theory
- Gina Says
- Greg Kuperberg
- Guy Kindler
- Helly type theorems
- Hirsch conjecture
- Influence
- Itai Benjamini
- Jean Bourgain
- Jeff Kahn
- Jerusalem
- Laci Lovasz
- Linear programming
- Mathematics to the rescue
- Mathoverflow
- Michal Linial
- Mittag-Leffler Institute
- Nati Linial
- Noga Alon
- Noise
- Noise-sensitivity
- Noise-stability
- Oded Schramm
- Paul Erdos
- Percolation
- Peter Frankl
- Philosophy
- Physics
- polymath1
- Polymath3
- Polytopes
- Probability
- Quantum computation
- Quantum computers
- Quantum error-correction
- Randomness
- Roth's theorem
- Scott Aaronson
- Sex
- sunflower conjecture
- Taxi-and-other-stories
- Terrence Tao
- Terry Tao
- Test your intuition
- Tim Gowers
- Topological combinatorics
- Trees
- Turan's problem
- Tverberg's theorem
- Updates

%d bloggers like this:

Hi Gil,

This is really off-topic, but the post reminded me of something I wanted to ask you. Feel free to ignore.

Question: Are there any versions of the KKL Theorem or of Friedgut’s theorem for distributions that are not product distributions? Specifically, I’m considering distributions D where 1/2<=D(x)/D(y)<=2 for any x and y that differ only by 1 coordinate. I only need something that works for monotone functions.

(For those who don’t know what the hell I’m talking about: Friedgut’s theorem says that if the influence of a boolean function f is k then f can be epsilon-approximated by a function that just depends on c^{k/eps} variables for some universal constant c. It holds even for product distributions mu_p^n, in which case c depends on p).

I need this for an application in learning theory. The application should be obvious to anyone who knows the (as far as I know) one and only use of Friedgut’s theorem in Learning Theory, but due to the location being public, I won’t say more.

One thing I can contribute is that the most basic theorem (what Friedgut calls KKL1 in his paper about "KKL and BKKL") is _not_ true. Consider the majority function, and then choose the distribution to be symmetric (i.e. D(x) depends only on the weight of x) and let D be smallest in the middle two layers, and increasing as fast as possible to both sides. A simple calculation shows that the total influence is o(1) (in fact, exponentially small).

(here I’m assuming that we define the influence like Friedgut does for product spaces, i.e. the naive way, Inf_f(i)=Pr_D(f(x) \neq f(x \xor i)). This definition makes sense to me, but alternatives might work out as well).

It it easy to see that MAJ with this distribution is a balanced function (for odd n), so KKL1 is not true. QED.

So, KKL1 doesn’t work. However, I actually need Friendgut’s Theorem, or maybe KKL2 or something. And then the task is to find a function of a small number of variables that approximates f, and that seems like maybe it would be true. Furthermore, I only need it for monotone functions.

Friedgut-Dinur do have a variant of BKKKL that works for monotone functions, but I can’t see how to use it. (I tried defining g(x)=f(x)*D(x) and applying Friedgut-Dinur or any continuous type of KKL thingy, but that doesn’t seem to be useful.

Part of the problem in proving anything is that I can’t get any variant of Fourier Analysis to be relevant. Of course I can’t base Fourier Analysis on D, since I need a basis of orthogonal functions. So I need to define a product space in some way. I tried to define p_i as P(x_i=1) and just using the corresponding orthonormal basis, but that didn’t work for me. I tried other things as well, but nothing works. I’m skeptical that anything like this might work. (But then again, back in Poland I was already skeptical).

What I’d really love to have is a combinatorial proof of Friedgut’s theorem or of some (possibly weaker) variant of KKL that doesn’t use Bonami-Beckner or Fourier Analysis at all, but just combinatorial arguments and maybe some applications of Cauchy-Schwartz. I understand that such a thing is not known? Before I understood how KKL works, my intuition told me that proving KKL combinatorially should be possible (over uniform distrib, let’s say), since you can remove one variable with small influence very easily, by "squishing" f, i.e. setting f'(x)=(f(x)+f(x \xor i))/2. So you could conceivably just repeat this for each variable with small influence, and do something clever to put it all together and avoid having to pay the price for each coordinate separately. My intuition might have been too-simplistic, as usual. I understand now that that’s where you use Fourier Analysis and Bonami-Beckner (in a way), exactly in order to avoid being punished by each coordinate seperately. And I don’t know if you can do this combinatorially.

Gosh, this turned out much longer than I planned. I just wanted to ask you the question from the first paragraph: is there a version of KKL/Friedgut’s Theorem for some class of non-product distribs, or a version that doesn’t use Fourier Analysis? It’s enough for me if it works just for monotone functions. Feel free to ignore the question. If you’re interested in discussing it, we can talk by email (or here, this might be fun — that’s why I’m posting here, it seems useful to have it on google as well).

For d=2 I’m getting an answer of about 1.9542589152342531. You can get length 2 very easily by taking two perpendicular sides of the square. But you can do better by taking a Steiner tree of three of the four square vertices, say the points at (0,0), (0,1), and (1,0), with a Steiner vertex at (x,x) where x=sqrt(3)/(2+2sqrt(3)). The tree has a diagonal edge from (0,0) with length sqrt(2)x, and two longer edges to the other two vertices with length sqrt(x^2+(1-x)^2), giving the total as calculated above. It cuts the square torus into a non-regular hexagon with 120-degree vertices that tiles the plane with the translational symmetries of the square tiling.

Guy, Anup, Avi and I will describe a solution showing f(3) < 2.801 in the journal version of our paper… 🙂

I must have miscalculated somewhere, because the solution I was trying to describe is the same as the one depicted in spherical cows “Spherical Cubes and Rounding in High Dimensions” but the length is different.

Dear Elad,

I have to think more about what you asked. Usually when you leave product measures things are difficult. I am aware of two papers in this direction. There is a result for FKG distributions that may interest you: Influence and sharp-threshold theorems for monotonic measures, by Ben Graham and Geoffry Geimmett http://front.math.ucdavis.edu/0505.5057 There is also a paper by Olle Haggstrom, Elchanan Mossel and me called “A Law of Large Numbers for Weighted Majority” http://front.math.ucdavis.edu/0406.5509. Both these paper uses a different notion of influence which is simply the correlation between the value of f and the value of .

Dear Gil,

Thank you very much for your useful advice! Looks like I have some reading to do. On a shallow look, none of the results in the papers seem to exactly be what I need, but the Graham-Grimmett paper has a proof idea (Thm. 2.10) that I never tried, and your paper with Olle and Elchanan contains a bunch of useful warnings.

Your paper with Olle and Elchanan actually shows that weird things happen when we consider arbitrary distributions (or even FKG distributions) and consider “effect” instead of “influence”. In my setting, I can use your notion of “effect”, but as you show, bad things happen. So I prefer my own version of “influence” which I believe might lead to less catastrophes. Here it is: it’s the same thing as your “effect”, but for the case x_i=1, I “re-normalize” the contribution of f(x) by multiplying it by D(x xor i)/D(x). Thus, if variable i has no effect on f, then my concept of influence will = 0, which is not the case for your “effect”, and this makes my definition “more right” ;). Another benefit of this definition is that it can be well-estimated for monotone f if you;re given a random oracle to the function f and a “membership” oracle to the distribution D. This is good for my learning application, since I actually need to compute these things. If I didn’t care about being able to compute it, I could just define it in the classic way, of just choosing a random x according to D, and checking what’s the probability that f(x)~=f(x xor i). In fact, for my class of distributions, this is related to my definition by a multiplicative constant, I think.

Anyway, just wanted to point out that maybe the weakness you prove in your paper with Olle and Elchanan might come from a problematic definition of “effect”, where the effect of variable i might be non-zero even if it does not affect the value of the function.

But I’m doing something bad and talking about papers that i haven’t given enough attention to. I’ll keep reading and say if I managed to get something interesting. Please tell me if you remember anything else that might be relevant.

Thanks again Gil!!

P.S. on a side note, I really liked the explanation of Condorcet’s Jury Theorem in your paper. Someone should have told Feynman about it, and explained to him that rather than yelling about the textbook committee members and acting like a volcano, he should just convince them to use majority voting rather than averaging on the reviews that they receive. And then the committee should also majority-vote as well. Because, apparently, majority vote of almost-junk is not junk at all. This managed to surprise me since I never thought about it.

Pingback: Download Jamie Foxx songs

Pingback: Answer to Test Your Intuition (3) « Combinatorics and more

Pingback: Test Your Intuition (4) « Combinatorics and more

Pingback: Answer To Test Your Intuition (4) « Combinatorics and more