Sensitivity Conjecture Resolved
scottaaronson.com
scottaaronson.com
For example (with n=64), if you take any set of 1+2^63 (or more) 64-bit words, then for some word in this set, there will be at least 8 other words in the set that each differ from this word in only one of the 64 bit positions.
To illustrate, here's a brute-force verification in Python for the n=4 case, that tries all (16 choose 9) = 11440 subsets:
import itertools
n = 4
m = 2
def degree(word, s):
"""How many other words differ in one bit position"""
return sum(1 for w in s if bin(word ^ w).count('1') == 1)
words = range(2**n) # All n-bit words
for s in itertools.combinations(words, 1 + 2**(n-1)):
assert any(degree(word, s) >= m for word in s)
Whenever there’s an announcement like this, ~99% of the time either the proof is wrong, or at any rate it’s way too complicated for outsiders to evaluate it quickly. This is one of the remaining 1% of cases. I’m rather confident that the proof is right. Why? Because I read and understood it. It took me about half an hour. If you’re comfortable with concepts like induced subgraph and eigenvalue, you can do the same."
The celebrated pigeonhole principle says...
If we have disjoint sets S_1, S_2, ..., S_m subsets in [n]
each of size s, then m (the number of sets) is at most [n/s].
Suppose that instead of being disjoint, we require that every
pair of sets has intersection at most 1. How much can this
change the maximum number of sets m? Is it still roughly n/s,
or could the number be much larger?
Interestingly, it turns out that there is a sharp phase
transition at s = √n .
[1] Interval (graph theory) https://en.wikipedia.org/wiki/Interval_(graph_theory)
[2] Flow Graph Theory http://infolab.stanford.edu/~ullman/dragon/w06/lectures/dfa3...
[3] Does robustness imply tractability? A lower bound for planted clique in the semi-random model (2018) - Jacob Steinhardt, Stanford https://arxiv.org/pdf/1704.05120.pdf
There are some biggie problems out there having to do with combinations of discrete things, optimization with such things, etc. For example, this challenge led to the question P versus NP. Bluntly, there is a big supply of potentially tasty nuts there we are unable to crack or poor at cracking.
If want to crack those nuts, e.g., have something "useful", then likely we have to back off on a direct attack via some one bright idea, technique, paper, and chunk of code. Instead, we have to, say, build a foundation, circle around the problem and look for entering wedges, construct some tools, look for related, seeming somewhat promising smaller results that in time we could build on to make progress to the real goal of being good at cracking those tasty nuts.
So, right, maybe we are not sure yet that some result will be useful -- that's sad but just part of the challenge of cracking those nuts. They are tasty but tough nuts to crack. Moreover, such results are about the best we see; we should take, and take seriously, the best we do see.
So, that's part of how research works, for much of the best we know how to do, in pure and applied math. Yes, I know; I know; they don't always make this aspect of research fully clear in freshman calculus!!!
George Polya in his book "How To Solve It?" encourages to think about "What is the easiest problem that you cannot solve yet?" Most theoretical results tend to answer this, and this principle is a good guideline for theoretical research.