OpenRaiser/Intern-Atlas huggingface dataset:
Full-Duplex Wireless-Powered Communication Network with Energy Causality
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we consider a wireless communication network with a full-duplex hybrid access point (HAP) and a set of wireless users with energy harvesting capabilities. The HAP implements the full-duplex through two antennas: one for broadcasting wireless energy to users in the downlink and one for receiving independent information from users via time-division-multiple-access (TDMA) in the uplink at the same time. All users can continuously harvest wireless power from the HAP until its transmission slot, i.e., the energy causality constraint is modeled by assuming that energy harvested in the future cannot be used for tranmission. Hence, latter users' energy harvesting time is coupled with the transmission time of previous users. Under this setup, we investigate the sum-throughput maximization (STM) problem and the total-time minimization (TTM) problem for the proposed multi-user full-duplex wireless-powered network. The STM problem is proved to be a convex optimization problem. The optimal solution strategy is then obtained in closed-form expression, which can be computed with linear complexity. It is also shown that the sum throughput is non-decreasing with increasing of the number of users. For the TTM problem, by exploiting the properties of the coupling constraints, we propose a two-step algorithm to obtain an optimal solution. Then, for each problem, two suboptimal solutions are proposed and investigated. Finally, the effect of user scheduling on STM and TTM are investigated through simulations. It is also shown that different user scheduling strategies should be used for STM and TTM.
Monadic Datalog Containment on Trees
Venue: arXiv cs.LO 2014
Year: 2014

We show that the query containment problem for monadic datalog on finite unranked labeled trees can be solved in 2-fold exponential time when (a) considering unordered trees using the axes child and descendant, and when (b) considering ordered trees using the axes firstchild, nextsibling, child, and descendant. When omitting the descendant-axis, we obtain that in both cases the problem is EXPTIME-complete.
A probabilistic estimation and prediction technique for dynamic continuous social science models: The evolution of the attitude of the Basque Country population towards ETA as a case study
Venue: arXiv cs.LG 2014
Year: 2014

In this paper, we present a computational technique to deal with uncertainty in dynamic continuous models in Social Sciences. Considering data from surveys, the method consists of determining the probability distribution of the survey output and this allows to sample data and fit the model to the sampled data using a goodness-of-fit criterion based on the chi-square-test. Taking the fitted parameters non-rejected by the chi-square-test, substituting them into the model and computing their outputs, we build 95% confidence intervals in each time instant capturing uncertainty of the survey data (probabilistic estimation). Using the same set of obtained model parameters, we also provide a prediction over the next few years with 95% confidence intervals (probabilistic prediction). This technique is applied to a dynamic social model describing the evolution of the attitude of the Basque Country population towards the revolutionary organization ETA.
Resistance of Statistical Attacks of Parastrophic Quasigroup Transformation
Venue: arXiv cs.CR 2014
Year: 2014

In this paper, we prove an important cryptographic property of $PE$-transformation proposed elsewhere. If $PE$-transformation is used as encrypting function then after $n$ applications of it on arbitrary message the distribution of $l$-tuples ($l=1,2,\dots, n$) is uniform. This property implies the resistance of statistical kind of attack of this transformation. For illustration of theoretical results, some experimental results are presented as well.
Component Substitution through Dynamic Reconfigurations
Venue: arXiv cs.SE 2014
Year: 2014

Component substitution has numerous practical applications and constitutes an active research topic. This paper proposes to enrich an existing component-based framework--a model with dynamic reconfigurations making the system evolve--with a new reconfiguration operation which "substitutes" components by other components, and to study its impact on sequences of dynamic reconfigurations. Firstly, we define substitutability constraints which ensure the component encapsulation while performing reconfigurations by component substitutions. Then, we integrate them into a substitutability-based simulation to take these substituting reconfigurations into account on sequences of dynamic reconfigurations. Thirdly, as this new relation being in general undecidable for infinite-state systems, we propose a semi-algorithm to check it on the fly. Finally, we report on experimentations using the B tools to show the feasibility of the developed approach, and to illustrate the paper's proposals on an example of the HTTP server.
Automated Mapping of UML Activity Diagrams to Formal Specifications for Supporting Containment Checking
Venue: arXiv cs.SE 2014
Year: 2014

