Detecting tampering in a random hypercube (Q388876): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
| Property / review text | |||
Let us assume the graph of the hypercube \(H_2^n\), and let us consider its random subgraph obtained by deleting each edge with probability \(1-p_n\). Another measure on subgraphs of \(H_2^n\) can be obtained by additionally adding edges along a randomly chosen geodesic (that is, a path which makes one step in every of the \(n\) directions). Yet another measure can be obtained by adding edges along a randomly chosen geodesic starting at a fixed vertex of the hypecube. These additional modifications are called ``tamperings''. The paper studies the question how different these three measures are. The qualitative asymptotic behavior of the total variation distance of these measures as a function of \(p_n\)'s is described. | |||
| Property / review text: Let us assume the graph of the hypercube \(H_2^n\), and let us consider its random subgraph obtained by deleting each edge with probability \(1-p_n\). Another measure on subgraphs of \(H_2^n\) can be obtained by additionally adding edges along a randomly chosen geodesic (that is, a path which makes one step in every of the \(n\) directions). Yet another measure can be obtained by adding edges along a randomly chosen geodesic starting at a fixed vertex of the hypecube. These additional modifications are called ``tamperings''. The paper studies the question how different these three measures are. The qualitative asymptotic behavior of the total variation distance of these measures as a function of \(p_n\)'s is described. / rank | |||
Normal rank | |||
| Property / reviewed by | |||
| Property / reviewed by: Jan Hladký / rank | |||
Normal rank | |||
| Property / Mathematics Subject Classification ID | |||
| Property / Mathematics Subject Classification ID: 05C80 / rank | |||
Normal rank | |||
| Property / Mathematics Subject Classification ID | |||
| Property / Mathematics Subject Classification ID: 60C05 / rank | |||
Normal rank | |||
| Property / zbMATH DE Number | |||
| Property / zbMATH DE Number: 6247197 / rank | |||
Normal rank | |||
| Property / zbMATH Keywords | |||
random graph | |||
| Property / zbMATH Keywords: random graph / rank | |||
Normal rank | |||
| Property / zbMATH Keywords | |||
random hypercube | |||
| Property / zbMATH Keywords: random hypercube / rank | |||
Normal rank | |||
Revision as of 13:34, 29 June 2023
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Detecting tampering in a random hypercube |
scientific article |
Statements
Detecting tampering in a random hypercube (English)
0 references
17 January 2014
0 references
Let us assume the graph of the hypercube \(H_2^n\), and let us consider its random subgraph obtained by deleting each edge with probability \(1-p_n\). Another measure on subgraphs of \(H_2^n\) can be obtained by additionally adding edges along a randomly chosen geodesic (that is, a path which makes one step in every of the \(n\) directions). Yet another measure can be obtained by adding edges along a randomly chosen geodesic starting at a fixed vertex of the hypecube. These additional modifications are called ``tamperings''. The paper studies the question how different these three measures are. The qualitative asymptotic behavior of the total variation distance of these measures as a function of \(p_n\)'s is described.
0 references
random graph
0 references
random hypercube
0 references
