Search

Chen and Wee [CRYPTO, 2013] proposed the first almost tightly and adaptively secure IBE in the standard model and left two open problems which called for a tightly secure IBE with (1) constant-size master public key and/or (2) constant security loss. In this paper, we propose an IBE scheme with constant-size master public key and tighter security reduction. This (partially) solves Chen and Wee’s first open problem and makes progress on the second one. Technically, our IBE scheme is built based on Wee’s petit IBE scheme [TCC, 2016] in the composite-order bilinear group whose order is product of four primes. The sizes of master public key, ciphertexts, and secret keys are not only constant but also nearly optimal as Wee’s petit IBE. We can prove its adaptive security in the multi-instance, multi-ciphertext setting [PKC, 2015] based on the decisional subgroup assumption and a subgroup variant of DBDH assumption. The security loss is \({\mathcal {O}}(\log q)\) where q is the upper bound of the total number of secret keys and challenge ciphertexts per instance. It’s much smaller than those for all known adaptively secure IBE schemes in a concrete sense.

Obfuscation is challenging; we currently have practical candidates with rather vague security guarantees on the one side, and theoretical constructions which have recently experienced jeopardizing attacks against the underlying cryptographic assumptions on the other side. This motivates us to study and present robust combiners for obfuscators, which integrate several candidate obfuscators into a single obfuscator which is secure as long as a quorum of the candidates is indeed secure. We give several results about building obfuscation combiners, with matching upper and lower bounds for the precise quorum of secure candidates. Namely, we show that one can build 3-out-of-4 obfuscation combiners where at least three of the four combiners are secure, whereas 2-out-of-3 structural combiners which combine the obfuscator candidates in a black-box sense with only two secure candidates, are impossible. Our results generalize to $$2\gamma +1$$-out-of-$$3\gamma +1$$ combiners for the positive result, and to $$2\gamma $$-out-of-$$3\gamma $$ results for the negative result, for any integer $$\gamma $$. To reduce overhead, we define detecting combiners, where the combined obfuscator may sometimes produce an error-indication instead of the desired output, indicating that some of the component obfuscators is faulty. We present a $$\gamma +1$$-out-of-$$2\gamma +1$$ detecting combiner for any integer $$\gamma $$, bypassing the previous lower bound. We further show that $$\gamma $$-out-of-$$2\gamma $$ structural detecting combiners are again impossible. Since our approach can be used for practical obfuscators, as well as for obfuscators proven secure based on assumptions, we also briefly report on implementation results for some applied obfuscator programs.

Algebraic immunity is a cryptographic measure about the resistance against algebraic attack which was first proposed by Courtois in 2003 for stream ciphers. This chapter studies some basic properties of algebraic immunity of Boolean functions, including the construction of annihilators of Boolean functions, upper and lower bounds of algebraic immunity, and an approach toward computing the annihilators of Boolean functions.

The literature on leakage-resilient cryptography contains various leakage models that provide different levels of security. In this work, we consider the bounded leakage and the continual leakage models. In the bounded leakage model Akavia et al. --- TCC 2009, it is assumed that there is a fixed upper bound L on the number of bits the attacker may leak on the secret key in the entire lifetime of the scheme. Alternatively, in the continual leakage model Brakerski et al. --- FOCS 2010, Dodis et al. --- FOCS 2010, the lifetime of a cryptographic scheme is divided into "time periods" between which the scheme's secret key is updated. Furthermore, in its attack the adversary is allowed to obtain some bounded amount of leakage on the current secret key during each time period. In the continual leakage model, a challenging problem has been to provide security against leakage on key updates, that is, leakage that is a function not only of the current secret key but also the randomness used to update it. We propose a new, modular approach to overcome this problem. Namely, we present a compiler that transforms any public-key encryption or signature scheme that achieves a slight strengthening of continual leakage resilience, which we call consecutive continual leakage resilience, to one that is continual leakage resilient with leakage on key updates, assuming indistinguishability obfuscation Barak et al. --- CRYPTO 2001, Garg et al. --- FOCS 2013. Under the stronger assumption of public-coin differing-inputs obfuscation Ishai eti¾?al. --- TCC 2015 the leakage rate tolerated by our compiled scheme is essentially as good as that of the starting scheme. Our compiler is obtained by making a new connection between the problems of leakage on key updates and so-called "sender-deniable" encryption Canetti et al. --- CRYPTO 1997. In particular, our compiler adapts and optimizes recent techniques of Sahai and Waters STOC 2014 that make any encryption scheme sender-deniable. We then show that prior continual leakage resilient schemes can be upgraded to security against consecutive continual leakage without introducing new assumptions. In the bounded leakage model, we develop an entirely new approach to constructing leakage-resilient encryption from obfuscation directly, based upon the public-key encryption scheme from $${\mathsf {iO}} $$ and punctured pseudorandom functions due to Sahai and Waters STOC 2014. In particular, we achieve 1 leakage-resilient public key encryption tolerating L bits of leakage for any L from $${\mathsf {iO}} $$ and one-way functions, 2 leakage-resilient public key encryption with optimal leakage rate of $$1-o1$$ based on public-coin differing-inputs obfuscation and collision-resistant hash functions.

