OpenRaiser/Intern-Atlas huggingface dataset:
Credal Classification based on AODE and compression coefficients
Venue: arXiv cs.LG 2012
Year: 2012

Bayesian model averaging (BMA) is an approach to average over alternative models; yet, it usually gets excessively concentrated around the single most probable model, therefore achieving only sub-optimal classification performance. The compression-based approach (Boulle, 2007) overcomes this problem, averaging over the different models by applying a logarithmic smoothing over the models' posterior probabilities. This approach has shown excellent performances when applied to ensembles of naive Bayes classifiers. AODE is another ensemble of models with high performance (Webb, 2005), based on a collection of non-naive classifiers (called SPODE) whose probabilistic predictions are aggregated by simple arithmetic mean. Aggregating the SPODEs via BMA rather than by arithmetic mean deteriorates the performance; instead, we aggregate the SPODEs via the compression coefficients and we show that the resulting classifier obtains a slight but consistent improvement over AODE. However, an important issue in any Bayesian ensemble of models is the arbitrariness in the choice of the prior over the models. We address this problem by the paradigm of credal classification, namely by substituting the unique prior with a set of priors. Credal classifier automatically recognize the prior-dependent instances, namely the instances whose most probable class varies, when different priors are considered; in these cases, credal classifiers remain reliable by returning a set of classes rather than a single class. We thus develop the credal version of both the BMA-based and the compression-based ensemble of SPODEs, substituting the single prior over the models by a set of priors. Experiments show that both credal classifiers provide higher classification reliability than their determinate counterparts; moreover the compression-based credal classifier compares favorably to previous credal classifiers.
Constructive Discrepancy Minimization by Walking on The Edges
Venue: arXiv cs.DS 2012
Year: 2012

Minimizing the discrepancy of a set system is a fundamental problem in combinatorics. One of the cornerstones in this area is the celebrated six standard deviations result of Spencer (AMS 1985): In any system of n sets in a universe of size n, there always exists a coloring which achieves discrepancy 6\sqrt{n}. The original proof of Spencer was existential in nature, and did not give an efficient algorithm to find such a coloring. Recently, a breakthrough work of Bansal (FOCS 2010) gave an efficient algorithm which finds such a coloring. His algorithm was based on an SDP relaxation of the discrepancy problem and a clever rounding procedure. In this work we give a new randomized algorithm to find a coloring as in Spencer's result based on a restricted random walk we call "Edge-Walk". Our algorithm and its analysis use only basic linear algebra and is "truly" constructive in that it does not appeal to the existential arguments, giving a new proof of Spencer's theorem and the partial coloring lemma.
Performance Analysis of Adaptive Physical Layer Network Coding for Wireless Two-way Relaying
Venue: arXiv cs.IT 2012
Year: 2012

The analysis of modulation schemes for the physical layer network-coded two way relaying scenario is presented which employs two phases: Multiple access (MA) phase and Broadcast (BC) phase. It was shown by Koike-Akino et. al. that adaptively changing the network coding map used at the relay according to the channel conditions greatly reduces the impact of multiple access interference which occurs at the relay during the MA phase. Depending on the signal set used at the end nodes, deep fades occur for a finite number of channel fade states referred as the singular fade states. The singular fade states fall into the following two classes: The ones which are caused due to channel outage and whose harmful effect cannot be mitigated by adaptive network coding are referred as the \textit{non-removable singular fade states}. The ones which occur due to the choice of the signal set and whose harmful effects can be removed by a proper choice of the adaptive network coding map are referred as the \textit{removable} singular fade states. In this paper, we derive an upper bound on the average end-to-end Symbol Error Rate (SER), with and without adaptive network coding at the relay, for a Rician fading scenario. It is shown that without adaptive network coding, at high Signal to Noise Ratio (SNR), the contribution to the end-to-end SER comes from the following error events which fall as $\text{SNR}^{-1}$: the error events associated with the removable singular fade states, the error events associated with the non-removable singular fade states and the error event during the BC phase. In contrast, for the adaptive network coding scheme, the error events associated with the removable singular fade states contributing to the average end-to-end SER fall as $\text{SNR}^{-2}$ and as a result the adaptive network coding scheme provides a coding gain over the case when adaptive network coding is not used.
An Independent Validation of Vulnerability Discovery Models
Venue: arXiv cs.CR 2012
Year: 2012