Business analysts and domain experts are often sketching the behaviors of a software system using high-level models that are technology- and platform-independent. The developers will refine and enrich these high-level models with technical details. As a consequence, the refined models can deviate from the original models over time, especially when the two kinds of models evolve independently. In this context, we focus on behavior models; that is, we aim to ensure that the refined, low-level behavior models conform to the corresponding high-level behavior models. Based on existing formal verification techniques, we propose containment checking as a means to assess whether the system's behaviors described by the low-level models satisfy what has been specified in the high-level counterparts. One of the major obstacles is how to lessen the burden of creating formal specifications of the behavior models as well as consistency constraints, which is a tedious and error-prone task when done manually. Our approach presented in this paper aims at alleviating the aforementioned challenges by considering the behavior models as verification inputs and devising automated mappings of behavior models onto formal properties and descriptions that can be directly used by model checkers. We discuss various challenges in our approach and show the applicability of our approach in illustrative scenarios.
Enabling Automatic Certification of Online Auctions
Venue: arXiv cs.LO 2014
Year: 2014

We consider the problem of building up trust in a network of online auctions by software agents. This requires agents to have a deeper understanding of auction mechanisms and be able to verify desirable properties of a given mechanism. We have shown how these mechanisms can be formalised as semantic web services in OWL-S, a good enough expressive machine-readable formalism enabling software agents, to discover, invoke, and execute a web service. We have also used abstract interpretation to translate the auction's specifications from OWL-S, based on description logic, to COQ, based on typed lambda calculus, in order to enable automatic verification of desirable properties of the auction by the software agents. For this language translation, we have discussed the syntactic transformation as well as the semantics connections between both concrete and abstract domains. This work contributes to the implementation of the vision of agent-mediated e-commerce systems.
Binary pattern tile set synthesis is NP-hard
Venue: arXiv cs.CC 2014
Year: 2014

In the field of algorithmic self-assembly, a long-standing unproven conjecture has been that of the NP-hardness of binary pattern tile set synthesis (2-PATS). The $k$-PATS problem is that of designing a tile assembly system with the smallest number of tile types which will self-assemble an input pattern of $k$ colors. Of both theoretical and practical significance, $k$-PATS has been studied in a series of papers which have shown $k$-PATS to be NP-hard for $k = 60$, $k = 29$, and then $k = 11$. In this paper, we close the fundamental conjecture that 2-PATS is NP-hard, concluding this line of study. While most of our proof relies on standard mathematical proof techniques, one crucial lemma makes use of a computer-assisted proof, which is a relatively novel but increasingly utilized paradigm for deriving proofs for complex mathematical problems. This tool is especially powerful for attacking combinatorial problems, as exemplified by the proof of the four color theorem by Appel and Haken (simplified later by Robertson, Sanders, Seymour, and Thomas) or the recent important advance on the Erdős discrepancy problem by Konev and Lisitsa using computer programs. We utilize a massively parallel algorithm and thus turn an otherwise intractable portion of our proof into a program which requires approximately a year of computation time, bringing the use of computer-assisted proofs to a new scale. We fully detail the algorithm employed by our code, and make the code freely available online.
Improved channel estimation for interference cancellation in random access methods for satellite communications
Venue: arXiv cs.IT 2014
Year: 2014

In the context of satellite communications, random access (RA) methods can significantly increase throughput and reduce latency over the network. The recent RA methods are based on multi-user multiple access transmission at the same time and frequency combined with interference cancellation and iterative decoding at the receiver. Generally, it is assumed that perfect knowledge of the interference is available at the receiver. In practice, the interference term has to be accurately estimated to avoid performance degradation. Several estimation techniques have been proposed lately in the case of superimposed signals. In this paper, we present an improved channel estimation technique that combines estimation using an autocorrelation based method and the Expectation-Maximization algorithm, and uses Pilot Symbol Assisted Modulation to further improve the performance and achieve optimal interference cancellation.
Online bin packing with cardinality constraints revisited
Venue: arXiv cs.DS 2014
Year: 2014