When scheduling jobs for systems in the cloud, we often deal with jobs that arrive and depart in an online manner. Each job should be assigned to a server upon arrival. Jobs are annotated with sizes which define the amount of resources that they need. Servers have uniform capacity and, at all times, the total size of jobs assigned to a server should not exceed this capacity. This setting is closely related to the classic bin packing problem. The difference is that, in bin packing, the objective is to minimize the total number of used servers. In the cloud systems, however, the cost for each server is proportional to the length of the time interval it is rented for, and the goal is to minimize the cost involved in renting all used servers. Recently, certain bin packing strategies were considered for renting servers in the cloud [Li et al. SPAA’14]. There, it is proved that all Any-Fit strategies have a competitive ratio of at least μ, where μ is the max/min interval length ratio of jobs. It is also proved that First Fit has a competitive ratio of 2μ + 13, while Best Fit is not competitive at all. We observe that the lower bound of μ extends to all online algorithms. We also prove that, surprisingly, Next Fit algorithm has a competitive ratio of at most 2 μ + 1. We also show that a variant of Next Fit achieves a competitive ratio of K × max {1,μ/(K − 1)} + 1, where K is a parameter of the algorithm. In particular, if the value of μ is known, the algorithm has a competitive ratio of μ + 2; this improves upon the existing upper bound of μ + 8. Finally, we introduce a simple algorithm called Move To Front (Mtf) which has a competitive ratio of at most 6μ + 8. We experimentally study the average-case performance of different algorithms and observe that the typical behaviour of Mtf is better than other algorithms.

International audience; We initiate a systematic treatment of the communication complexity of conditional disclosure of secrets (CDS), where two parties want to disclose a secret to a third party if and only if their respective inputs satisfy some predicate. We present a general upper bound and the first non-trivial lower bounds for conditional disclosure of secrets. Moreover, we achieve tight lower bounds for many interesting setting of parameters for CDS with linear reconstruction, the latter being a requirement in the application to attribute-based encryption. In particular, our lower bounds explain the trade-off between ciphertext and secret key sizes of several existing attribute-based encryption schemes based on the dual system methodology.

At CRYPTO 2014, Abe et al. presented generic-signer structure-preserving signature schemes using Typei¾?2 pairings. According to the authors, the proposed constructions are optimal with only two group elements in each signature and just one verification equation. The schemes beat the known lower bounds in the Typei¾?3 setting and thereby establish that the Typei¾?2 setting permits construction of cryptographic schemes with unique properties not achievable in Typei¾?3. In this paper we undertake a concrete analysis of the Abe et al. claims. By properly accounting for the actual structure of the underlying groups and subgroup membership testing of group elements in signatures, we show that the schemes are not as efficient as claimed. We present natural Typei¾?3 analogues of the Typei¾?2 schemes, and show that the Typei¾?3 schemes are superior to their Typei¾?2 counterparts in every aspect. We also formally establish that in the concrete mathematical structure of asymmetric pairing, all Typei¾?2 structure-preserving signature schemes can be converted to the Typei¾?3 setting without any penalty in security or efficiency, and show that the converse is false. Furthermore, we prove that the Typei¾?2 setting does not allow one to circumvent the known lower bound result for the Typei¾?3 setting. Our analysis puts the optimality claims for Typei¾?2 structure-preserving signature in a concrete perspective and indicates an incompleteness in the definition of a generic bilinear group in the Typei¾?2 setting.

In this chapter, we present a dynamic version of fireworks algorithm, which is an improved version of the recently developed enhanced fireworks algorithm (EFWA) based on an adaptive dynamic local search mechanism. In EFWA, the explosion amplitude of each firework is computed based on the quality of the firework’s current location. This explosion amplitude is limited by a lower bound which decreases with the number of iterations in order to avoid the explosion amplitude to be [close to] zero, and in order to enhance global search abilities at the beginning and local search abilities toward the later phase of the algorithm. As the explosion amplitude in EFWA depends solely on the fireworks’ fitness and the current number of iterations, this procedure does not allow for an adaptive optimization process. To deal with these limitations, a dynamic search fireworks algorithm (dynFWA) is proposed, which uses a dynamic explosion amplitude for the firework at the current best position. If the fitness of the best firework could be improved, the explosion amplitude will increase to speed up convergence. On the contrary, if the current position of the best firework could not be improved, the explosion amplitude will decrease in order to narrow the search area. In addition, we show that one of the EFWA operators, i.e., Gaussian mutation operator, can be removed in dynFWA without a loss in accuracy—this makes dynFWA computationally more efficient than EFWA.

