[HN Gopher] New Proof Settles Decades-Old Bet About Connected Ne...
___________________________________________________________________
New Proof Settles Decades-Old Bet About Connected Networks
Author : rbanffy
Score : 55 points
Date : 2025-04-20 17:48 UTC (5 hours ago)
(HTM) web link (www.quantamagazine.org)
(TXT) w3m dump (www.quantamagazine.org)
| 3np wrote:
| 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.
| hinkley wrote:
| 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.
| juancroldan wrote:
| 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
| krnsll wrote:
| 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.
| michelpp wrote:
| I agree with you, I work with graph algebra libraries and
| this article did a very nice job.
| franktankbank wrote:
| Coming to a leetcode interview soon near you!
| rvz wrote:
| 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.
| jlrubin wrote:
| > 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.
___________________________________________________________________
(page generated 2025-04-20 23:00 UTC)