Bin packing with cardinality constraints is a bin packing problem where an upper bound k \geq 2 on the number of items packed into each bin is given, in addition to the standard constraint on the total size of items packed into a bin. We study the online scenario where items are presented one by one. We analyze it with respect to the absolute competitive ratio and prove tight bounds of 2 for any k \geq 4. We show that First Fit also has an absolute competitive ratio of 2 for k=4, but not for larger values of k, and we present a complete analysis of its asymptotic competitive ratio for all values of k \geq 5. Additionally, we study the case of small $k$ with respect to the asymptotic competitive ratio and the absolute competitive ratio.
Characterizing Spatial Patterns of Base Stations in Cellular Networks
Venue: arXiv cs.NI 2014
Year: 2014

The topology of base stations (BSs) in cellular networks, serving as a basis of networking performance analysis, is considered to be obviously distinctive with the traditional hexagonal grid or square lattice model, thus stimulating a fundamental rethinking. Recently, stochastic geometry based models, especially the Poisson point process (PPP), attracts an ever-increasing popularity in modeling BS deployment of cellular networks due to its merits of tractability and capability for capturing nonuniformity. In this study, a detailed comparison between common stochastic models and real BS locations is performed. Results indicate that the PPP fails to precisely characterize either urban or rural BS deployment. Furthermore, the topology of real data in both regions are examined and distinguished by statistical methods according to the point interaction trends they exhibit. By comparing the corresponding real data with aggregative point process models as well as repulsive point process models, we verify that the capacity-centric deployment in urban areas can be modeled by typical aggregative processes such as the Matern cluster process, while the coverage-centric deployment in rural areas can be modeled by representative
Hadamard Coded Modulation: An Alternative to OFDM for Optical Wireless Communications
Venue: arXiv cs.IT 2014
Year: 2014

Orthogonal frequency division multiplexing (OFDM) is a modulation technique susceptible to source, channel and amplifier nonlinearities because of its high peak-to-average ratio (PAPR). The distortion gets worse by increasing the average power of the OFDM signals since larger portion of the signals are affected by nonlinearity. In this paper we introduce Hadamard coded modulation (HCM) that uses the fast Walsh-Hadamard transform (FWHT) to modulate data as an alternative technique to OFDM in direct-detection wireless optical systems. This technique is shown to have a better performance for high average optical power scenarios because of its small PAPR, and can be used instead of OFDM in two scenarios: 1) in optical systems that require high average optical powers such as visible light communications (VLC), and 2) in optical wireless systems unconstrained by average power, for which HCM achieves lower bit error rate (BER) compared to OFDM. The power efficiency of HCM can be improved by removing a part of the signal's DC bias without losing any information. In this way, the amplitude of the transmitted signal is decreased and the signals become less susceptible to nonlinearity. Interleaving can be applied on HCM to make the resulting signals resistent against inter-symbol interference (ISI) effects in dispersive channels by uniformly distributing the interference over all symbols.
Color to Gray and Back transformation for distributing color digital images
Venue: arXiv cs.MM 2014
Year: 2014

The Color to Gray and Back transformation watermarking with a secrete key is considered. Color is embedded into the bit planes of the luminosity component of the YUV color space with the help of a block algorithm that allows using not only the least significant bits. An application of the problem of distributing color digital images from a data base among legitimate users is discussed. The proposed protocol can protect original images from unauthorized copying.
Lower bounds for testing digraph connectivity with one-pass streaming algorithms
Venue: arXiv cs.DS 2014
Year: 2014