Having a precise vulnerability discovery model (VDM) would provide a useful quantitative insight to assess software security. Thus far, several models have been proposed with some evidence supporting their goodness-of-fit. In this work we describe an independent validation of the applicability of six existing VDMs in seventeen releases of the three popular browsers Firefox, Google Chrome and Internet Explorer. We have collected five different kinds of data sets based on different definitions of a vulnerability. We introduce two quantitative metrics, goodness-of-fit entropy and goodness-of-fit quality, to analyze the impact of vulnerability data sets to the stability as well as quality of VDMs in the software life cycles. The experiment result shows that the "confirmed-by-vendors' advisories" data sets apparently yields more stable and better results for VDMs. And the performance of the s-shape logistic model (AML) seems to be superior performance in overall. Meanwhile, Anderson thermodynamic model (AT) is indeed not suitable for modeling the vulnerability discovery process. This means that the discovery process of vulnerabilities and normal bugs are different because the interests of people in finding security vulnerabilities are more than finding normal programming bugs.
The Kernel Quantum Probabilities (KQP) Library
Venue: arXiv cs.MS 2012
Year: 2012

In this document, we show how the different quantities necessary to compute kernel quantum probabilities can be computed. This document form the basis of the implementation of the Kernel Quantum Probability (KQP) open source project
Randomized Gossip Algorithm with Unreliable Communication
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we study an asynchronous randomized gossip algorithm under unreliable communication. At each instance, two nodes are selected to meet with a given probability. When nodes meet, two unreliable communication links are established with communication in each direction succeeding with a time-varying probability. It is shown that two particularly interesting cases arise when these communication processes are either perfectly dependent or independent. Necessary and sufficient conditions on the success probability sequence are proposed to ensure almost sure consensus or $ε$-consensus. Weak connectivity is required when the communication is perfectly dependent, while double connectivity is required when the communication is independent. Moreover, it is proven that with odd number of nodes, average preserving turns from almost forever (with probability one for all initial conditions) for perfectly dependent communication, to almost never (with probability zero for almost all initial conditions) for the independent case. This average preserving property does not hold true for general number of nodes. These results indicate the fundamental role the node interactions have in randomized gossip algorithms.
MDCC: Multi-Data Center Consistency
Venue: arXiv cs.DB 2012
Year: 2012

Replicating data across multiple data centers not only allows moving the data closer to the user and, thus, reduces latency for applications, but also increases the availability in the event of a data center failure. Therefore, it is not surprising that companies like Google, Yahoo, and Netflix already replicate user data across geographically different regions. However, replication across data centers is expensive. Inter-data center network delays are in the hundreds of milliseconds and vary significantly. Synchronous wide-area replication is therefore considered to be unfeasible with strong consistency and current solutions either settle for asynchronous replication which implies the risk of losing data in the event of failures, restrict consistency to small partitions, or give up consistency entirely. With MDCC (Multi-Data Center Consistency), we describe the first optimistic commit protocol, that does not require a master or partitioning, and is strongly consistent at a cost similar to eventually consistent protocols. MDCC can commit transactions in a single round-trip across data centers in the normal operational case. We further propose a new programming model which empowers the application developer to handle longer and unpredictable latencies caused by inter-data center communication. Our evaluation using the TPC-W benchmark with MDCC deployed across 5 geographically diverse data centers shows that MDCC is able to achieve throughput and latency similar to eventually consistent quorum protocols and that MDCC is able to sustain a data center outage without a significant impact on response times while guaranteeing strong consistency.
Asynchrony from Synchrony
Venue: arXiv cs.DC 2012
Year: 2012

We consider synchronous dynamic networks which like radio networks may have asymmetric communication links, and are affected by communication rather than processor failures. In this paper we investigate the minimal message survivability in a per round basis that allows for the minimal global cooperation, i.e., allows to solve any task that is wait-free read-write solvable. The paper completely characterizes this survivability requirement. Message survivability is formalized by considering adversaries that have a limited power to remove messages in a round. Removal of a message on a link in one direction does not necessarily imply the removal of the message on that link in the other direction. Surprisingly there exist a single strongest adversary which solves any wait-free read/write task. Any different adversary that solves any wait-free read/write task is weaker, and any stronger adversary will not solve any wait-free read/write task. ABD \cite{ABD} who considered processor failure, arrived at an adversary that is $n/2$ resilient, consequently can solve tasks, such as $n/2$-set-consensus, which are not read/write wait-free solvable. With message adversaries, we arrive at an adversary which has exactly the read-write wait-free power. Furthermore, this adversary allows for a considerably simpler (simplest that we know of) proof that the protocol complex of any read/write wait-free task is a subdivided simplex, finally making this proof accessible for students with no algebraic-topology prerequisites, and alternatively dispensing with the assumption that the Immediate Snapshot complex is a subdivided simplex.
Dynamic PageRank using Evolving Teleportation
Venue: arXiv cs.SI 2012
Year: 2012