Margin-based strategies and model change based strategies represent two important types of strategies for active learning. While margin-based strategies have been dominant for Support Vector Machines (SVMs), most methods are based on heuristics and lack a solid theoretical support. In this paper, we propose an active learning strategy for SVMs based on Maximum Model Change (MMC). The model change is defined as the difference between the current model parameters and the updated parameters obtained with the enlarged training set. Inspired by Stochastic Gradient Descent (SGD) update rule, we measure the change as the gradient of the loss at a candidate point. We analyze the convergence property of the proposed method, and show that the upper bound of label requests made by MMC is smaller than passive learning. Moreover, we connect the proposed MMC algorithm with the widely used simple margin method in order to provide a theoretical justification for margin-based strategies. Extensive experimental results on various benchmark data sets from UCI machine learning repository have demonstrated the effectiveness and efficiency of the proposed method.

The Minimax Probability Machine (MPM) is an elegant machine learning algorithm for inductive learning. It learns a classifier that minimizes an upper bound on its own generalization error. In this paper, we extend its celebrated inductive formulation to an equally elegant transductive learning algorithm. In the transductive setting, the label assignment of a test set is already optimized during training. This optimization problem is an intractable mixed-integer programming. Thus, we provide an efficient label-switching approach to solve it approximately. The resulting method scales naturally to large data sets and is very efficient to run. In comparison with nine competitive algorithms on eleven data sets, we show that the proposed Transductive MPM (TMPM) almost outperforms all the other algorithms in both accuracy and speed.

We put forth the question of whether cryptography is feasible using streaming devices. We give constructions and prove lower bounds. In streaming cryptography (not to be confused with stream-ciphers) everything—the keys, the messages, and the seeds—are huge compared to the internal memory of the device. These streaming algorithms have small internal memory size and make a constant number of passes over big data maintained in a constant number of read/write external tapes. Typically, the internal memory size is O(logn) and we use 2 external tapes; whereas 1 tape is provably insufficient. In this setting we cannot compute instances of popular intractability assumptions. Nevertheless, we base cryptography on these assumptions by employing non-black-box techniques, and study its limitations.

We consider the problem of consensus in the challenging classic model. In this model, the adversary is adaptive; it can choose which processors crash at any point during the course of the algorithm. Further, communication is via asynchronous message passing: there is no known upper bound on the time to send a message from one processor to another, and all messages and coin flips are seen by the adversary.

The Bitcoin virtual currency is built on the top of a decentralized peer-to-peer (P2P) network used to propagate system information such as transactions or blockchain updates. In this paper, we have performed a data collection process identifying more than 872000 different Bitcoin nodes. This data allows us to present information on the size of the Bitcoin P2P network, the node geographic distribution, the network stability in terms of interrupted availability of nodes, as well as some data regarding the propagation time of the transmitted information. Furthermore, although not every Bitcoin user can be identified as a P2P network node, measurements of the P2P network can be considered as a lower bound for Bitcoin usage, and they provide interesting results on the adoption of such virtual currency.

This paper proves a lower bound on the trade-off between server storage size and the locality of memory accesses in searchable symmetric encryption (SSE). Namely, when encrypting an index of N identifier/keyword pairs, the encrypted index must have size ω(N) or the scheme must perform searching with ω(1) non-contiguous reads to memory or the scheme must read many more bits than is necessary to compute the results. Recent implementations have shown that nonlocality of server memory accesses create a throughput-bottleneck on very large databases. Our lower bound shows that this is due to the security notion and not a defect of the constructions. An upper bound is also given in the form of a new SSE construction with an O(N logN) size encrypted index that performs O(log N) reads during a search.

Consider the Ants Nearby Treasure Search (ANTS) problem introduced by Feinerman, Korman, Lotker, and Sereni (PODC 2012), where n mobile agents, initially placed in a single cell of an infinite grid, collaboratively search for an adversarially hidden treasure. In this paper, the model of Feinerman et al. is adapted such that each agent is controlled by an asynchronous (randomized) finite state machine: they possess a constant-size memory and can locally communicate with each other through constant-size messages. Despite the restriction to constant-size memory, we show that their collaborative performance remains the same by presenting a distributed algorithm that matches a lower bound established by Feinerman et al. on the run-time of any ANTS algorithm.

The software system under test can be modeled as a graph comprising of a set of vertices, V and a set of edges, E. Test Cases are Test Paths over the graph meeting a particular test criterion. In this paper, we present a method to achieve the minimum number of Test Paths needed to cover different structural coverage criteria. Our method can accommodate Prime Path, Edge-Pair, Simple & Complete Round Trip, Edge and Node coverage criteria. Our method obtains the optimal solution by transforming the graph into a flow graph and solving the minimum flow problem. We present an algorithm for the minimum flow problem that matches the best known solution complexity of $ O\left(\left\vert{V}\right\vert\left\vert{E}\right\vert\right)$ . Our method is evaluated through two sets of tests. In the first, we test against graphs representing actual software. In the second test, we create random graphs of varying complexity. In each test we measure the number of Test Paths, the length of Test Paths, the lower bound on minimum number of Test Paths and the execution time.

