OpenRaiser/Intern-Atlas huggingface dataset:
Cooperative Relaying at Finite SNR -- Role of Quantize-Map-and-Forward
Venue: arXiv cs.IT 2013
Year: 2013

Quantize-Map-and-Forward (QMF) relaying has been shown to achieve the optimal diversity-multiplexing trade-off (DMT) for arbitrary slow fading full-duplex networks as well as for the single-relay half-duplex network. A key reason for this is that quantizing at the noise level suffices to achieve the cut-set bound approximately to within an additive gap, without any requirement of instantaneous channel state information (CSI). However, DMT only captures the high SNR performance and potentially, limited CSI at the relay can improve performance at moderate SNRs. In this work we propose an optimization framework for QMF relaying over slow fading channels. Focusing on vector Gaussian quantizers, we optimize the outage probability for the full-duplex and half-duplex single relay by finding the best quantization level and relay schedule according to the available CSI at the relays. For the N-relay diamond network, we derive an universal quantizer that sharpens the additive approximation gap of QMF from the conventional Θ(N) bits/s/Hz to Θ(log(N)) bits/s/Hz using only network topology information. Analytical solutions to channel-aware optimal quantizers for two-relay and symmetric N-relay diamond networks are also derived. In addition, we prove that suitable hybridizations of our optimized QMF schemes with Decode-Forward (DF) or Dynamic DF protocols provide significant finite SNR gains over the individual schemes.
Source localization in reverberant rooms using sparse modeling and narrowband measurements
Venue: arXiv cs.IT 2013
Year: 2013

We study two cases of acoustic source localization in a reverberant room, from a number of point-wise narrowband measurements. In the first case, the room is perfectly known. We show that using a sparse recovery algorithm with a dictionary of sources computed a priori requires measurements at multiple frequencies. Furthermore, we study the choice of frequencies for these measurements, and show that one should avoid the modal frequencies of the room. In the second case, when the shape and the boundary conditions of the room are unknown, we propose a model of the acoustical field based on the Vekua theory, still allowing the localization of sources, at the cost of an increased number of measurements. Numerical results are given, using simple adaptations of standard sparse recovery methods.
Hard Asymptotic Sets for One-Dimensional Cellular Automata
Venue: arXiv cs.CC 2013
Year: 2013

We prove that the (language of the) asymptotic set (and the nonwandering set) of a one-dimensional cellular automaton can be $\SIGMA^1_1$-hard. We do not go into much detail, since the constructions are relatively standard.
DCE: A Novel Delay Correlation Measurement for Tomography with Passive Realization
Venue: arXiv cs.NI 2013
Year: 2013

Tomography is important for network design and routing optimization. Prior approaches require either precise time synchronization or complex cooperation. Furthermore, active tomography consumes explicit probeing resulting in limited scalability. To address the first issue we propose a novel Delay Correlation Estimation methodology named DCE with no need of synchronization and special cooperation. For the second issue we develop a passive realization mechanism merely using regular data flow without explicit bandwidth consumption. Extensive simulations in OMNeT++ are made to evaluate its accuracy where we show that DCE measured delay correlation is highly identical with the true value. Also from test result we find that mechanism of passive realization is able to achieve both regular data transmission and purpose of tomography with excellent robustness versus different background traffic and package size.
Coloring directed cycles
Venue: arXiv cs.DM 2013
Year: 2013

Sopena in his survey [E. Sopena, The oriented chromatic number of graphs: A short survey, preprint 2013] writes, without any proof, that an oriented cycle $\vec C$ can be colored with three colors if and only if $λ(\vec C)=0$, where $λ(\vec C)$ is the number of forward arcs minus the number of backward arcs in $\vec C$. This is not true. In this paper we show that $\vec C$ can be colored with three colors if and only if $λ(\vec C)=0(\bmod~3)$ or $\vec C$ does not contain three consecutive arcs going in the same direction.
Expressiveness and Robustness of First-Price Position Auctions
Venue: arXiv cs.GT 2013
Year: 2013

Since economic mechanisms are often applied to very different instances of the same problem, it is desirable to identify mechanisms that work well in a wide range of circumstances. We pursue this goal for a position auction setting and specifically seek mechanisms that guarantee good outcomes under both complete and incomplete information. A variant of the generalized first-price mechanism with multi-dimensional bids turns out to be the only standard mechanism able to achieve this goal, even when types are one-dimensional. The fact that expressiveness beyond the type space is both necessary and sufficient for this kind of robustness provides an interesting counterpoint to previous work on position auctions that has highlighted the benefits of simplicity. From a technical perspective our results are interesting because they establish equilibrium existence for a multi-dimensional bid space, where standard techniques break down. The structure of the equilibrium bids moreover provides an intuitive explanation for why first-price payments may be able to support equilibria in a wider range of circumstances than second-price payments.
Polymatroid Prophet Inequalities
Venue: arXiv cs.DS 2013
Year: 2013