In this note, we show that three graph properties - strong connectivity, acyclicity, and reachability from a vertex $s$ to all vertices - each require a working memory of $Ω(εm)$ on a graph with $m$ edges to be determined correctly with probability greater than $(1+ε)/2$.
Optimal Budget Allocation in Social Networks: Quality or Seeding
Venue: arXiv cs.SI 2014
Year: 2014

In this paper, we study a strategic model of marketing and product consumption in social networks. We consider two competing firms in a market providing two substitutable products with preset qualities. Agents choose their consumptions following a myopic best response dynamics which results in a local, linear update for the consumptions. At some point in time, firms receive a limited budget which they can use to trigger a larger consumption of their products in the network. Firms have to decide between marginally improving the quality of their products and giving free offers to a chosen set of agents in the network in order to better facilitate spreading their products. We derive a simple threshold rule for the optimal allocation of the budget and describe the resulting Nash equilibrium. It is shown that the optimal allocation of the budget depends on the entire distribution of centralities in the network, quality of products and the model parameters. In particular, we show that in a graph with a higher number of agents with centralities above a certain threshold, firms spend more budget on seeding in the optimal allocation. Furthermore, if seeding budget is nonzero for a balanced graph, it will also be nonzero for any other graph, and if seeding budget is zero for a star graph, it will be zero for any other graph too. We also show that firms allocate more budget to quality improvement when their qualities are close, in order to distance themselves from the rival firm. However, as the gap between qualities widens, competition in qualities becomes less effective and firms spend more budget on seeding.
A Review of Power Aware Routing Protocols in Wireless Sensor Networks
Venue: arXiv cs.NI 2014
Year: 2014

WSNs are envisioned to consist of many small devices that can sense the environment and communicate the data as required. The most critical requirement for widespread sensor networks is power efficiency since battery replacement is not viable. Many protocols are proposed to minimize the power consumption by using complex algorithms. However, it is difficult to perform these complex methods since an individual sensor node in sensor networks does not have high computational capacity. On the other hand, many sensor nodes should transfer the data packet to the sink node that collects the required data. Therefore, the operations of the sensor nodes over the route are terminated. It is difficult to deliver the data packet to the sink node even if some sensor nodes are active. In this paper, an introduction of WSNs is presented with a deep insight into the power-aware routing protocol for sensor networks. The protocols considered are LEACH,VGA and PEGASIS. In addition, a comparison of these protocols is also presented.
High Throughput and Less Area AMP Architecture for Audio Signal Restoration
Venue: arXiv cs.SD 2014
Year: 2014

Audio restoration is effectively achieved by using low complexity algorithm called AMP. This algorithm has fast convergence and has lower computation intensity making it suitable for audio recovery problems. This paper focuses on restoring an audio signal by using VLSI architecture called AMP-M that implements AMP algorithm. This architecture employs MAC unit with fixed bit Wallace tree multiplier, FFT-MUX and various memory units (RAM) for audio restoration. VLSI and FPGA implementation results shows that reduced area, high throughput, low power is achieved making it suitable for real time audio recovery problems. Prominent examples are Magnetic Resonance Imaging (MRI), Radar and Wireless Communications.
MUSIC for Single-Snapshot Spectral Estimation: Stability and Super-resolution
Venue: arXiv cs.IT 2014
Year: 2014

