waashk/dblp huggingface dataset:
is the internet fractal? one of the main benefits of multicast communication is the overall reduction of network load. to quantify this reduction, when compared to traditional unicast, experimental studies by chuang and sirbu indicated the so called power law which asserts that the ratio r(n) of the average number of links in a multicast delivery tree connecting n sites to the average number of links in a unicast path is &theta;(n0.8). our goal is to explain theoretically this behavior. claiming that the essence of the phenomenon lies in the geometry of the internet and its modeling assumptions, we introduce the model of self-similar trees with similarity factor 0 &le; &theta; < 1. under this assumption, we analyze r(n) and prove that it is &theta;(n1-&theta;). we also discuss some experimental results of real networks that confirm the power law and show that these networks have the self similar profile. in particular, we find experimentally that the power law holds with &theta;exp &asymp; 0.12. our theoretical findings are established by analytical techniques of the precise analysis of algorithms such as mellin transform and complex asymptotics.
smaller explicit superconcentrators. we present an explicit construction of an infinite family of n-superconcentrators of density 44. the most economical previously known explicit graphs of this type have density around 60.
collecting correlated information from a sensor network. a fundamental problem in the study of sensor networks is collecting data to a central server from a set of k distributed sensor nodes. a considerable amount of recent research in this area attempts to reduce the number of bits sent by the nodes by taking advantage of correlations between the data items collected from different nodes. in this paper, we study this problem in the following model: let d be a probability distribution over k binary strings of length n. a sample &xmacr; is drawn from d and the k strings of &xmacr; are revealed to the nodes, one string per node. the goal is to inform the server of all k strings of &xmacr;. our primary objective is to minimize the total number of bits sent by the nodes, but we also seek to minimize both the bits sent by the server and the number of rounds required. this problem is a natural parallelization of the model introduced in [2], and is also well motivated by recent work on distributed source coding for sensor networks. our main result is a protocol that allows the server to correctly determine &xmacr;. in this protocol, the nodes send o(h(d) + k) bits in expectation, where h(d) is the binary entropy of d; this is asymptotically optimal. the server sends o(kn + h(d) log n) bits in expectation, and the number of rounds is o(1 + log[h(d)]) in expectation. we also demonstrate that if the server is allowed to produce an incorrect result with probability up to &delta;, then the expected number of bits sent by the server can be reduced to o(k log(nk/&delta;) + h(d) log n), without increasing the other measures of performance.
guessing secrets efficiently via list decoding. we consider the guessing secrets problem defined by chung et al. [2001]. this is a variant of the standard 20 questions game where the player has a set of k > 1 secrets from a universe of n possible secrets. the player is asked boolean questions about the secret. for each question, the player picks one of the k secrets adversarially, and answers according to this secret. we present an explicit set of o(log n) questions together with an efficient (i.e., poly(log n) time) algorithm to solve the guessing secrets problem for the case of 2 secrets. this answers the main algorithmic question left unanswered by chung et al. [2001]. the main techniques we use are small &epsis;-biased spaces and the notion of list decoding. we also establish bounds on the number of questions needed to solve the k-secrets game for k > 2, and discuss how list decoding can be used to get partial information about the secrets, specifically to find a small core of secrets that must intersect the actual set of k secrets.
beating the logarithmic lower bound: randomized preemptive disjoint paths and call control algorithms. we consider the maximum disjoint paths problem and its generalization, the call control problem, in the on-line setting. in the maximum disjoint paths problem, we are given a sequence of connection requests for some communication network. each request consists of a pair of nodes, that wish to communicate over a path in the network. the request has to be immediately connected or rejected, and the goal is to maximize the number of connected pairs, such that no two paths share an edge. in the call control problem, each request has an additional bandwidth specification, and the goal is to maximize the total bandwidth of the connected pairs (throughput), while satisfying the bandwidth constraints (assuming each edge has unit capacity). these classical problems are central in routing and admission control in high speed networks and in optical networks.we present the first known constant-competitive algorithms for both problems on the line. this settles an open problem of garay et al. and of leonardi. moreover, to the best of our knowledge, all previous algorithms for any of these problems, are ω(log n)-competitive, where n is the number of vertices in the network (and obviously noncompetitive for the continuous line). our algorithms are randomized and preemptive. our results should be contrasted with the ω(log n) lower bounds for deterministic preemptive algorithms of garay et al. and the ω(log n) lower bounds for randomized non-preemptive algorithms of lipton and tomkins and awerbuch et al. interestingly, nonconstant lower bounds were proved by canetti and irani for randomized preemptive algorithms for related problems but not for these exact problems.
testing triangle-freeness in general graphs. in this paper we consider the problem of testing whether a graph is triangle-free, and more generally, whether it is h-free, for a fixed subgraph h. the algorithm should accept graphs that are triangle-free and reject graphs that are far from being triangle-free in the sense that a constant fraction of the edges should be removed in order to obtain a triangle-free graph. the algorithm is allowed a small probability of error.this problem has been studied quite extensively in the past, but the focus was on dense graphs, that is, when d = &theta;(n), where d is the average degree in the graph and n is the number of vertices. here we study the complexity of the problem in general graphs, that is, for varying d.our main finding is a lower bound of &omega;(n1/3) on the necessary number of queries that holds for every d < n1-&nu;(n), where &nu;(n) = o(1). since when d = &theta;(n) the number of queries sufficient for testing has been known to be independent of n, we observe an abrupt, threshold-like behavior of the complexity of testing around n. this lower bound holds for testing h-freeness of every non-bipartite subgraph h.additionally we provide sub-linear upper bounds for testing triangle-freeness that are at most quadratic in the stated lower bounds, and we describe a transformation from certain one-sided error lower bounds for testing subgraph-freeness to two-sided error lower bounds.finally, in the course of our analysis we show that dense random cayley graphs behave like quasi-random graphs in the sense that relatively large subsets of vertices have the "correct" edge density. the result for subsets of this size cannot be obtained from the known spectral techniques that only supply such estimates for much larger subsets.
lower bounds for asymmetric communication channels and distributed source coding. we prove nearly tight lower bounds on the number of rounds of communication required by efficient protocols over asymmetric channels between a server (with high sending capacity) and one or more clients (with low sending capacity). this scenario captures the common asymmetric communication bandwidth between broadband internet providers and home users, as well as sensor networks where sensors (clients) have limited capacity because of the high power requirements for long-range transmissions. an efficient protocol in this setting communicates n bits from each of the k clients to the server, where the clients' bits are sampled from a joint distribution d that is known to the server but not the clients, with the clients sending only o(h(d) + k) bits total, where h(d) is the entropy of distribution d. in the single-client case, there are efficient protocols using o(1) rounds in expectation and o(lg n) rounds in the worst case. we prove that this is essentially best possible: with probability 1/2o(t lg t), any efficient protocol can be forced to use t rounds. in the multi-client case, there are efficient protocols using o(lg k) rounds in expectation. we prove that this is essentially best possible: with probability &omega;(1), any efficient protocol can be forced to use &omega;(lg k/ lg lg k) rounds. along the way, we develop new techniques of independent interest for proving lower bounds in communication complexity.
testing satisfiability. let &phi; be a set of general boolean functions on n variables, such that each function depends on exactly k variables, and each variable can take a value from [1,d]. we say that &phi; is &epsilon;-far from satisfiable, if one must remove at least &epsilon;nk functions in order to make the set of remaining functions satisfiable. our main result is that if &phi; is &epsilon;-far from satisfiable, then most of the induced sets of functions, on sets of variables of size c(k,d)&epsilon;2, are not satisfiable, where c(k,d) depends only on k and d. using the above claim, we obtain similar results for k-sat and k-naeq-sat.assume we relax the decision problem of whether an instance of one of the above mentioned problems is satisfiable or not, to the problem of deciding whether an instance is satisfiable or &epsilon;-far from satisfiable. while the above decision problems are np-hard, our result implies that we can solve their relaxed versions, that is, distinguishing between satisfiable and &epsilon;-far from satisfiable instances, in randomized constant time.from the above result we obtain as a special case, previous results of alon and krivelevich [3] and of czumaj and sohler [8], concerning testing of graphs and hypergraphs colorability. we also discuss the problem of testing whether a graph g can be d-colored, such that it does not contain any copy of a colored graph from a fixed, given set of colored graphs.
on the capacity of information networks. we consider information networks in the absence of interference and noise, and present an upper bound on the rate at which information can be transmitted using network coding. our upper bound is based on combining properties of entropy with a strong information inequality derived from the structure of the network.the undirected k-pairs conjecture states that the information capacity of an undirected network supporting k point-to-point connections is achievable by multicommodity flows. our techniques prove the conjecture for a non-trivial class of graphs, and also yield the first known proof of a gap between the sparsity of an undirected graph and its capacity. we believe that these techniques may be instrumental in resolving the conjecture completely. we demonstrate the importance of the undirected k-pairs conjecture by connecting it with a long-standing open question in input/output (i/o) complexity. we also show that proving the conjecture would provide the strongest known lower bound for computation in the oblivious cell-probe model and give a non-trivial lower bound for two-tape oblivious turing machines.finally, we conclude by considering the capacity of directed information networks. we construct a family of directed graphs whose capacity is much larger than the rate achievable using only multicommodity flows. the gap that we exhibit is linear in the number of vertices, edges, and commodities of the graph, which is asymptotically optimal.
a characterization of easily testable induced subgraphs. let h be a fixed graph on h vertices. we say that a graph g is induced h-free if it does not contain any induced copy of h. let g be a graph on n vertices and suppose that at least εn2 edges have to be added to or removed from it in order to make it induced h-free. it was shown in [5] that in this case g contains at least f(ε, h)nh induced copies of h, where 1/f(ε, h) is an extremely fast growing function in 1/ε, that is independent of n. as a consequence, it follows that for every h, testing induced h-freeness with one-sided error has query complexity independent of n. a natural question, raised by the first author in [1], is to decide for which graphs h the function 1/f(ε, h) can be bounded from above by a polynomial in 1/ε. an equivalent question is for which graphs h, can one design a one-sided error property tester for testing induced h-freeness, whose query complexity is polynomial in 1/ε. we settle this question almost completely by showing that, quite surprisingly, for any graph other than the paths of lengths 1,2 and 3, the cycle of length 4, and their complements, no such property tester exists. we further show that a similar result also applies to the case of directed graphs, thus answering a question raised by the authors in [9]. we finally show that the same results hold even in the case of two-sided error property testers. the proofs combine combinatorial, graph theoretic and probabilistic arguments with results from additive number theory.
pricing multicasting in more practical network models. the problem of designing efficient algorithms for sharing the cost of multicasting has recently seen considerable attention. in this paper, we examine the effect on the complexity of pricing when two practical considerations are incorporated into the network model. in particular, we study a model where the session is offered at a number of different rates of transmission, and where there is a cost for enabling multicasting at each node of the network. we consider two techniques that have been used in practice to provide multiple rates: using a layered transmission scheme (called the layered paradigm) and using different multicast groups for each possible rate (called the split session paradigm). we demonstrate that the difference between these two paradigms has a significant impact on the complexity of pricing multicasting.for the layered paradigm, we provide a distributed algorithm for computing pricing efficiently in terms of local computation and message complexity. for the split session paradigm, on the other hand, we demonstrate that this problem can be solved in polynomial time if the number of possible rates is fixed, but if the number of rates is part of the input, then the problem becomes np-hard even to approximate. we also examine the effect of delivering the transmissions for the various rates from different locations within the network. we show that in this case, the pricing problem becomes np-hard for the split session paradigm even for a fixed constant number of possible rates, but if layering is used, then it can be solved in polynomial time by formulating the problem as a totally unimodular integer program.
linear equations, arithmetic progressions and hypergraph property testing. for a fixed k-uniform hypergraph d (k-graph for short, k &ge; 3), we say that a k-graph h satisfies property pd (resp. p*d) if it contains no copy (resp. induced copy) of d. our goal in this paper is to classify the k-graphs d for which there are property-testers for testing pd and p*d whose query complexity is polynomial in 1/&epsilon;. for such k-graphs, we say that pd (or p*d) is easily testable.for p*d, we prove that aside from a single 3-graph, p*d is easily testable if and only if d is a single k-edge. for large k, we obtain stronger lower bounds than those obtained for the general case on the query complexity of testing p*d for any d other than the single k-edge. these bounds are proved by applying a more sophisticated technique than the basic one that works for all k. these results extend and improve previous results about graphs [5] and k-graphs [18].for pd, we show that for any k-partite k-graph d, pd, is easily testable, by giving an efficient one-sided error-property tester, which improves the one obtained by [18]. we further prove a nearly matching lower bound on the query complexity of such a property-tester. finally, we give a sufficient condition for inferring that pd is not easily testable. though our results do not supply a complete characterization of the k-graphs for which pd is easily testable, they are a natural extension of the previous results about graphs [1].our proofs combine results and arguments from additive number theory, linear algebra and extremal hypergraph theory. we also develop new techniques, which are of independent interest. the first is a construction of a dense set of integers, which does not contain a subset that satisfies a certain set of linear equations. the second is an algebraic construction of certain extremal hypergraphs. we demonstrate the applicability of this last construction by resolving several cases of an open problem raised by brown, erd&ouml;s and s&oacute;s in 1973. these two techniques have already been applied in two recent subsequent papers [6], [27].
constructing worst case instances for semidefinite programming based approximation algorithms. semidefinite programming based approximation algorithms, such as the goemans and williamson approximation algorithm for the max cut problem, are usually shown to have certain performance guarantees using local ratio techniques. are the bounds obtained in this way tight? this problem was considered before by karloff and by alon and sudakov. here we further extend their results and show, for the first time, that the local analyses of the goemans and williamson max cut algorithm, as well as its extension by zwick, are tight for every possible relative size of the maximum cut. we also obtain similar results for several related problems. our approach is quite general and could possibly be applied to some additional problems and algorithms.
efficient algorithms for bichromatic separability. a closed solid body separates one point set from another if it contains the former and the closure of its complement contains the latter. we present a near-linear algorithm for deciding whether two sets of n points in 3-space can be separated by a prism, near-quadratic algorithms for separating by a slab or a wedge, and a near-cubic algorithm for separating by a double-wedge. the latter three algorithms improve the previous best known results by an order of magnitude, while the prism separability algorithm constitutes an improvement of two orders of magnitude.
labeling schemes for small distances in trees. we consider labeling schemes for trees, supporting various relationships between nodes at small distance. for instance, we show that given a tree t and an integer k we can assign labels to each node of t such that given the label of two nodes we can decide, from these two labels alone, if the distance between v and w is at most k and, if so, compute it. for trees with n nodes and $k\geq 2$, we give a lower bound on the maximum label length of $\log n + \omega(\log \log n)$ bits, and for constant k, we give an upper bound of log n + o(log log n). bounds for ancestor, sibling, connectivity, and bi- and triconnectivity labeling schemes are also presented.
an optimal dynamic interval stabbing-max data structure? in this paper we consider the dynamic stabbing-max problem, that is, the problem of dynamically maintaining a set s of n axis-parallel hyper-rectangles in rd, where each rectangle s &isin; s has a weight w(s) &isin; r, so that the rectangle with the maximum weight containing a query point can be determined efficiently. we develop a linear-size structure for the one-dimensional version of the problem, the interval stabbing-max problem, that answers queries in worst-case o(log n) time and supports updates in amortized o(log n) time. our structure works in the pointer-machine model of computation and utilizes many ingredients from recently developed external memory structures. using standard techniques, our one-dimensional structure can be extended to higher dimensions, while paying a logarithmic factor in space, update time, and query time per dimension. furthermore, our structure can easily be adapted to external memory, where we obtain a linear-size structure that answers queries and supports updates in o(logb n) i/os, where b is the disk block size.
improved labeling scheme for ancestor queries. we present a labeling scheme for rooted trees that supports ancestor queries. given a tree, the scheme assigns to each node a label which is a binary string. given the labels of any two nodes u and v, it can in constant time be determined whether u is ancestor to v alone from these labels. for trees of size n our scheme assigns labels of size bounded by log n + o(&radic;log n) bits to each node. this improves a recent result of abiteboul, kaplan and milo at soda'01, where a labeling scheme with labels of size 3/2log n + o(log log n) was presented. the problem is among other things motivated in connection with efficient representation of information for xml-based search engines for the internet.
matching planar maps. the subject of this paper are algorithms for measuring the similarity of patterns of line segments in the plane, a standard problem in, e.g., computer vision, geographic information systems, etc. more precisely, we define feasible distance measures that reflect how close a given pattern h is to some part of a larger pattern g. these distance measures are generalizations of the well-known fréchet distance for curves. we first give an efficient algorithm for the case that h is a polygonal curve and g is a geometric graph. then, slightly relaxing the definition of distance measure, we give an algorithm for the general case where both, h and g, are geometric graphs.
an efficient algorithm for the configuration problem of dominance graphs. dominance constraints are logical tree descriptions originating from automata theory that have multiple applications in computational linguistics. the satisfiability problem of dominance constraints is np-complete. in most applications, however, only normal dominance constraints are used. the satisfiability problem of normal dominance constraints can be reduced in linear time to the configuration problem of dominance graphs, as shown recently. in this paper, we give a polynomial time algorithm testing configurability of dominance graphs (and thus satisfiability of normal dominance constraints). previous to our work no polynomial time algorithms were known.
point containment in the integer hull of a polyhedron. we show that the point containment problem in the integer hull of a polyhedron, which is defined by m inequalities, with coefficients of at most &phis; bits can be solved in time o(m + &phis;) in the two-dimensional case and in expected time o(m + &phis;2 log m) in any fixed dimension. this improves on the algorithm which is based on the equivalence of separation and optimization in the general case and on a direct algorithm (soda 97) for the two-dimensional case.
computing the writhing number of a polygonal knot. the writhing number measures the global geometry of a closed space curve or knot. we show that this measure is related to the average winding number of its gauss map. using this relationship, we give an algorithm for computing the writhing number for a polygonal knot with n edges in time roughly proportional to n1.6. we also implement a different, simple algorithm and provide experimental evidence for its practical efficiency.