The importance of nodes in a network constantly fluctuates based on changes in the network structure as well as changes in external interest. We propose an evolving teleportation adaptation of the PageRank method to capture how changes in external interest influence the importance of a node. This framework seamlessly generalizes PageRank because the importance of a node will converge to the PageRank values if the external influence stops changing. We demonstrate the effectiveness of the evolving teleportation on the Wikipedia graph and the Twitter social network. The external interest is given by the number of hourly visitors to each page and the number of monthly tweets for each user.
Classical and quantum satisfiability
Venue: arXiv cs.CC 2012
Year: 2012

We present the linear algebraic definition of QSAT and propose a direct logical characterization of such a definition. We then prove that this logical version of QSAT is not an extension of classical satisfiability problem (SAT). This shows that QSAT does not allow a direct comparison between the complexity classes NP and QMA, for which SAT and QSAT are respectively complete.
Circle separability queries in logarithmic time
Venue: arXiv cs.CG 2012
Year: 2012

Let $P$ be a set of $n$ points in the plane. In this paper we study a new variant of the circular separability problem in which a point set $P$ is preprocessed so that one can quickly answer queries of the following form: Given a geometric object $Q$, report the minimum circle containing $P$ and exluding $Q$. Our data structure can be constructed in $O(n\log n)$ time using O(n) space, and can be used to answer the query when $Q$ is either a circle or a convex $m$-gon in $O(\log n)$ or $O(\log n + \log m)$ time, respectively.
Performance Optimization of Multiple Interconnected Heterogeneous Sensor Networks via Collaborative Information Sharing
Venue: arXiv cs.NI 2012
Year: 2012

Interconnecting multiple sensor networks is a relatively new research field which has emerged in the Wireless Sensor Network domain. Wireless Sensor Networks (WSNs) have typically been seen as logically separate, and few works have considered interconnection and interaction between them. Interconnecting multiple heterogeneous sensor networks therefore opens up a new field besides more traditional research on, e.g., routing, self organization, or MAC layer development. Up to now, some approaches have been proposed for interconnecting multiple sensor networks with goals like information sharing or monitoring multiple sensor networks. In this paper, we propose to utilize inter-WSN communication to enable Collaborative Performance Optimization, i.e., our approach aims to optimize the performance of individual WSNs by taking into account measured information from others. The parameters to be optimized are energy consumption on the one hand and sensing quality on the other.
Locally Best Invariant Test for Multiple Primary User Spectrum Sensing
Venue: arXiv cs.IT 2012
Year: 2012

We consider multi-antenna cooperative spectrum sensing in cognitive radio networks, when there may be multiple primary users. A noise-uncertainty-free detector that is optimal in the low signal to noise ratio regime is analyzed in such a scenario. Specifically, we derive the exact moments of the test statistics involved, which lead to simple and accurate analytical formulae for the false alarm probability and the decision threshold. Simulations are provided to examine the accuracy of the derived results, and to compare with other detectors in realistic sensing scenarios.
Querying Schemas With Access Restrictions
Venue: arXiv cs.DB 2012
Year: 2012

We study verification of systems whose transitions consist of accesses to a Web-based data-source. An access is a lookup on a relation within a relational database, fixing values for a set of positions in the relation. For example, a transition can represent access to a Web form, where the user is restricted to filling in values for a particular set of fields. We look at verifying properties of a schema describing the possible accesses of such a system. We present a language where one can describe the properties of an access path, and also specify additional restrictions on accesses that are enforced by the schema. Our main property language, AccLTL, is based on a first-order extension of linear-time temporal logic, interpreting access paths as sequences of relational structures. We also present a lower-level automaton model, Aautomata, which AccLTL specifications can compile into. We show that AccLTL and A-automata can express static analysis problems related to "querying with limited access patterns" that have been studied in the database literature in the past, such as whether an access is relevant to answering a query, and whether two queries are equivalent in the accessible data they can return. We prove decidability and complexity results for several restrictions and variants of AccLTL, and explain which properties of paths can be expressed in each restriction.
Analysis of Test Efficiency during Software Development Process
Venue: arXiv cs.SE 2012
Year: 2012

One of the prerequisites of any organization is an unvarying sustainability in the dynamic and competitive industrial environment. Development of high quality software is therefore an inevitable constraint of any software industry. Defect management being one of the highly influencing factors for the production of high quality software, it is obligatory for the software organizations to orient them towards effective defect management. Since, the time of software evolution, testing is deemed a promising technique of defect management in all IT industries. This paper provides an empirical investigation of several projects through a case study comprising of four software companies having various production capabilities. The aim of this investigation is to analyze the efficiency of test team during software development process. The study indicates very low-test efficiency at requirements analysis phase and even lesser test efficiency at design phase of software development. Subsequently, the study calls for a strong need to improve testing approaches using techniques such as dynamic testing of design solutions in lieu of static testing of design document. Dynamic testing techniques enhance the ability of detection and elimination of design flaws right at the inception phase and thereby reduce the cost and time of rework. It further improves productivity, quality and sustainability of software industry.
Global preferential consistency for the topological sorting-based maximal spanning tree problem
Venue: arXiv cs.AI 2012
Year: 2012

