[HN Gopher] In highly connected networks, there's always a loop
___________________________________________________________________
In highly connected networks, there's always a loop
Author : headalgorithm
Score : 108 points
Date : 2024-06-07 15:45 UTC (2 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.
| adzm wrote:
| I can't even think of a hash function that maps 0 to 0
| foota wrote:
| 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.
| ithinkso wrote:
| > 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
| 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.
| marvel_boy wrote:
| > ing the Data Encryption Standard method (DES), which is
| a widely-used method of data encryption.
|
| No, it is not. Today AES is preferred.
| denton-scratch wrote:
| It was published in 2006.
| 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 ?
| ororroro wrote:
| 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.
| noqc wrote:
| 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.
| 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|.
| jgalt212 wrote:
| 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).
___________________________________________________________________
(page generated 2024-06-09 23:02 UTC)