We are developing an opportunistic communication based wireless sensor network system to gather and analyze the data of sediment transport in the desert for desertification research. There are two kinds of nodes in our system, one is base station and the other is sensor node, which can move randomly driven by wind and forward the data to the base station while they are encountering. Science the number of nodes has large impact on performance like success rate of data forward, lifetime and cost of the system, it is significant to estimate the lower bound for the required number of sensor nodes. In this paper, through some assumption and simplification, we give a simple formula to estimate the minimum number of sensor nodes that the system need to ensure opportunistic encounter between nodes will occur to make the data can be forwarded.

Consider a synchronous static radio network of \(n\) nodes represented by an undirected graph with maximum degree \(\varDelta \). Suppose that each node has a unique ID from \(\{1,\ldots ,N\}\), where \(N \gg n\). In the complete neighbourhood learning task, each node \(p\) must produce a set \(L_p\) of IDs such that ID \(i \in L_p\) if and only if \(p\) has a neighbour with ID \(i\). We study the complexity of this task when it is assumed that each node fixes its entire transmission schedule at the start of the algorithm. We prove a \(\varOmega (\frac{\varDelta ^2}{\log \varDelta }\log {N})\)-slot lower bound on schedule length that holds in very general models, e.g., when nodes possess collision detectors, messages can be of arbitrary size, and nodes know the schedules being followed by all other nodes. We also prove a similar result for the SINR model of radio networks. To prove these results, we introduce a new generalization of cover-free families of sets, which may be of independent interest. We also show a separation between the class of fixed-schedule algorithms and the class of algorithms where nodes can choose to leave out some transmissions from their schedule.

Many futuristic technologies, such as Internet of Things or nano-communication, assume that a large number of simple devices of very limited energy and computational power will be able to communicate efficiently via wireless medium. Motivated by this, we study broadcasting in the model of ad-hoc wireless networks of weak devices with uniform transmission powers. We compare two settings: with and without local knowledge about immediate neighborhood. In the latter setting, we prove Ω(nlogn)-round lower bound and develop an algorithm matching this formula. This result could be made more accurate with respect to network density, or more precisely, the maximum node degree Δ in the communication graph. If Δ is known to the nodes, it is possible to broadcast in O(DΔlog2n) rounds, which is almost optimal in the class of networks parametrized by D and Δ due to the lower bound Ω(DΔ). In the setting with local knowledge, we design a scalable and almost optimal algorithm accomplishing broadcast in O(Dlog2n) communication rounds, where n is the number of nodes and D is the eccentricity of a network. This can be improved to O(Dlogg) if network granularity g is known to the nodes. Our results imply that the cost of "local communication" is a dominating component in the complexity of wireless broadcasting by weak devices, unlike in traditional models with non-weak devices in which well-scalable solutions can be obtained even without local knowledge.

In this paper the problem of wireless transmissions scheduling in the path-loss/SINR model is considered for different fixed power schemes. The lower bounds for the optimum schedule length proven by Kesselheim and Voecking are considered. It is shown that the lower bound for the linear power scheme is tight, by presenting a constant-factor approximation algorithm. On the other hand, it is shown that the lower bounds proven for many other interesting power schemes can be essentially far from the optima.

Using directional antennae in forming a wireless sensor network has many advantages over omnidirectional, including improved energy efficiency, reduced interference, increased security, and improved routing efficiency. We propose using double (Yagi) directional antennae in 3D space: for a given spherical angle such antennae transmit from their apex simultaneously directionally along two diametrically opposing cones in 3D. We study the resulting network formed by such directional sensors. We design a new algorithm to address strong connectivity of the resulting network and compare its hop-stretch factor with the three-dimensional omnidirectional model. We also obtain a lower bound on the minimum range required to ensure strong connectivity for sensors with double antennae. Further, we present simulation results comparing the diameter of a traditional sensor network using omnidirectional and one using directional antennae.

In this paper, we present a new methodology to adapt any kind of lattice reduction algorithms to deal with the modular knapsack problem. In general, the modular knapsack problem can be solved using a lattice reduction algorithm, when its density is low. The complexity of lattice reduction algorithms to solve those problems is upper-bounded in the function of the lattice dimension and the maximum norm of the input basis. In the case of a low density modular knapsack-type basis, the weight of maximum norm is mainly from its first column. Therefore, by distributing the weight into multiple columns, we are able to reduce the maximum norm of the input basis. Consequently, the upper bound of the time complexity is reduced.

