commit 627fa0aafcf92d7331a8195e4d69eabb43f6299e
parent 45c58f0900b456aea664c84328d5a626ede91210
Author: Nils Gillmann <ng0@n0.is>
Date: Sun, 7 Oct 2018 20:09:17 +0000
bib: non-ascii fixes.
Signed-off-by: Nils Gillmann <ng0@n0.is>
Diffstat:
1 file changed, 2 insertions(+), 2 deletions(-)
diff --git a/gnunetbib.bib b/gnunetbib.bib
@@ -10225,7 +10225,7 @@ Specifically, we implement a variant of a recently proposed technique that passi
publisher = {Society for Industrial and Applied Mathematics},
organization = {Society for Industrial and Applied Mathematics},
address = {New Orleans, Louisiana},
- abstract = {We consider a model for monitoring the connectivity of a network subject to node or edge failures. In particular, we are concerned with detecting ({\epsilon}, k)-failures: events in which an adversary deletes up to network elements (nodes or edges), after which there are two sets of nodes A and B, each at least an {\epsilon} fraction of the network, that are disconnected from one another. We say that a set D of nodes is an ({\epsilon} k)-detection set if, for any ({\epsilon} k)-failure of the network, some two nodes in D are no longer able to communicate; in this way, D "witnesses" any such failure. Recent results show that for any graph G, there is an is ({\epsilon} k)-detection set of size bounded by a polynomial in k and {\epsilon}, independent of the size of G.In this paper, we expose some relationships between bounds on detection sets and the edge-connectivity λ and node-connectivity κ of the underlying graph. Specifically, we show that detection set bounds can be made considerably stronger when parameterized by these connectivity values. We show that for an adversary that can delete κλ edges, there is always a detection set of size O((κ/{\epsilon}) log (1/{\epsilon})) which can be found by random sampling. Moreover, an ({\epsilon}, \&lambda)-detection set of minimum size (which is at most 1/{\epsilon}) can be computed in polynomial time. A crucial point is that these bounds are independent not just of the size of G but also of the value of λ.Extending these bounds to node failures is much more challenging. The most technically difficult result of this paper is that a random sample of O((κ/{\epsilon}) log (1/{\epsilon})) nodes is a detection set for adversaries that can delete a number of nodes up to κ, the node-connectivity.For the case of edge-failures we use VC-dimension techniques and the cactus representation of all minimum edge-cuts of a graph; for node failures, we develop a novel approach for working with the much more complex set of all minimum node-cuts of a graph},
+ abstract = {We consider a model for monitoring the connectivity of a network subject to node or edge failures. In particular, we are concerned with detecting ({\epsilon}, k)-failures: events in which an adversary deletes up to network elements (nodes or edges), after which there are two sets of nodes A and B, each at least an {\epsilon} fraction of the network, that are disconnected from one another. We say that a set D of nodes is an ({\epsilon} k)-detection set if, for any ({\epsilon} k)-failure of the network, some two nodes in D are no longer able to communicate; in this way, D "witnesses" any such failure. Recent results show that for any graph G, there is an is ({\epsilon} k)-detection set of size bounded by a polynomial in k and {\epsilon}, independent of the size of G.In this paper, we expose some relationships between bounds on detection sets and the edge-connectivity {\lambda} and node-connectivity {\kappa} of the underlying graph. Specifically, we show that detection set bounds can be made considerably stronger when parameterized by these connectivity values. We show that for an adversary that can delete {\kappa}{\lambda} edges, there is always a detection set of size O(({\kappa}/{\epsilon}) log (1/{\epsilon})) which can be found by random sampling. Moreover, an ({\epsilon}, \&lambda)-detection set of minimum size (which is at most 1/{\epsilon}) can be computed in polynomial time. A crucial point is that these bounds are independent not just of the size of G but also of the value of {\lambda}.Extending these bounds to node failures is much more challenging. The most technically difficult result of this paper is that a random sample of O(({\kappa}/{\epsilon}) log (1/{\epsilon})) nodes is a detection set for adversaries that can delete a number of nodes up to {\kappa}, the node-connectivity.For the case of edge-failures we use VC-dimension techniques and the cactus representation of all minimum edge-cuts of a graph; for node failures, we develop a novel approach for working with the much more complex set of all minimum node-cuts of a graph},
keywords = {failure detection, graph connectivity, network},
isbn = {0-89871-558-X},
www_section = {http://dl.acm.org/citation.cfm?id=982792.982803},
@@ -14242,7 +14242,7 @@ We then show how these building blocks can be used for applying the scheme to ef
pages = {89--98},
abstract = {A Private Information Retrieval (PIR) protocol enables a user to retrieve a data item from a database while hiding the identity of the item being retrieved. In a t-private, k-server PIR protocol the database is replicated among k servers, and the user{\textquoteright}s privacy is protected from any collusion of up to t servers. The main cost-measure of such protocols is the communication complexity of retrieving a single bit of data.
This work addresses the information-theoretic setting for PIR, in which the user{\textquoteright}s privacy should be unconditionally protected from collusions of servers. We present a unified general construction, whose abstract components can be instantiated to yield both old and new families of PIR protocols. A main ingredient in the new protocols is a generalization of a solution by Babai, Kimmel, and Lokam to a communication complexity problem in the so-called simultaneous messages model.
-Our construction strictly improves upon previous constructions and resolves some previous anomalies. In particular, we obtain: (1) t-private k-server PIR protocols with O(n 1/⌊ (2k-1)/tc⌋) communication bits, where n is the database size. For t > 1, this is a substantial asymptotic improvement over the previous state of the art; (2) a constant-factor improvement in the communication complexity of 1-private PIR, providing the first improvement to the 2-server case since PIR protocols were introduced; (3) efficient PIR protocols with logarithmic query length. The latter protocols have applications to the construction of efficient families of locally decodable codes over large alphabets and to PIR protocols with reduced work by the servers},
+Our construction strictly improves upon previous constructions and resolves some previous anomalies. In particular, we obtain: (1) t-private k-server PIR protocols with O(n 1/{\lfllor} (2k-1)/tc{\rfloor}) communication bits, where n is the database size. For t > 1, this is a substantial asymptotic improvement over the previous state of the art; (2) a constant-factor improvement in the communication complexity of 1-private PIR, providing the first improvement to the 2-server case since PIR protocols were introduced; (3) efficient PIR protocols with logarithmic query length. The latter protocols have applications to the construction of efficient families of locally decodable codes over large alphabets and to PIR protocols with reduced work by the servers},
keywords = {communication complexity, privacy, private information retrieval},
isbn = {978-3-540-42287-7},
issn = {0302-9743},