This paper studies the problem of line spectral estimation in the continuum of a bounded interval with one snapshot of array measurement. The single-snapshot measurement data is turned into a Hankel data matrix which admits the Vandermonde decomposition and is suitable for the MUSIC algorithm. The MUSIC algorithm amounts to finding the null space (the noise space) of the Hankel matrix, forming the noise-space correlation function and identifying the s smallest local minima of the noise-space correlation as the frequency set. In the noise-free case exact reconstruction is guaranteed for any arbitrary set of frequencies as long as the number of measurements is at least twice the number of distinct frequencies to be recovered. In the presence of noise the stability analysis shows that the perturbation of the noise-space correlation is proportional to the spectral norm of the noise matrix as long as the latter is smaller than the smallest (nonzero) singular value of the noiseless Hankel data matrix. Under the assumption that frequencies are separated by at least twice the Rayleigh Length (RL), the stability of the noise-space correlation is proved by means of novel discrete Ingham inequalities which provide bounds on nonzero singular values of the noiseless Hankel data matrix. The numerical performance of MUSIC is tested in comparison with other algorithms such as BLO-OMP and SDP (TV-min). While BLO-OMP is the stablest algorithm for frequencies separated above 4 RL, MUSIC becomes the best performing one for frequencies separated between 2 RL and 3 RL. Also, MUSIC is more efficient than other methods. MUSIC truly shines when the frequency separation drops to 1 RL or below when all other methods fail. Indeed, the resolution length of MUSIC decreases to zero as noise decreases to zero as a power law with an exponent much smaller than an upper bound established by Donoho.
Sparse Coding: A Deep Learning using Unlabeled Data for High - Level Representation
Venue: arXiv cs.LG 2014
Year: 2014

Sparse coding algorithm is an learning algorithm mainly for unsupervised feature for finding succinct, a little above high - level Representation of inputs, and it has successfully given a way for Deep learning. Our objective is to use High - Level Representation data in form of unlabeled category to help unsupervised learning task. when compared with labeled data, unlabeled data is easier to acquire because, unlike labeled data it does not follow some particular class labels. This really makes the Deep learning wider and applicable to practical problems and learning. The main problem with sparse coding is it uses Quadratic loss function and Gaussian noise mode. So, its performs is very poor when binary or integer value or other Non- Gaussian type data is applied. Thus first we propose an algorithm for solving the L1 - regularized convex optimization algorithm for the problem to allow High - Level Representation of unlabeled data. Through this we derive a optimal solution for describing an approach to Deep learning algorithm by using sparse code.
MU-MIMO MAC Protocols for Wireless Local Area Networks: A Survey
Venue: arXiv cs.NI 2014
Year: 2014

As wireless devices boom, and bandwidth-hungry applications (e.g., video and cloud uploading) get popular, today's Wireless Local Area Networks (WLANs) become not only crowded but also stressed at throughput. Multi-user Multiple-Input and Multiple-Output (MU-MIMO), an advanced form of MIMO, has gained attention due to its huge potential in improving the performance of WLANs. This paper surveys random access based MAC protocols for MU-MIMO enabled WLANs. It first provides background information about the evolution and the fundamental MAC schemes of IEEE 802.11 Standards and Amendments, and then identifies the key requirements of designing MU-MIMO MAC protocols for WLANs. After that, the most representative MU-MIMO MAC proposals in the literature are overviewed by benchmarking their MAC procedures and examining the key components, such as the channel state information acquisition, de/pre-coding and scheduling schemes. Classifications and discussions on important findings of the surveyed MAC protocols are provided, based on which, the research challenges for designing effective MU-MIMO MAC protocols, as well as the envisaged MAC's role in the future heterogeneous networks, are highlighted.
Analysis, Review and Optimization of SONET/SDH Technology for today and future aspects
Venue: arXiv cs.NI 2014
Year: 2014

Network layers are analyzed for their design and issues of researches, while dense wavelength division multiplexing equipment has been deployed in networks of major telecommunications carriers for a long time, the efficiency of networking and relation with network control and management have not caught up to those of digital cross-connect systems and packet-switched counterparts in higher layer networks.
Fun with Fonts: Algorithmic Typography
Venue: arXiv cs.CG 2014
Year: 2014

Over the past decade, we have designed six typefaces based on mathematical theorems and open problems, specifically computational geometry. These typefaces expose the general public in a unique way to intriguing results and hard problems in hinged dissections, geometric tours, origami design, computer-aided glass design, physical simulation, and protein folding. In particular, most of these typefaces include puzzle fonts, where reading the intended message requires solving a series of puzzles which illustrate the challenge of the underlying algorithmic problem.