Chunked-reward advertising is commonly used in the industry, such as the guaranteed delivery in display advertising and the daily-deal services e.g., Groupon in online shopping. In chunked-reward advertising, the publisher promises to deliver at least a certain volume a.k.a. tipping point or lower bound of user traffic to an advertiser according to their mutual contract. At the same time, the advertiser may specify a maximum volume upper bound of traffic that he/she would like to pay for according to his/her budget constraint. The objective of the publisher is to design an appropriate mechanism to allocate the user traffic so as to maximize the overall revenue obtained from all such advertisers. In this paper, we perform a formal study on this problem, which we call Chunked-reward Allocation Problem CAP. In particular, we formulate CAP as a knapsack-like problem with variable-sized items and majorization constraints. Our main results regarding CAP are as follows. 1 We first show that for a special case of CAP, in which the lower bound equals the upper bound for each contract, there is a simple dynamic programming-based algorithm that can find an optimal allocation in pseudo-polynomial time. 2 The general case of CAP is much more difficult than the special case. To solve the problem, we first discover several structural properties of the optimal allocation, and then design a two-layer dynamic programming-based algorithm that can find an optimal allocation in pseudo-polynomial time by leveraging these properties. 3 We convert the two-layer dynamic programming based algorithm to a fully polynomial time approximation scheme FPTAS. Besides these results, we also investigate some natural generalizations of CAP, and propose effective algorithms to solve them.

In this paper, we investigate the buffer occupation in wireless social networks. n source nodes are randomly distributed in the networks, and each of them chooses several friend nodes, whose number follows power-law distribution. Two different strategies are proposed to achieve optimal buffer occupation or throughput, and the upper bound and lower bound for buffer size and throughput are also investigated. The results show that there exists trade-off between buffer occupation and throughput, and we also find that the buffer occupation for each node will not increase when the size of network becomes larger, which is opposite to our intuitive understanding.

The main complexity lower and upper bound frontiers seem to be moved only once a decade lately, and Ryan Williams kicked off this decade by proving a new lower bound against Boolean circuits with modular counting. This chapter surveys his proof strategy and why he was able to break through a twenty-year barrier.

Dynamic Time Warping (DTW) is a powerful technique in the time-series similarity search. However, its performance on large-scale data is unsatisfactory because of its high computational cost. Although many methods have been proposed to alleviate this, they are mostly indirect methods, i.e., they do not improve the DTW algorithm itself. In this paper, we propose to incorporate the Ordered Graph Search (OGS) and the lower bound for DTW into an improved DTW algorithm and apply it on time series data. Extensive experiments show that the improved DTW algorithm is faster than the original dynamic programming based algorithm on multi-dimensional time series data. It is also especially useful in the post-processing stage of searching in large time series data based on DTW distance.

This study has presented the End to End (E2E) upper bound capacity limits for high performance mesh nodes that can be deployed in rural and remote areas. The achievable capacity limits for both irregular and clustered placements of nodes have been analytically derived. Numerical results based on the data sheets of IEEE 802.11a/n standards reveal the efficacy of such designs to typical rural networks such as the Peebles valley mesh in rural South Africa.

In this paper, we present an incremental learning method on a budget for embedded systems. We discuss its application for two power systems: a micro-converter for photovoltaic and a step down DC-DC-converter. This learning method is a variation of the general regression neural network but it is able to continue incremental learning on a bounded support set. The method basically learns new instances by adding new kernels. However, when the number of kernels reaches a predefined upper bound, the method selects the most effective learning option from several options: including replacing the most ineffective kernel with the new kernel, modifying of the parameters of existing kernels, and ignoring the new instance. The proposed method is compared with other similar learning methods on a budget, which are based on kernel perceptron. Two examples of the application of the proposed method are demonstrated in power electronics. In these two examples, we show that the proposed system learns the properties of the control-objects during the services and realizes quick control.

In some applications, the tomographic reconstruction is not an end in itself. When the goal is rather to gather information about the object being studied, the question is if it is more interesting to directly extract these information from the projections without the reconstructing step. We would then know if less projections are needed to directly get the information than to reconstruct the object. In this paper, we address the problem of extracting quantitative information about an object namely an estimation of its area, an upper and a lower bound to the perimeter given its projections from point sources.

In the Control Message Aggregation (CMA) problem, control packets are generated over time at the nodes of a tree T and need to be transmitted to the root of T. To optimize the overall cost, these transmissions can be delayed and different packets can be aggregated, that is a single transmission can include all packets from a subtree rooted at the root of T. The cost of this transmission is then equal to the total edge length of this subtree, independently of the number of packets that are sent. A sequence of transmissions that transmits all packets is called a schedule. The objective is to compute a schedule with minimum cost, where the cost of a schedule is the sum of all the transmission costs and delay costs of all packets. The problem is known to be $\mathbb{NP}$-hard, even for trees of depth 2. In the online scenario, it is an open problem whether a constant-competitive algorithm exists. We address the special case of the problem when T is a chain network. For the online case, we present a 5-competitive algorithm and give a lower bound of 2+φ≈3.618, improving the previous bounds of 8 and 2, respectively. Furthermore, for the offline version, we give a polynomial-time algorithm that computes the optimum solution.

