[HN Gopher] In highly connected networks, there's always a loop
___________________________________________________________________
In highly connected networks, there's always a loop
Author : headalgorithm
Score : 70 points
Date : 2024-06-07 15:45 UTC (1 days ago)
(HTM) web link (www.quantamagazine.org)
(TXT) w3m dump (www.quantamagazine.org)
| SteveJS wrote:
| 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"?
| nyrikki wrote:
| > 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.
| kwstas wrote:
| 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.
| denton-scratch wrote:
| > 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]
| foota wrote:
| 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).
| klyrs wrote:
| 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.
| dustfinger wrote:
| > that could be useful in cryptography.
|
| See related Neural Cryptography
| https://en.wikipedia.org/wiki/Neural_cryptography
| denton-scratch wrote:
| Thanks; interesting. Sounds like it's mainly to do with
| cryptanalysis and key-exchange.
| dustfinger wrote:
| See https://en.wikipedia.org/wiki/Neural_cryptography#Appli
| catio...
|
| > 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.scipu
| b...
|
| > 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.
| Sniffnoy wrote:
| 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...
| noqc wrote:
| This quanta title has to be rage bait. I don't think they could
| have constructed a more annoying title.
| PartiallyTyped wrote:
| Could you elaborate ?
| blt wrote:
| 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|.
___________________________________________________________________
(page generated 2024-06-08 23:00 UTC)