Consider a gambler and a prophet who observe a sequence of independent, non-negative numbers. The gambler sees the numbers one-by-one whereas the prophet sees the entire sequence at once. The goal of both is to decide on fractions of each number they want to keep so as to maximize the weighted fractional sum of the numbers chosen. The classic result of Krengel and Sucheston (1977-78) asserts that if both the gambler and the prophet can pick one number, then the gambler can do at least half as well as the prophet. Recently, Kleinberg and Weinberg (2012) have generalized this result to settings where the numbers that can be chosen are subject to a matroid constraint. In this note we go one step further and show that the bound carries over to settings where the fractions that can be chosen are subject to a polymatroid constraint. This bound is tight as it is already tight for the simple setting where the gambler and the prophet can pick only one number. An interesting application of our result is in mechanism design, where it leads to improved results for various problems.
Ontology alignment repair through modularization and confidence-based heuristics
Venue: arXiv cs.AI 2013
Year: 2013

Ontology Matching aims to find a set of semantic correspondences, called an alignment, between related ontologies. In recent years, there has been a growing interest in efficient and effective matching methods for large ontologies. However, most of the alignments produced for large ontologies are logically incoherent. It was only recently that the use of repair techniques to improve the quality of ontology alignments has been explored. In this paper we present a novel technique for detecting incoherent concepts based on ontology modularization, and a new repair algorithm that minimizes the incoherence of the resulting alignment and the number of matches removed from the input alignment. An implementation was done as part of a lightweight version of AgreementMaker system, a successful ontology matching platform, and evaluated using a set of four benchmark biomedical ontology matching tasks. Our results show that our implementation is efficient and produces better alignments with respect to their coherence and f-measure than the state of the art repairing tools. They also show that our implementation is a better alternative for producing coherent silver standard alignments.
How do Viruses Attack Anti-Virus Programs
Venue: arXiv cs.CR 2013
Year: 2013

As the anti-viruses run in a trusted kernel level any loophole in the anti-virus program can enable attackers to take full control over the computer system and steal data or do serious damages. Hence the anti-virus engines must be developed with proper security in mind. The ant-virus should be able to any type of specially created executable files, compression packages or documents that are intentionally created to exploit the anti-virus weakness. Viruses are present in almost every system even though there are anti-viruses installed. This is because every anti-virus, however good it may be, leads to some extent of false positives and false negatives. Our faith on the anti-virus system often makes us more careless about hygienic habits which increases the possibility of infection. It is necessary for an anti-virus to detect and destroy the malware before its own files are detected and destroyed by the malware.
10 Inventions on keyboard attachments-A TRIZ based analysis
Venue: arXiv cs.HC 2013
Year: 2013

Although the primary objective of the keyboard to input data into the computer, the advanced keyboards keep various other things in mind, such as, how to use the same keyboard for various other purposes, or how to use the same keyboard efficiently by using various other attachments to the keyboard. This objective led to various inventions on keyboard attachments, some of which are illustrated below in this article. This article illustrates 10 inventions on various keyboard attachments from US patent database. Each different attachment improves the usability of the keyboard in some way or other. Some attachments illustrated are template holders, paper holders, pointing device attachments, mouse pad attachments, wrist rest attachments, storage device attachments, and multimedia attachments.
A Novel Equation based Classifier for Detecting Human in Images
Venue: arXiv cs.CV 2013
Year: 2013

Shape based classification is one of the most challenging tasks in the field of computer vision. Shapes play a vital role in object recognition. The basic shapes in an image can occur in varying scale, position and orientation. And specially when detecting human, the task becomes more challenging owing to the largely varying size, shape, posture and clothing of human. So, in our work we detect human, based on the head-shoulder shape as it is the most unvarying part of human body. Here, firstly a new and a novel equation named as the Omega Equation that describes the shape of human head-shoulder is developed and based on this equation, a classifier is designed particularly for detecting human presence in a scene. The classifier detects human by analyzing some of the discriminative features of the values of the parameters obtained from the Omega equation. The proposed method has been tested on a variety of shape dataset taking into consideration the complexities of human head-shoulder shape. In all the experiments the proposed method demonstrated satisfactory results.
Robotic Arm for Remote Surgery
Venue: arXiv cs.RO 2013
Year: 2013