Evolutionary algorithms is a class of randomized heuristics inspired by natural evolution. They are applied in many different contexts, in particular in optimization, and analysis of such algorithms has seen tremendous advances in recent years. In this book the author provides an introduction to the methods used to analyze evolutionary algorithms and other randomized search heuristics. He starts with an algorithmic and modular perspective and gives guidelines for the design of evolutionary algorithms. He then places the approach in the broader research context with a chapter on theoretical perspectives. By adopting a complexity-theoretical perspective, he derives general limitations for black-box optimization, yielding lower bounds on the performance of evolutionary algorithms, and then develops general methods for deriving upper and lower bounds step by step. This main part is followed by a chapter covering practical applications of these methods. The notational and mathematical basics are covered in an appendix, the results presented are derived in detail, and each chapter ends with detailed comments and pointers to further reading. So the book is a useful reference for both graduate students and researchers engaged with the theoretical analysis of such algorithms.

Aiming to extend the network lifespan through balancing the energy consumption, an EDRAND (Enhanced DRAND) algorithm based on the node's residual energy is presented in this paper. The EDRAND can be considered as an improved DRAND in which slot sizes are determined by the residual energy of sensor nodes. By taking into account of the nodes' residual energy and the network traffic, an E-ZMAC (Energy-ZMAC) protocol which employs energy control and traffic adaptive mechanism in the Z-MAC protocol, is introduced. In the presented protocol, a node in the network will switch to sleep mode for a while within its slot to reduce power consumption and network traffic. The time span in the sleep mode of a node will be shortened with the growth of the network traffic. A node will switch to TDMA mode when the network traffic reaches a certain upper bound. By doing so, the channel access mode is enabled to transit smoothly from competition-based to scheduling-based. In the presented methodology, the contention window size will be increased with the growth of the network traffic, and the backoff span will be negatively related to the amount of residual energy. To validate the presented approach, a group of simulations are conducted in NS2 under different scenarios. The simulation results have demonstrated that the proposed E-ZMAC protocol outperforms Z-MAC protocol in terms of network lifespan, throughput and energy consumption.

The development of a new software system involves extensive tests on the software functionality in order to identify possible failures. It will be ideal to test all possible input cases (configurations), but the exhaustive approach usually demands too large cost and time. The test suite reduction problem can be defined as the task of generating small set of test cases under certain requirements. A way to design test suites is through interaction testing using a matrix called Covering Array, CA(N;t,k,v), which guarantees that all configurations among every t parameters are covered. This paper presents a simple strategy that reduces the number of rows of a CA. The algorithms represent a post-optimization process which detects wild cards (values that can be changed arbitrarily without the CA losses its degree of coverage) and uses them to merge rows. In the experiment, 667 CAs, created by a state-of-the-art algorithm, were subject to the reduction process. The results report a reduction in the size of 347 CAs (52% of the cases). As part of these results, we report the matrix for CA(42;2,8,6) constructed from CA(57;2,8,6) with an impressive reduction of 15 rows, which is the best upper bound so far.

We consider protocols for two parties to select a random string of a given length n. We are interested in protocols in which the resulting distribution is close to the uniform one even if one party deviates from the protocol. For 2 and 3 round protocols we prove tight upper bounds for the Shannon entropy that such protocols can guarantee for the honest party. We also prove some upper bound for r round protocols for every r.

