waashk/dblp huggingface dataset:
maximum scan statistics and channel assignment problems in homogeneous wireless networks. in wireless networks, to avoid collisions of simultaneous transmissions over the same channel, adjacent nodes are assigned distinct channels, and the least number of channels used in an assignment is called the chromatic number. the determination of the chromatic number is np-hard. in this paper, we introduce an analytic tool called maximum scan statistics. for a finite point set v and a convex compact set c, the maximum scan statistic of v with respect to the scanning set c is the largest number of points in v covered by a copy c. based on the study of asymptotic maximum scan statistics, we obtain the asymptotics of the maximum degree and the clique number of homogeneous wireless networks. the results imply that the chromatic number is almost surely at most four times the clique number. we further prove that the approximation ratios of some vertex-ordering-based first-fit channel assignment algorithms are almost surely bounded by 2. in the analysis, we also learn that the chromatic number is almost surely at most twice the clique number.
an infinite hierarchy of language families generated by scattered context grammars with n-limited derivations. this paper introduces scattered context grammars without erasing productions, in which an application of a production always occurs within the first n nonterminals of the current sentential form. it demonstrates that this restriction gives rise to an infinite hierarchy of language families each of which is properly included in the family of context-sensitive languages. in addition, it proves analogous results for unordered scattered context grammars. some consequences of these results are derived and open problems formulated.
asymptotic subword complexity of fixed points of group substitutions. the subword complexity of fixed points of some types of substitutions was studied by various authors. here we introduce a family of substitutions, arising from multiplication tables of finite groups and other similar structures, and analyze their subword complexity.
sampling methods for shortest vectors, closest vectors and successive minima. we study four problems from the geometry of numbers, the shortest vector problem(svp), the closest vector problem(cvp), the successive minima problem(smp), and the shortest independent vectors problem (sivp). extending and generalizing results of ajtai, kumar, and sivakumar we present probabilistic single exponential time algorithms for all four problems for all @?"p norms. the results on smp and sivp are new for all norms. the results on svp and cvp generalize previous results of ajtai et al. for the euclidean @?"2 norm to arbitrary @?"p norms. we achieve our results by introducing a new lattice problem, the generalized shortest vector problem (gsvp). we describe a single exponential time algorithm for gsvp. we also describe polynomial time reductions from svp,cvp,smp, and sivp to gsvp, establishing single exponential time algorithms for the four classical lattice problems. this approach leads to a unified algorithmic treatment of the lattice problems svp,cvp,smp, and sivp.
multiple pass streaming algorithms for learning mixtures of distributions in r. we present a multiple pass streaming algorithm for learning the density function of a mixture of k uniform distributions over rectangles in r^d, for any d>0. our learning model is: samples drawn according to the mixture are placed in arbitrary order in a data stream that may only be accessed sequentially by an algorithm with a very limited random access memory space. our algorithm makes 2@?+2 passes, for any @?>0, and requires memory at most o@?(@e^-^2^/^@?k^2d^4+(4k)^d), where @e is the tolerable error of the algorithm. this exhibits a strong memory-pass tradeoff in terms of @e: a few more passes significantly lower its memory requirements, thus trading one of the two most important resources in streaming computation for the other. chang and kannan first considered this problem for d=1,2. our learning algorithm is especially appropriate for situations where massive data sets of samples are available, but computation with such large inputs requires very restricted models of computation.
on outer bounds to the capacity region of wireless networks. in this correspondence, we study the capacity region of a general wireless network by deriving fundamental upper bounds on a class of linear functionals of the rate tuples at which joint reliable communication can take place. the widely studied transport capacity is a specific linear functional: the coefficient of the rate between a pair of nodes is equal to the euclidean distance between them. the upper bound on the linear functionals of the capacity region is used to derive upper bounds to scaling laws for generalized transport capacity: the coefficient of the rate between a pair of nodes is equal to some arbitrary function of the euclidean distance between them, for a class of minimum distance networks. this upper bound to the scaling law meets that achievable by multihop communication over these networks for a wide class of channel conditions; this shows the optimality, in the scaling-law sense, of multihop communication when studying generalized transport capacity of wireless networks.
new upper bounds on generalized weights. we derive new asymptotic upper bounds on the generalized weights of a binary linear code of a given size. we also prove some asymptotic results on the distance distribution of binary codes.
coding on demand by an informed source (iscod) for efficient broadcast of different supplemental data to caching clients. the informed-source coding on demand (iscod)approach for efficiently supplying nonidentical data from a central server to multiple caching clients over a broadcast channel is presented. the key idea underlying iscod is the joint exploitation of the data blocks already cached by each client, the server's full knowledge of client-cache contents and client requests, and the fact that each client only needs to be able to derive the blocks requested by it rather than all the blocks ever transmitted or even the union of the blocks requested by the different clients. we present two-phase iscod algorithms: the server first creates ad-hoc error-correction sets based on its knowledge of client states; next, it uses erasure-correction codes to construct the data for transmission. each client uses its cached data and the received supplemental data to derive its requested blocks. the result is up to a several-fold reduction in the amount of transmitted supplemental data. also, we define k-partial cliques in a directed graph and cast iscod in terms of partial-clique covers.
the feasibility of matchings in a wireless network. the problem of determining what links can be simultaneously activated in a wireless network such that a signal-to-interference-and-noise (sinr) constraint is satisfied at all receivers is considered. the term "feasible matching" is introduced to describe a set of (transmitter, receiver) pairs for which there exists some set of transmit powers which can simultaneously meet the sinr equirements at the receivers. given disjoint equally sized sets of transmitters and receivers, it is shown that when the sinr requirement at the receivers is greater than 1, no more than one feasible matching between the transmitters and the receivers exists. sufficient conditions are provided under which certain broad classes of matchings in a network are guaranteed to be feasible; for example all matchings involving k or fewer links. the application of these results to ad hoc wireless networks and to scheduling is discussed.
randomized gossip algorithms. motivated by applications to sensor, peer-to-peer, and ad hoc networks, we study distributed algorithms, also known as gossip algorithms, for exchanging information and for computing in an arbitrarily connected network of nodes. the topology of such networks changes continuously as new nodes join and old nodes leave the network. algorithms for such networks need to be robust against changes in topology. additionally, nodes in sensor networks operate under limited computational, communication, and energy resources. these constraints have motivated the design of "gossip" algorithms: schemes which distribute the computational burden and in which a node communicates with a randomly chosen neighbor.we analyze the averaging problem under the gossip constraint for an arbitrary network graph, and find that the averaging time of a gossip algorithm depends on the second largest eigenvalue of a doubly stochastic matrix characterizing the algorithm. designing the fastest gossip algorithm corresponds to minimizing this eigenvalue, which is a semidefinite program (sdp). in general, sdps cannot be solved in a distributed fashion; however, exploiting problem structure, we propose a distributed subgradient method that solves the optimization problem over the network.the relation of averaging time to the second largest eigenvalue naturally relates it to the mixing time of a random walk with transition probabilities derived from the gossip algorithm. we use this connection to study the performance and scaling of gossip algorithms on two popular networks: wireless sensor networks, which are modeled as geometric random graphs, and the internet graph under the so-called preferential connectivity (pc) model.
bounds on approximate steepest descent for likelihood maximization in exponential families. an approximate steepest descent strategy converging, in families of regular exponential densities, to maximum likelihood estimates of density functions is described. these density estimates are also obtained by an application of the principle of minimum relative entropy subject to empirical constraints. we prove tight bounds on the increase of the log-likelihood at each iteration of our strategy for families of exponential densities whose log-densities are spanned by a set of bounded basis functions.
constructions of optical fifo queues. discrete-time queues are infinite dimensional switches in time. ever since shannon published his paper ("memory requirements in telephone exchange," bell syst. tech. j., pp. 343-349, vol. 29, 1950) on the memory requirements in a telephone exchange, there have been tremendous efforts in the search for switches with minimum complexity. constructing queues with minimum complexity has not received the same amount of attention as queues are relatively cheap to build via electronic memory. recent advances in optical technologies, however, have spurred interest in building optical queues with minimum complexity. in this correspondnece, we develop mathematical theory of constructing discrete-time optical first-in-first-out (fifo) queues. to our surprise, we find that many classical constructions for switches have their counterparts for constructing queues. analogous to the three-stage construction of clos networks, we develop three-stage construction of optical fifo queues via switched delay lines (sdls). via recursively expanding the three-stage construction, we show that an optical fifo queue with buffer 2n -- 1 can be constructed by using 2n 2 × 2 switches with the total fiber length 3, 2n-1 -- 2.
on average throughput and alphabet size in network coding. we examine the throughput benefits that network coding offers with respect to the average throughput achievable by routing, where the average throughput refers to the average of the rates that the individual receivers experience. we relate these benefits to the integrality gap of a standard linear programming formulation for the directed steiner tree problem. we describe families of configurations over which network coding at most doubles the average throughput, and analyze a class of directed graph configurations with n receivers where network coding offers benefits proportional to √n. we also discuss other throughput measures in networks, and show how in certain classes of networks, average throughput bounds can be translated into minimum throughput bounds, by employing vector routing and channel coding. finally, we show configurations where use of randomized coding may require an alphabet size exponentially larger than the minimum alphabet size required.
scaling properties of statistical end-to-end bounds in the network calculus. the stochastic network calculus is an evolving new methodology for backlog and delay analysis of networks that can account for statistical multiplexing gain. this paper advances the stochastic network calculus by deriving a network service curve, which expresses the service given to a flow by the network as a whole in terms of a probabilistic bound. the presented network service curve permits the calculation of statistical end-to-end delay and backlog bounds for broad classes of arrival and service distributions. the benefits of the derived service curve are illustrated for the exponentially bounded burstiness (ebb) traffic model. it is shown that end-to-end performance measures computed with a network service curve are bounded by o (h log h), where h is the number of nodes traversed by a flow. using currently available techniques, which compute end-to-end bounds by adding single node results, the corresponding performance measures are bounded by o (h3).
algebraic gossip: a network coding approach to optimal multiple rumor mongering. the problem of simultaneously disseminating k messages in a large network of n nodes, in a decentralized and distributed manner, where nodes only have knowledge about their own contents, is studied. in every discrete time-step, each node selects a communication partner randomly, uniformly among all nodes and only one message can be transmitted. the goal is to disseminate rapidly, with high probability, all messages to all nodes. it is shown that a random linear coding (rlc) based protocol disseminates all messages to all nodes in time ck + o (√k ln(k) ln(n)), where c < 3.46 using pull-based dissemination and c < 5.96 using push-based dissemination. simulations suggest that c < 2 might be a tighter bound. thus, if k ≫ (ln(n))3, the time for simultaneous dissemination rlc is asymptotically at most ck, versus the ω(k log2(n))3 time of sequential dissemination. furthermore, when k ≫ (ln(n))3, the dissemination time is order optimal. when k ≪ (ln(n))2, rlc reduces dissemination time by a factor of ω(√k/ln k) over sequential dissemination. the overhead of the rlc protocol is negligible for messages of reasonable size. a store-and-forward mechanism without coding is also considered. it is shown that this approach performs no better than a sequential approach when k=∞ n. owing to the distributed nature of the system, the proof requires analysis of an appropriate time-varying bernoulli process.
on the security of public key protocols. recently, the use of public key encryption to provide secure network communication has received considerable attention. such public key systems are usually effective against passive eavesdroppers, who merely tap the lines and try to decipher the message. it has been pointed out, however, that an improperly designed protocol could be vulnerable to an active saboteur, one who may impersonate another user or alter the message being transmitted. in this paper we formulate several models in which the security of protocols can be discussed precisely. algorithms and characterizations that can be used to determine protocol security in these models will be given.
unachievability of network coding capacity. the coding capacity of a network is the supremum of ratios k/n for which there exists a fractional (k, n) coding solution, where k is the source message dimension and n is the maximum edge dimension. the coding capacity is referred to as routing capacity in the case when only routing is allowed. a network is said to achieve its capacity if there is some fractional (k, n) solution for which k/n equals the capacity. the routing capacity is known to be achievable for arbitrary networks.we give an example of a network whose coding capacity (which is 1) cannot be achieved by a network code. we do this by constructing two networks, one of which is solvable if and only if the alphabet size is odd, and the other of which is solvable if and only if the alphabet size is a power of 2. no linearity assumptions are made.
on the throughput scaling of wireless relay networks. the throughput of wireless networks is known to scale poorly when the number of users grows. the rate at which an arbitrary pair of nodes can communicate must decrease to zero as the number of users tends to infinity, under various assumptions. one of them is the requirement that the network is fully connected: the computed rate must hold for any pair of nodes of the network. we show that this requirement can be responsible for the lack of throughput scalability. we consider a two-dimensional (2-d) network of extending area with only one active source-destination pair at any given time, and all remaining nodes acting only as possible relays. allowing an arbitrary small fraction of the nodes to be disconnected, we show that the per-node throughput remains constant as the network size increases. as a converse bound, we show that communications occurring at fixed nonzero rate imply a fraction of the nodes to be disconnected. our results are of information theoretic flavor, as they hold without assumptions on the communication strategies employed by the network nodes.
on the shape of a set of points in the plane. a generalization of the convex hull of a finite set of points in the plane is introduced and analyzed. this generalization leads to a family of straight-line graphs, called ``shapes'''', which seem to capture the intuitive notion of ``fine shape'''' and ``crude shape'''' of point sets. .br additionally, close relationships with delaunay triangulations are revealed and, relying on these results, an optimal algorithm that constructs ``shapes'''' is developed.
suboptimality of the karhunen-loe`ve transform for transform coding. we examine the performance of the klt for transform coding applications.theklt has long been viewed as the best available block transform for transform coding.this paper treats fixed-rate and variable-rate transform codes.the fixed-rate approachuses an optimal fixed-rate scalar quantizer to describe the transform coefficients; thevariable-rate approach uses a uniform scalar quantizer followed by an optimal entropycode.earlier work shows that for the variable-rate case there exist sources on whichthe klt is not unique and the optimal transform code matched to a "worst" klt yieldsperformance as much as 1.5 db worse than the optimal transform code matched to a"best" klt. in this paper, we strengthen that result to show that in both the fixed-rateand the variable-rate coding frameworks there exist sources for which the performancepenalty for using a "worst" klt can be made arbitrarily large.further, we demonstratein both frameworks that there exist sources for which even a best klt gives suboptimalperformance.finally, we show that even for vector sources where the klt yieldsindependent coefficients, the klt can be suboptimal for fixed-rate coding.
on the maximum tolerable noise for reliable computation by formulas. it is shown that if a formula is constructed from noisy 2-input nand gates, with each gate failing independently with probability e, then reliable computation can or cannot take place according as e is less than or greater than e_0 = (3-sqrt(7))/4 = 0.08856....
critical node lifetimes in random networks via the chen-stein method. this correspondence considers networks where nodes are connected randomly and can fail at random times. it provides scaling laws that allow to find the critical time at which isolated nodes begin to appear in the system as its size tends to infinity. applications are in the areas of sensor and ad-hoc networks where nodes are subject to battery drainage and 'blind spots' formation becomes a primary concern. the techniques adopted are based on the chen-stein method of poisson approximation, which allows to obtain elegant derivations that are shown to improve upon and simplify previous related results that appeared in the literature. since blind spots are strongly related to full connectivity, we also obtain some scaling results about the latter.
optimal overload response in sensor networks. a single commodity network that models the information flow in an arbitrary topology sensor field that collects and forwards information to a backbone through certain designated gateway nodes is considered. resilient operation in overload stress situations caused by unpredictable traffic or topology variations is investigated. that amounts to studying the network in instability mode, where the traffic load distribution is outside the throughput region. a fluid model is adopted where superflows model traffic forwarding and backlog formations at the network level. quantitative performance metrics of the overload including throughput, lexicographic minimization, most balanced allocation, and amount of lost traffic due to buffer overflow are considered to capture the information loss process due to overflow in the network. optimal superflows with respect to these metrics are characterized and a distributed asynchronous algorithm that computes such superflows is given. the characterization of the optimal superflow amounts to obtaining a structural decomposition of the network in a sequence of disjoint subregions with decreasing overload such that traffic flows only from regions of higher overload to regions of lower overload. the optimal superflow represents the smoothest trajectory to overflow, followed by the network in case of instability.
optimal throughput-delay scaling in wireless networks: part i: the fluid model. gupta and kumar (2000) introduced a random model to study throughput scaling in a wireless network with static nodes, and showed that the throughput per source-destination pair is θ (1/√n log n). grossglauser and tse (2001) showed that when nodes are mobile it is possible to have a constant throughput scaling per source-destination pair. in most applications, delay is also a key metric of network performance. it is expected that high throughput is achieved at the cost of high delay and that one can be improved at the cost of the other. the focus of this paper is on studying this tradeoff for wireless networks in a general framework. optimal throughput-delay scaling laws for static and mobile wireless networks are established. for static networks, it is shown that the optimal throughput-delay tradeoff is given by d(n) = θ (nt(n)), where t(n) and d(n) are the throughput and delay scaling, respectively. for mobile networks, a simple proof of the throughput scaling of θ(1) for the grossglauser-tse scheme is given and the associated delay scaling is shown to be θ(n log n). the optimal throughput-delay tradeoff for mobile networks is also established. to capture physical movement in the real world, a random-walk (rw) model for node mobility is assumed. it is shown that for throughput of o (1/√n log n), which can also be achieved in static networks, the throughput-delay tradeoff is the same as in static networks, i.e., d(n) = θ (nt(n)). surprisingly, for almost any throughput of a higher order, the delay is shown to be θ (n log n), which is the delay for throughput of θ(1). our result, thus, suggests that the use of mobility to increase throughput, even slightly, in real-world networks would necessitate an abrupt and very large increase in delay.