Mathematician Solves Sensitivity Conjecture in Two Pages (2019) • Hacker News Board

Re: Mathematician Solves Sensitivity Conjecture in Two Pages (2019)

#101

Post by rocqua » Sat, Feb 13, 2021, 12:13 PM UTC

twic wrote: post #97

LolWolf wrote: post #26

The sensitivity conjecture is actually pretty simple to understand, intuitively. (Its reduction to applications, and its proof, of course, are both a little bit more of the "magical" parts so-to-speak.) The 'canonical' way of thinking about it is in terms of the hypercube graph , which is defined in the following way: - The dimension-0 hypercube graph is... just a single vertex. . - The dimension-1 hypercube graph is…

> So, it turns out (and I will give it to you as an exercise!) that you can color 2ⁿ⁻¹ vertices of the cube with two colors without any vertices of a single color being adjacant to each other For n=3, a three-dimensional cube, you're saying I can colour four vertices. But I can colour all eight. r --- g |\ |\ | g --+ r | | | | g +-- r | \| \| r --- g And I think there's a simple method to take a completely coloured n…

The actual paper is rather easy to understand [1]. I glanced through it for a bit. Your construction of "Make a copy, flip the colors, the connect corresponding vertices" is very similar to the construction of the matrix A used in lemma 2.2

This matrix is essentially the adjacency-matrix of the hyper-cube, except with a few minus signs. Take the hyper-cube to have weighted edges of either 1 or -1, then the construction is. Take two hyper cubes, connect them, flip the sign of all internal connections in one of the cubes.

[1] http://www.mathcs.emory.edu/~hhuan30/papers/sensitivity_1.pd...

Re: Mathematician Solves Sensitivity Conjecture in Two Pages (2019)

#102

Post by jjgreen » Sat, Feb 13, 2021, 1:37 PM UTC

yesenadam wrote: post #96

jjgreen wrote: post #87

Earlier quoted context omitted.

It is notable that in English, Chinese names are generally written given-family, but in French the original family-given order is preserved. I'm curious how other languages handle this -- any takers?

> in English, Chinese names are generally written given-family Is that right? All the famous Chinese people I can think of are known in english by the family name first. Names of Chinese players of chess are always family-given in english. I read after a moment's google that "Chinese people working in western countries usually adopt western order", maybe that's it. Indian names I believe are similar, family or parent…

Possibly this depends on the subculture. One example picked at random, the (fabulous) film Black coal, thin ice is reported in Cahiers du Cinema as directed by Diao Yinan [1], but in IMDb as by Yi'nan Diao [2]

[1] https://www.cahiersducinema.com/produit/juin-2014-n-701/

[2] https://www.imdb.com/title/tt3469910/

Re: Mathematician Solves Sensitivity Conjecture in Two Pages (2019)

#103

Post by LolWolf » Sat, Feb 13, 2021, 5:36 PM UTC

ColinWright wrote: post #100

codethief wrote: post #99

Earlier quoted context omitted.

I don't see the contradiction. In fact, Donald Knuth's simplified proof[0] phrases it exactly[1] the same way as GP: > Theorem. Any set H of 2ⁿ⁻¹+1 vertices of the n-cube contains a vertex with a least √n neighbors in H. [0]: https://www.cs.stanford.edu/~knuth/papers/huang.pdf [1]: Or almost exactly. The only difference being that Knuth's version does not make any assumptions on the set H (apart from its cardinality)…

OK, I've mis-understood what people are saying. I often find these colloquial re-phrasings more difficult and convoluted than the precise and exact statements, but perhaps my confusion will serve others in thinking through things.

Oh, I think both of these statements are quite precise (in the sense that reading them and turning them into math is rather immediate). Otoh, you are right and we are saying different things: I’m giving an equivalent formulation with a two-coloring (but there’s a bit of work to actually map it to the original problem) while the other post gives a direct formulation (though the “colors” part of the coloring is irrelevant, in that latter case).