We study storyboarding where advertisers wish to present sequences of ads (stories) uninterruptedly on a major ad position of a web page. These jobs/stories arrive online and are triggered by the browsing history of a user who at any time continues surfing with probability β. The goal of an ad server is to construct a schedule maximizing the expected reward. The problem was introduced by Dasgupta, Ghosh, Nazerzadeh and Raghavan (SODA'09) who presented a 7-competitive online algorithm. They also showed that no deterministic online strategy can achieve a competitiveness smaller than 2, for general β. We present improved algorithms for storyboarding. First we give a simple online strategy that achieves a competitive ratio of 4/(2−β), which is upper bounded by 4 for any β. The algorithm is also 1/(1−β)-competitive, which gives better bounds for small β. As the main result of this paper we devise a refined algorithm that attains a competitive ratio of c=1+φ, where ϕ = (1 + √5)/2 is the Golden Ratio. This performance guarantee of c≈2.618 is close to the lower bound of 2. Additionally, we study for the first time a problem extension where stories may be presented simultaneously on several ad positions of a web page. For this parallel setting we provide an algorithm whose competitive ratio is upper bounded by $1/(3-2\sqrt{2})\approx 5.828$, for any β. All our algorithms work in phases and have to make scheduling decisions only every once in a while.

We introduce a new algorithm for generating tetrahedral meshes that conform to physical boundaries in volumetric domains consisting of multiple materials. The proposed method allows for an arbitrary number of materials, produces high-quality tetrahedral meshes with upper and lower bounds on dihedral angles, and guarantees geometric fidelity. Moreover, the method is combinatoric so its implementation enables rapid mesh construction. These meshes are structured in a way that also allows grading, in order to reduce element counts in regions of homogeneity.

With the rapid development of navigation technologies, spoofing has become a significant threat to navigation system. As a key step in receiver signal processing, acquisition is an important barrier to anti-spoofing. Nowadays, researching on anti-spoofing performance of acquisition is in a blank stage, threshold method in acquisition is the most commonly used detection strategy. In this article, we add a single spoofing signal on GPS P code and through the construction of mathematical model, we define successful probability of anti-spoofing as the assessment standard, then we analyze the relationship between factors influencing acquisition threshold and the successful probability of anti-spoofing, finally we give the theoretical calculate method of upper bound of threshold method’s anti-spoofing performance, which all have a guiding significance for the design of receiver.

We present a new and flexible approach to repair reactive programs with respect to a specification. The specification is given in linear-temporal logic. Like in previous approaches, we aim for a repaired program that satisfies the specification and is syntactically close to the faulty program. The novelty of our approach is that it produces a program that is also semantically close to the original program by enforcing that a subset of the original traces is preserved. Intuitively, the faulty program is considered to be a part of the specification, which enables us to synthesize meaningful repairs, even for incomplete specifications. Our approach is based on synthesizing a program with a set of behaviors that stay within a lower and an upper bound. We provide an algorithm to decide if a program is repairable with respect to our new notion, and synthesize a repair if one exists. We analyze several ways to choose the set of traces to leave intact and show the boundaries they impose on repairability. We also discuss alternative notions based on reward models to obtain repair systems that behave similar to the original system. We have evaluated the approach on several examples.

We consider the following online scheduling problem in which the input consists of n jobs to be scheduled on identical machines of bounded capacity g (the maximum number of jobs that can be processed simultaneously on a single machine). Each job is associated with a release time and a completion time between which it is supposed to be processed. When a job is released, the online algorithm has to make decision without changing it afterwards. We consider two versions of the problem. In the minimization version, the goal is to minimize the total busy time of machines used to schedule all jobs. In the resource allocation maximization version, the goal is to maximize the number of jobs that are scheduled under a budget constraint given in terms of busy time. This is the first study on online algorithms for these problems. We show a rather large lower bound on the competitive ratio for general instances. This motivates us to consider special families of input instances for which we show constant competitive algorithms. Our study has applications in power aware scheduling, cloud computing and optimizing switching cost of optical networks.

The Signal-to-Interference-and-Noise-Ratio (SINR) physical model is one of the most popular models of wireless networks. Despite of the vast amount of study done in design and analysis of centralized algorithms supporting wireless communication under the SINR physical model, little is known about distributed algorithms in this model, especially deterministic ones. In this work we construct, in a deterministic distributed way, a backbone structure on the top of a given wireless network, which can be used for efficient transformation of many algorithms designed in a simpler model of ad hoc broadcast networks without interference into the SINR physical model with uniform power of stations. The time cost of the backbone data structure construction is only $O(\Delta \text{ \!polylog\! } N)$ rounds, where Δ is roughly the network density and {1,…,N} is the range of identifiers (IDs) and thus N is an upper bound on the number of nodes in the whole network. The core of the construction is a novel combinatorial structure called SINR-selector, which is introduced in this paper. We demonstrate the power of the backbone data structure by using it for obtaining efficient $O(D+\Delta \text{ \!polylog\! } N)$ round and $O(D+k+\Delta \text{ \!polylog\! } N)$ round deterministic distributed solutions for leader election and multi-broadcast, respectively, where D is the network diameter and k is the number of messages to be disseminated.

With the increasing wireless communication demands, frequency spectrum has become more and more limited and expensive. This paper proposes a novel optimization objective: minimizing the required frequency resource, on the premise that both the power constraints and users’ quality of service (QoS) demands can be met. With the frequency saving objective, the primary system can release the unnecessary frequencies for other applications, such as subordinate or cognitive networks. In this paper, we formulate the number of subcarriers minimization problem for both uplink and downlink OFDMA-based networks, which is a mixed NP-hard problem. For the downlink case, we propose an efficient near-optimal algorithm to solve the problem. For the uplink case, we derive low complexity greedy algorithms to obtain tight lower bound and upper bound. Simulation results show that our algorithms can significantly save the system’s frequency resource.

It is indispensable for companies to take some marketing strategy to predict and analyze the sale price met to customer satisfaction. In sale price prediction model, human factors are included in the elements composing the model, and it is getting more difficult to define and describe entire systems precisely. Therefore in case we obtain data from such a model, the data are accompanied by human subjective and experiential uncertainty. In this paper, we develop a theoretical formulation of sale price prediction model based on fuzzy regression with fuzzy input-output data (SPP-model). The solutions of SPP-model is found by solving two LP problems, both Min- and Max-problems, and each of them indicates upper and lower bounds of possibility for solutions (prices).

This paper considers the problem of delay---dependent stabilization criterion for uncertain distributed systems with time-varying delay. The time-varying delay considered is assumed to belong to a given interval in which lower bound of delay is not restricted to zero. Through constructing a suitable Lyapunov-Krasovskii functional, the delay-dependent stabilization criterion is established in terms of linear matrix inequality which can be efficiently solved with available computational software.

In this paper we use an implementation of an access selection architecture, whose main goal is to foster the Always Best Connected paradigm over heterogeneous wireless environments, cornerstone of the Mobility Concepts for IMT-Advanced (Mobilia) project, to enhance quality of service, by means of an integration with the IEEE 802.11e architecture. We provide an upper bound of the performance which might be achieved with this extension and afterwards, using a fully experimental approach, we show the enhancements which can be obtained by dynamically configuring the operational parameters of the subjacent MAC mechanisms.

Wireless Ad-hoc networks are distributed systems that often reside in error-prone environments. Self-stabilization lets the system recover autonomously from an arbitrary system state, making the system recover from errors and temporarily broken assumptions. Clustering nodes within ad-hoc networks can help forming backbones, facilitating routing, improving scaling, aggregating information, saving power and much more. We present a self-stabilizing distributed (k,r)-clustering algorithm. A (k,r)-clustering assigns k cluster heads within r communication hops for all nodes in the network while trying to minimize the total number of cluster heads. The algorithm assumes a bound on clock frequency differences and a limited guarantee on message delivery. It uses multiple paths to different cluster heads for improved security, availability and fault tolerance. The algorithm assigns, when possible, at least k cluster heads to each node within O(rπλ3) time from an arbitrary system configuration, where π is a limit on message loss and λ is a limit on pulse rate differences. The set of cluster heads stabilizes, with high probability, to a local minimum within O(rπλ4glogn) time, where n is the size of the network and g is an upper bound on the number of nodes within 2r hops.

With the emergence of Role Based Access Control (RBAC) as the de facto access control model, organizations can now implement and manage many high level security policies. As a means of migration from traditional access control systems to RBAC, different role mining algorithms have been proposed in recent years for finding a minimal set of roles from existing user-permission assignments. While determining such roles, it is often required that certain security objectives are satisfied. A common goal is to enforce the role-usage cardinality constraint, which limits the maximum number of roles any user can have. In this paper, we propose two alternative approaches for role mining with an upper bound on the number of roles that can be assigned to each user, and validate their performance with benchmark data sets.

We present how to perform exact large-scale multi-class Gaussian process classification with parameterized histogram intersection kernels. In contrast to previous approaches, we use a full Bayesian model without any sparse approximation techniques, which allows for learning in sub-quadratic and classification in constant time. To handle the additional model flexibility induced by parameterized kernels, our approach is able to optimize the parameters with large-scale training data. A key ingredient of this optimization is a new efficient upper bound of the negative Gaussian process log-likelihood. Experiments with image categorization tasks exhibit high performance gains with flexible kernels as well as learning within a few minutes and classification in microseconds for databases, where exact Gaussian process inference was not possible before.

Contribution. We study the fundamental naming and counting problems in networks that are anonymous, unknown, and possibly dynamic. Network dynamicity is modeled by the 1-interval connectivity model [KLO10]. We first prove that on static networks with broadcast counting is impossible to solve without a leader and that naming is impossible to solve even with a leader and even if nodes know n. These impossibilities carry over to dynamic networks as well. With a leader we solve counting in linear time. Then we focus on dynamic networks with broadcast. We show that if nodes know an upper bound on the maximum degree that will ever appear then they can obtain an upper bound on n. Finally, we replace broadcast with one-to-each, in which a node may send a different message to each of its neighbors. This variation is then proved to be computationally equivalent to a full-knowledge model with unique names.

The Vehicle Positioning Problem (VPP) is a classical combinatorial optimization problem that has a natural formulation as a Mixed Integer Quadratically Constrained Program. This MIQCP is closely related to the Quadratic Assignment Problem and, as far as we know, has not received any attention yet. We show in this article that such a formulation has interesting theoretical properties. Its QP relaxation produces, in particular, the first known nontrivial lower bound on the number of shuntings. In our experiments, it also outperformed alternative integer linear models computationally. The strengthening technique that raises the lower bound might also be useful for other combinatorial optimization problems.

In this paper, we investigate the impact of group multicast on the capacity of large-scale random wireless networks. n nodes are randomly distributed in the networks, among which n s nodes are selected as sources and n d destined nodes are chosen for each. Specifically, we consider two different scenarios, i.e., (1) regular distribution scenario, and (2) random distribution scenario. The upper bound capacity of group multicast is derived for the network. Furthermore, we propose the corresponding capacity-achieving communication schemes to achieve the upper bound. Moreover, our study is the first attempt to understand how group multicast may impact on large scale network capacity from a theoretical perspective.