Recent advances in telecommunications have enabled surgeons to operate remotely on patients with the use of robotics. The investigation and testing of remote surgery using a robotic arm is presented. The robotic arm is designed to have four degrees of freedom that track the surgeon's x, y, z positions and the rotation angle of the forearm θ. The system comprises two main subsystems viz. the detecting and actuating systems. The detection system uses infrared light-emitting diodes, a retroreflective bracelet and two infrared cameras which as a whole determine the coordinates of the surgeon's forearm. The actuation system, or robotic arm, is based on a lead screw mechanism which can obtain a maximum speed of 0.28 m/s with a 1.5 degree/step for the end-effector. The infrared detection and encoder resolutions are below 0.6 mm/pixel and 0.4 mm respectively, which ensures the robotic arm can operate precisely. The surgeon is able to monitor the patient with the use of a graphical user interface on the display computer. The lead screw system is modelled and compared to experimentation results. The system is controlled using a simple proportional-integrator (PI) control scheme which is implemented on a dSpace control unit. The control design results in a rise time of less than 0.5 s, a steady-state error of less than 1 mm and settling time of less than 1.4 s. The system accumulates, over an extended period of time, an error of approximately 4 mm due to inertial effects of the robotic arm. The results show promising system performance characteristics for a relatively inexpensive solution to a relatively advanced application.
A New Strategy of Cost-Free Learning in the Class Imbalance Problem
Venue: arXiv cs.LG 2013
Year: 2013

In this work, we define cost-free learning (CFL) formally in comparison with cost-sensitive learning (CSL). The main difference between them is that a CFL approach seeks optimal classification results without requiring any cost information, even in the class imbalance problem. In fact, several CFL approaches exist in the related studies, such as sampling and some criteria-based pproaches. However, to our best knowledge, none of the existing CFL and CSL approaches are able to process the abstaining classifications properly when no information is given about errors and rejects. Based on information theory, we propose a novel CFL which seeks to maximize normalized mutual information of the targets and the decision outputs of classifiers. Using the strategy, we can deal with binary/multi-class classifications with/without abstaining. Significant features are observed from the new strategy. While the degree of class imbalance is changing, the proposed strategy is able to balance the errors and rejects accordingly and automatically. Another advantage of the strategy is its ability of deriving optimal rejection thresholds for abstaining classifications and the "equivalent" costs in binary classifications. The connection between rejection thresholds and ROC curve is explored. Empirical investigation is made on several benchmark data sets in comparison with other existing approaches. The classification results demonstrate a promising perspective of the strategy in machine learning.
Rotational Mutation Genetic Algorithm on optimization Problems
Venue: arXiv cs.NE 2013
Year: 2013

Optimization problem, nowadays, have more application in all major but they have problem in computation. Calculation of the optimum point in the spaces with the above dimensions is very time consuming. In this paper, there is presented a new approach for the optimization of continuous functions with rotational mutation that is called RM. The proposed algorithm starts from the point which has best fitness value by elitism mechanism. Then, method of rotational mutation is used to reach optimal point. In this paper, RM algorithm is implemented by GA(Briefly RMGA) and is compared with other well- known algorithms: DE, PGA, Grefensstette and Eshelman [15, 16] and numerical and simulation results show that RMGA achieve global optimal point with more decision by smaller generations.
The Use of Cuckoo Search in Estimating the Parameters of Software Reliability Growth Models
Venue: arXiv cs.AI 2013
Year: 2013

This work aims to investigate the reliability of software products as an important attribute of computer programs; it helps to decide the degree of trustworthiness a program has in accomplishing its specific functions. This is done using the Software Reliability Growth Models (SRGMs) through the estimation of their parameters. The parameters are estimated in this work based on the available failure data and with the search techniques of Swarm Intelligence, namely, the Cuckoo Search (CS) due to its efficiency, effectiveness and robustness. A number of SRGMs is studied, and the results are compared to Particle Swarm Optimization (PSO), Ant Colony Optimization (ACO) and extended ACO. Results show that CS outperformed both PSO and ACO in finding better parameters tested using identical datasets. It was sometimes outperformed by the extended ACO. Also in this work, the percentages of training data to testing data are investigated to show their impact on the results.
Continuous Double Auction Mechanism and Bidding Strategies in Cloud Computing Markets
Venue: arXiv cs.DC 2013
Year: 2013

