91–100 of 107 posts
Earlier quoted context omitted.
Huang Hao. Chinese family name姓 first
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?
Earlier quoted context omitted.
It's a shortcut, they're not literally invoking "God". It's an encoding of: We don't know what the optimum is, but we can imagine the complete set of possible things, and from those there will be one that's best. So that's the optimum, and we want to refer to it. We don't know what it is, but we assume it exists, so let's just call it 'God's solution'
> we can imagine the complete set of possible things, and from those there will be one that's best. Not necessarily, unless we make some more assumptions about the set of proofs and/or the proof goodness function ;)
And, as there are only finitely many proofs of any finite length, then the supremum of proof quality over any proofs of that theorem, is attained. (whether there is usually unique proof which attains it, I don't care to guess.)
Earlier quoted context omitted.
I agree, it's extremely distasteful. I feel the author has cut their teeth writing clickbait headlines to make information extraction harder, the way a supermarket puts the milk at the far corner of the store. I want a link/cite to the original paper in the first para.
> the way a supermarket puts the milk at the far corner of the store I never noticed, but I can only recall a single instance from a set of 10 or so where that isn't the case. Any links on related content to the topic?
Earlier quoted context omitted.
Kind of makes this seem funny in retrospect: > Aaronson and O’Donnell both called Huang’s paper the “book” proof of the sensitivity conjecture, referring to Paul Erdős’ notion of a celestial book in which God writes the perfect proof of every theorem. “I find it hard to imagine that even God knows how to prove the Sensitivity Conjecture in any simpler way than this,” Aaronson wrote.
A few comments below a guy called Don Knuth claims to have shortened the proof to one page https://www.scottaaronson.com/blog/?p=4229#comment-1815290
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…
FWIW, I found your explanation helpful, but introducing two colours confused it needlessly for me. I'd say: You have a hypercube of dimension n with 2^n vertices, and you start colouring one after another of them, without having any two adjacent vertices coloured. You'll find that you can mark half of them (that is, 2^(n-1)) without any having a coloured neighbour (basically, you always go diagonal) - but as soon as…
Earlier quoted context omitted.
Huang Hao. Chinese family name姓 first
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?
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's name comes first[0], e.g. the ex-chess world champion Vishy Anand's name is Viswanathan Anand – Anand was/is actually his given name, but it's treated by english speakers as his surname. I read an interview where he said even he doesn't know any more which is his surname and which his first name hehe.
[0] Same in Hungarian, but always converted to given-family in english.
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…
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
What have I misunderstood?
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…
Earlier quoted context omitted.
FWIW, I found your explanation helpful, but introducing two colours confused it needlessly for me. I'd say: You have a hypercube of dimension n with 2^n vertices, and you start colouring one after another of them, without having any two adjacent vertices coloured. You'll find that you can mark half of them (that is, 2^(n-1)) without any having a coloured neighbour (basically, you always go diagonal) - but as soon as…
That's not the same thing. As a simple counter-example to what you're saying, given a 3D cube you can colour every vertex with either red or blue such that adjacent vertices are different colours.
> 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).
Earlier quoted context omitted.
That's not the same thing. As a simple counter-example to what you're saying, given a 3D cube you can colour every vertex with either red or blue such that adjacent vertices are different colours.
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)…