It does a decent job of conveying the essential idea for a broader readership: perturb a graph through its adjacency matrix just enough to make the universality conjecture hold for the distribution of eigenvalues -> analytically establish that the perturbation was so small that the result would carry back to the original adjacency matrix (I imagine this is an analytical estimate bounding the distance between distributions in terms of the perturbation) -> use the determined distribution to study the probability of the second eigenvalue being concentrated around the Alon-Bopanna number.
I haven't had a chance to read the paper and don't work in graph theory but close enough to have enjoyed the article.
Might be fruitful to apply this on p2p mesh networks.
I suppose you should be able to make a model describing how the relationship between the fraction of byzantine nodes affects the probability distribution of connectedness. Then you could figure out what algorithm parameters would put you within desired bounds for tolerated ratios of byzantine.
Byzantine has I think been misused. It’s the least number of good members you need to be successful, not the best number. I think there’s a reason parliamentary systems have a supermajority rule for making certain kinds of changes and a simple majority for others and we should probably be doing the same when we model systems.
It is simple enough for an adversarial system to subvert some members via collusion and others via obstruction. Take something like Consul which can elect new members and remove old ones (often necessary in modern cloud architectures). What does 50.1% mean when the divisor can be changed?
And meshes are extremely weird because the whole point is to connect nodes that cannot mutually see each other. It is quite difficult to know for sure if you’re hallucinating the existence of a node two hops away from yourself. You’ve never seen each other, except maybe when the weather was just right one day months ago.
Asking a candidate to solve proofs for a typical SWE interview in 2025 tells you that they don't know how to hire and likely google'd the answers before the interview themselves.
Unless you are a research scientist at an AI research company or top hedge fund, the interviewer should be best prepared to answer why they really need someone to know these proofs in their actual job.
> The fraction turned out to be approximately 69%, making the graphs neither common nor rare.
The wording kinda bothers me... Either 31% or 69% is exceedingly common.
Rare would be asymptotically few, or constant but smaller than e.g. 1 in 2^256.
I guess the article covers it's working definition of common, ever so briefly:
> that if you randomly select a graph from a large bucket of possibilities, you can practically guarantee it to be an optimal expander.
So it's not a reliable property, either way.
The article reads as written by someone who just learned about graphs, it focuses so much on the bet and so less on explaining Ramanujan expanders
Not sure I agree.
It does a decent job of conveying the essential idea for a broader readership: perturb a graph through its adjacency matrix just enough to make the universality conjecture hold for the distribution of eigenvalues -> analytically establish that the perturbation was so small that the result would carry back to the original adjacency matrix (I imagine this is an analytical estimate bounding the distance between distributions in terms of the perturbation) -> use the determined distribution to study the probability of the second eigenvalue being concentrated around the Alon-Bopanna number.
I haven't had a chance to read the paper and don't work in graph theory but close enough to have enjoyed the article.
I agree with you, I work with graph algebra libraries and this article did a very nice job.
Might be fruitful to apply this on p2p mesh networks. I suppose you should be able to make a model describing how the relationship between the fraction of byzantine nodes affects the probability distribution of connectedness. Then you could figure out what algorithm parameters would put you within desired bounds for tolerated ratios of byzantine.
Byzantine has I think been misused. It’s the least number of good members you need to be successful, not the best number. I think there’s a reason parliamentary systems have a supermajority rule for making certain kinds of changes and a simple majority for others and we should probably be doing the same when we model systems.
It is simple enough for an adversarial system to subvert some members via collusion and others via obstruction. Take something like Consul which can elect new members and remove old ones (often necessary in modern cloud architectures). What does 50.1% mean when the divisor can be changed?
And meshes are extremely weird because the whole point is to connect nodes that cannot mutually see each other. It is quite difficult to know for sure if you’re hallucinating the existence of a node two hops away from yourself. You’ve never seen each other, except maybe when the weather was just right one day months ago.
Coming to a leetcode interview soon near you!
Asking a candidate to solve proofs for a typical SWE interview in 2025 tells you that they don't know how to hire and likely google'd the answers before the interview themselves.
Unless you are a research scientist at an AI research company or top hedge fund, the interviewer should be best prepared to answer why they really need someone to know these proofs in their actual job.