Cloud computing has been an emerging model which aims at allowing customers to utilize computing resources hosted by Cloud Service Providers (CSPs). More and more consumers rely on CSPs to supply computing and storage service on the one hand, and CSPs try to attract consumers on favorable terms on the other. In such competitive cloud computing markets, pricing policies are critical to market efficiency. While CSPs often publish their prices and charge users according to the amount of resources they consume, auction mechanism is rarely applied. In fact a feasible auction mechanism is the most effective method for allocation of resources, especially double auction is more efficient and flexible for it enables buyers and sellers to enter bids and offers simultaneously. In this paper we bring up an electronic auction platform for cloud, and a cloud Continuous Double Auction (CDA) mechanism is formulated to match orders and facilitate trading based on the platform. Some evaluating criteria are defined to analyze the efficiency of markets and strategies. Furthermore, the selection of bidding strategies for the auction plays a very important role for each player to maximize its own profit, so we developed a novel bidding strategy for cloud CDA, BH-strategy, which is a two-stage game bidding strategy. At last we designed three simulation scenarios to compare the performance of our strategy with other dominating bidding strategies and proved that BH-strategy has better performance on surpluses, successful transactions and market efficiency. In addition, we discussed that our cloud CDA mechanism is feasible for cloud computing resource allocation.
A Case of Collusion: A Study of the Interface Between Ad Libraries and their Apps
Venue: arXiv cs.CR 2013
Year: 2013

A growing concern with advertisement libraries on Android is their ability to exfiltrate personal information from their host applications. While previous work has looked at the libraries' abilities to measure private information on their own, advertising libraries also include APIs through which a host application can deliberately leak private information about the user. This study considers a corpus of 114,000 apps. We reconstruct the APIs for 103 ad libraries used in the corpus, and study how the privacy leaking APIs from the top 20 ad libraries are used by the applications. Notably, we have found that app popularity correlates with privacy leakage; the marginal increase in advertising revenue, multiplied over a larger user base, seems to incentivize these app vendors to violate their users' privacy.
Finding Optimal Strategies in a Multi-Period Multi-Leader-Follower Stackelberg Game Using an Evolutionary Algorithm
Venue: arXiv cs.GT 2013
Year: 2013

Stackelberg games are a classic example of bilevel optimization problems, which are often encountered in game theory and economics. These are complex problems with a hierarchical structure, where one optimization task is nested within the other. Despite a number of studies on handling bilevel optimization problems, these problems still remain a challenging territory, and existing methodologies are able to handle only simple problems with few variables under assumptions of continuity and differentiability. In this paper, we consider a special case of a multi-period multi-leader-follower Stackelberg competition model with non-linear cost and demand functions and discrete production variables. The model has potential applications, for instance in aircraft manufacturing industry, which is an oligopoly where a few giant firms enjoy a tremendous commitment power over the other smaller players. We solve cases with different number of leaders and followers, and show how the entrance or exit of a player affects the profits of the other players. In the presence of various model complexities, we use a computationally intensive nested evolutionary strategy to find an optimal solution for the model. The strategy is evaluated on a test-suite of bilevel problems, and it has been shown that the method is successful in handling difficult bilevel problems.
Wireless Energy and Information Transfer Tradeoff for Limited Feedback Multi-Antenna Systems with Energy Beamforming
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we consider a multi-antenna system where the receiver should harvest energy from the transmitter by wireless energy transfer to support its wireless information transmission. In order to maximize the harvesting energy, we propose to perform adaptive energy beamforming according to the instantaneous channel state information (CSI). To help the transmitter to obtain the CSI for energy beamforming, we further propose a win-win CSI quantization feedback strategy, so as to improve the efficiencies of both power and information transmission. The focus of this paper is on the tradeoff of wireless energy and information transfer by adjusting the transfer duration with a total duration constraint. Through revealing the relationship between transmit power, transfer duration and feedback amount, we derive two wireless energy and information transfer tradeoff schemes by maximizing an upper bound and an approximate lower bound of the average information transmission rate, respectively. Moreover, the impact of imperfect CSI at the receiver is investigated and the corresponding wireless energy and information transfer tradeoff scheme is also given. Finally, numerical results validate the effectiveness of the proposed schemes.
Learning Schemas for Unordered XML
Venue: arXiv cs.DB 2013
Year: 2013

We consider unordered XML, where the relative order among siblings is ignored, and we investigate the problem of learning schemas from examples given by the user. We focus on the schema formalisms proposed in [10]: disjunctive multiplicity schemas (DMS) and its restriction, disjunction-free multiplicity schemas (MS). A learning algorithm takes as input a set of XML documents which must satisfy the schema (i.e., positive examples) and a set of XML documents which must not satisfy the schema (i.e., negative examples), and returns a schema consistent with the examples. We investigate a learning framework inspired by Gold [18], where a learning algorithm should be sound i.e., always return a schema consistent with the examples given by the user, and complete i.e., able to produce every schema with a sufficiently rich set of examples. Additionally, the algorithm should be efficient i.e., polynomial in the size of the input. We prove that the DMS are learnable from positive examples only, but they are not learnable when we also allow negative examples. Moreover, we show that the MS are learnable in the presence of positive examples only, and also in the presence of both positive and negative examples. Furthermore, for the learnable cases, the proposed learning algorithms return minimal schemas consistent with the examples.