We introduce a new type of fully computable problems, for DSS dedicated to maximal spanning tree problems, based on deduction and choice: preferential consistency problems. To show its interest, we describe a new compact representation of preferences specific to spanning trees, identifying an efficient maximal spanning tree sub-problem. Next, we compare this problem with the Pareto-based multiobjective one. And at last, we propose an efficient algorithm solving the associated preferential consistency problem.
A Novel Method on ISO 27001 Reviews: ISMS Compliance Readiness Level Measurement
Venue: arXiv cs.CR 2012
Year: 2012

Security is a hot issue to be discussed, ranging from business activities, correspondence, banking and financial activities; it requires prudence and high precision. Since information security has a very important role in supporting activities of the organization, we need a standard or benchmark which regulates governance over information security. The main objective of this paper is to implement a novel practical approach framework to the development of information security management system (ISMS) assessment and monitoring software, called by I-SolFramework. System / software is expected to assist stakeholders in assessing the level of their ISO27001 compliance readiness, the software could help stakeholders understood security control or called by compliance parameters, being shorter, more structured, high precision and measured forecasting.
Power Allocation over Two Identical Gilbert-Elliott Channels
Venue: arXiv cs.IT 2012
Year: 2012

We study the problem of power allocation over two identical Gilbert-Elliot communication channels. Our goal is to maximize the expected discounted number of bits transmitted over an infinite time horizon. This is achieved by choosing among three possible strategies: (1) betting on channel 1 by allocating all the power to this channel, which results in high data rate if channel 1 happens to be in good state, and zero bits transmitted if channel 1 is in bad state (even if channel 2 is in good state) (2) betting on channel 2 by allocating all the power to the second channel, and (3) a balanced strategy whereby each channel is allocated half the total power, with the effect that each channel can transmit a low data rate if it is in good state. We assume that each channel's state is only revealed upon transmission of data on that channel. We model this problem as a partially observable Markov decision processes (MDP), and derive key threshold properties of the optimal policy. Further, we show that by formulating and solving a relevant linear program the thresholds can be determined numerically when system parameters are known.
The Relationship Between Separation Logic and Implicit Dynamic Frames
Venue: arXiv cs.PL 2012
Year: 2012

Separation logic is a concise method for specifying programs that manipulate dynamically allocated storage. Partially inspired by separation logic, Implicit Dynamic Frames has recently been proposed, aiming at first-order tool support. In this paper, we precisely connect the semantics of these two logics. We define a logic whose syntax subsumes both that of a standard separation logic, and that of implicit dynamic frames as sub-syntaxes. We define a total heap semantics for our logic, and, for the separation logic subsyntax, prove it equivalent the standard partial heaps model. In order to define a semantics which works uniformly for both subsyntaxes, we define the novel concept of a minimal state extension, which provides a different (but equivalent) definition of the semantics of separation logic implication and magic wand connectives, while also giving a suitable semantics for these connectives in implicit dynamic frames. We show that our resulting semantics agrees with the existing definition of weakest pre-condition semantics for the implicit dynamic frames fragment. Finally, we show that we can encode the separation logic fragment of our logic into the implicit dynamic frames fragment, preserving semantics. For the connectives typically supported by tools, this shows that separation logic can be faithfully encoded in a first-order automatic verification tool (Chalice).
Fundamental Limits of Cooperation
Venue: arXiv cs.IT 2012
Year: 2012

Cooperation is viewed as a key ingredient for interference management in wireless systems. This paper shows that cooperation has fundamental limitations. The main result is that even full cooperation between transmitters cannot in general change an interference-limited network to a noise-limited network. The key idea is that there exists a spectral efficiency upper bound that is independent of the transmit power. First, a spectral efficiency upper bound is established for systems that rely on pilot-assisted channel estimation; in this framework, cooperation is shown to be possible only within clusters of limited size, which are subject to out-of-cluster interference whose power scales with that of the in-cluster signals. Second, an upper bound is also shown to exist when cooperation is through noncoherent communication; thus, the spectral efficiency limitation is not a by-product of the reliance on pilot-assisted channel estimation. Consequently, existing literature that routinely assumes the high-power spectral efficiency scales with the log of the transmit power provides only a partial characterization. The complete characterization proposed in this paper subdivides the high-power regime into a degrees-of-freedom regime, where the scaling with the log of the transmit power holds approximately, and a saturation regime, where the spectral efficiency hits a ceiling that is independent of the power. Using a cellular system as an example, it is demonstrated that the spectral efficiency saturates at power levels of operational relevance.