Re: Mathematician Solves Sensitivity Conjecture in Two Pages (2019)

#104

Post by LolWolf » Sat, Feb 13, 2021, 5:41 PM UTC

codethief wrote: post #98

twic wrote: post #97

Earlier quoted context omitted.

> So, it turns out (and I will give it to you as an exercise!) that you can color 2ⁿ⁻¹ vertices of the cube with two colors without any vertices of a single color being adjacant to each other For n=3, a three-dimensional cube, you're saying I can colour four vertices. But I can colour all eight. r --- g |\ |\ | g --+ r | | | | g +-- r | \| \| r --- g And I think there's a simple method to take a completely coloured n…

I don't think you misunderstood (or at least I interpreted GP's post the same way). I suppose GP meant to say that you can color all 2ⁿ vertices of the n-dimensional cube such that precisely half of them (2ⁿ⁻¹) are red and half of them are green and such that no vertices of a single color are adjacent to each other.

Yes! Sorry, I mixed up two sentences in my head there. I meant to say that you can color 2ⁿ⁻¹ green and 2ⁿ⁻¹ red (or, alternatively, you can color all 2ⁿ vertices with one of green or red) such that no two vertices of the same color share an edge. (Which is what you describe!)

It’s a bit late for me to edit now, but alas :)

Re: Mathematician Solves Sensitivity Conjecture in Two Pages (2019)

#105

Post by TheRealPomax » Sat, Feb 13, 2021, 8:34 PM UTC

ahmedalsudani wrote: post #46

TheRealPomax wrote: post #35

When of course, in reality rather than clickbaity titles, they only wrote up the final, concise proof using two pages _after_ thinking about, and working on, the problem for seven years, building on decades of specific research combined with seven years of learning new mathematics (new to Huang, not necessarily new to the world) that might offer ways into cracking this problem.

Nothing clickbaity about the title. It says two pages without describing how much effort went into those two pages. Two pages does not imply it's easy. It implies it's elegant, which probably requires a fair amount of effort.

It's great that you know that, but unfortunately most of the world does not.

Re: Mathematician Solves Sensitivity Conjecture in Two Pages (2019)

#106

Post by MichaelBurge » Sat, Feb 13, 2021, 9:35 PM UTC

LolWolf wrote: post #26

The sensitivity conjecture is actually pretty simple to understand, intuitively. (Its reduction to applications, and its proof, of course, are both a little bit more of the "magical" parts so-to-speak.) The 'canonical' way of thinking about it is in terms of the hypercube graph , which is defined in the following way: - The dimension-0 hypercube graph is... just a single vertex. . - The dimension-1 hypercube graph is…

Let v be a vertex in a N-dimensional hypercube. Assume it's colored C. It has N neighbors, which must be colored ~C if we're using 2 colors.

If you change v to ~C, v now has N neighbors with the same color. This improves on the √N you're giving.

What did I misunderstand?

Re: Mathematician Solves Sensitivity Conjecture in Two Pages (2019)

#107

Post by LolWolf » Sun, Feb 14, 2021, 10:19 PM UTC

MichaelBurge wrote: post #106

LolWolf wrote: post #26

The sensitivity conjecture is actually pretty simple to understand, intuitively. (Its reduction to applications, and its proof, of course, are both a little bit more of the "magical" parts so-to-speak.) The 'canonical' way of thinking about it is in terms of the hypercube graph , which is defined in the following way: - The dimension-0 hypercube graph is... just a single vertex. . - The dimension-1 hypercube graph is…

Let v be a vertex in a N-dimensional hypercube. Assume it's colored C. It has N neighbors, which must be colored ~C if we're using 2 colors. If you change v to ~C, v now has N neighbors with the same color. This improves on the √N you're giving. What did I misunderstand?

Well, turns out you’re completely right and I fucked up my reduction (quite badly it seems)! Alas, it also turns out I can’t edit nor delete the post, so, hopefully people get this far down the thread and read this :)