In highly connected networks, there's always a loop | Hacker News Reader

In highly connected networks, there's always a loop

quantamagazine.org

118 pointsheadalgorithm22 comments

In case the author is reading, some places that could be clarified:

> Scatter a bunch of points in a plane. Connect some of them with lines. That’s all a graph is.

This may mislead the uninitiated reader to think that the definition of a graph includes vertex locations in R^2.

> Over the years, mathematicians worked to reduce the number of edges Hamiltonian graphs had to have.

The article is about showing that certain graph properties guarantee the existence of a Hamiltonian cycle. But the logical structure of this sentence implies the converse: showing that the existence of a Hamiltonian cycle guarantees other properties. But all it guarantees is |E| >= |V|.

Here is the paper in arxiv the article is refering to for anyone else interested https://arxiv.org/abs/2402.06603

Though maybe just the proof outline section is enough for a Saturday.

> It just seems like this is bound to be useful.

If (a) it's hard to find cycles in a graph, and (b) it's not hard to construct a graph with a cycle, that sounds to me like the makings of a trapdoor function that could be useful in cryptography.

[I'm neither a mathematician nor a cryptographer]

Nit: It's only hard to find _hamiltonian_ cycles, finding general cycles is trivial. More generally, it's hard to find long simple cycles (a simple cycle is one with no overlapping vertices visited twice).

I don't know how hard it is to generate graphs that are hard to find simple cycles in though. For example, previous work showed that random graphs are likely to contain hamiltonian cycles (and with this algorithm they can now be found).

Take your favorite hash function, and view it as inducing a directed graph on the set of its possible outputs. Finding a cycle is hard! (except, most hash functions map 0->0 for "nothing up my sleeves" appeal)

But also, it's ridiculously hard to answer simple questions about such graphs, such as listing its nodes.

I can't even think of a hash function that maps 0 to 0

Since there are uncountably many functions, the functions we can think of have measure zero in the set of all functions.

Interestingly, CRC32C is a bijective function over 4 byte integers.

More generally, any perfect minimal hashing function could be used to map a set of N integers to the numbers 1 through N.

> Finding a cycle is hard!

I mean, it is easy in the size of the graph, you constructed implicitly an exponentially large graph, I don't think it's in the spirit of GP point where the hamiltonian cycle is exponentially (in the size of the graph) hard to find

> that could be useful in cryptography.

See related Neural Cryptography https://en.wikipedia.org/wiki/Neural_cryptography

Thanks; interesting. Sounds like it's mainly to do with cryptanalysis and key-exchange.

See https://en.wikipedia.org/wiki/Neural_cryptography#Applicatio...

> One example of a public-key protocol is given by Khalil Shihab. He describes the decryption scheme and the public key creation that are based on a backpropagation neural network.

Which leads to this paper by Khalil Shihab (2006)

https://web.archive.org/web/20070712012959/http://www.scipub...

> Abstract: In this paper, an efficient and scalable technique for computer network security is presented. On one hand, the decryption scheme and the public key creation used in this work are based on a multi-layer neural network that is trained by backpropagation learning algorithm. On the other hand, the encryption scheme and the private key creation process are based on Boolean algebra. This is a new potential source for public key cryptographic schemes which are not based on number theoretic functions and have small time and memory complexities. This paper along with test results show that the possibility of guessing keys is extremely weaker than using the Data Encryption Standard method (DES), which is a widely-used method of data encryption. The presented results are obtained through the use of MATLAB 6.5.1 software.

> ing the Data Encryption Standard method (DES), which is a widely-used method of data encryption.

No, it is not. Today AES is preferred.

It was published in 2006.

there’s a quote at the end, saying this establishes a fundamental connection between two objects which are central to computer science.

The quote leaves those two objects unnamed. Are they supposed to be “graphs” and “groups”?

> It proves, for instance, that certain types of graphs that have to do with groups, called Cayley graphs, must have Hamiltonian cycles

Yes, graphs and groups.

So annoyingly the paper doesn't explicitly state the constant they got, but from a brief skim it looks like it's, like, 10^15?? I really hope someone can improve that...

I wonder if this can be used to prove if all substantial React apps include cycles--even if the raison d'etre of React is one-way data flow (i.e. no cycles).

This quanta title has to be rage bait. I don't think they could have constructed a more annoying title.

Could you elaborate ?

I am not an expert but it looks like the quanta author has invented a definition for "highly connected" because C-expander was too complicated a concept for them (me too). There are older competing definitions for "highly connected" along the lines of a graph where the number of edges is greater then half the number of vertices which is obviously insufficient to guarantee a loop.

Then they have used networks instead of graphs and added a comma, for no apparent reason.

Sure, a graph is connected if it has a spanning tree, which requires |E|>=|V|-1. Presumably a graph is only highly connected if it has more edges than this minimal requirement, so we have |E|>=|V|, and this graph must have a loop.

Reply on news.ycombinator.com