OpenRaiser/Intern-Atlas huggingface dataset:
Highly Scalable Multiplication for Distributed Sparse Multivariate Polynomials on Many-core Systems
Venue: arXiv cs.SC 2013
Year: 2013

We present a highly scalable algorithm for multiplying sparse multivariate polynomials represented in a distributed format. This algo- rithm targets not only the shared memory multicore computers, but also computers clusters or specialized hardware attached to a host computer, such as graphics processing units or many-core coprocessors. The scal- ability on the large number of cores is ensured by the lacks of synchro- nizations, locks and false-sharing during the main parallel step.
Constructive Interference in Linear Precoding Systems: Power Allocation and User Selection
Venue: arXiv cs.IT 2013
Year: 2013

The exploitation of interference in a constructive manner has recently been proposed for the downlink of multiuser, multi-antenna transmitters. This novel linear precoding technique, herein referred to as constructive interference zero forcing (CIZF) precoding, has exhibited substantial gains over conventional approaches; the concept is to cancel, on a symbol-by-symbol basis, only the interfering users that do not add to the intended signal power. In this paper, the power allocation problem towards maximizing the performance of a CIZF system with respect to some metric (throughput or fairness) is investigated. What is more, it is shown that the performance of the novel precoding scheme can be further boosted by choosing some of the constructive multiuser interference terms in the precoder design. Finally, motivated by the significant effect of user selection on conventional, zero forcing (ZF) precoding, the problem of user selection for the novel precoding method is tackled. A new iterative, low complexity algorithm for user selection in CIZF is developed. Simulation results are provided to display the gains of the algorithm compared to known user selection approaches.
The Illusion of Requirements in Software Development
Venue: arXiv cs.SE 2013
Year: 2013

It is widely accepted that understanding system requirements is important for software development project success. However, this paper presents two novel challenges to the requirements concept. First, where many plausible approaches to achieving a goal are evident, there may be insufficient overlap between approaches to form requirements. Second, while all plausible approaches may have sufficient overlap to state requirements, we cannot know that unless all approaches are identified and we are sure that none have been missed. This suggest that many, if not most, software projects may have too few requirements drive the design process, and that analysts may misrepresent design decisions as requirements to compensate.
Packet Relaying Control in Sensing-based Spectrum Sharing Systems
Venue: arXiv cs.NI 2013
Year: 2013

Cognitive relaying has been introduced for opportunistic spectrum access systems by which a secondary node forwards primary packets whenever the primary link faces an outage condition. For spectrum sharing systems, cognitive relaying is parametrized by an interference power constraint level imposed on the transmit power of the secondary user. For sensing-based spectrum sharing, the probability of detection is also involved in packet relaying control. This paper considers the choice of these two parameters so as to maximize the secondary nodes' throughput under certain constraints. The analysis leads to a Markov decision process using dynamic programming approach. The problem is solved using value iteration. Finally, the structural properties of the resulting optimal control are highlighted.
On Energy Efficiency and Delay Minimization in Reactive Protocols in Wireless Multi-hop Networks
Venue: arXiv cs.NI 2013
Year: 2013

In Wireless Multi-hop Networks (WMhNs), routing protocols with energy efficient and delay reduction techniques are needed to fulfill users demands. In this paper, we present Linear Programming models (LP_models) to assess and enhance reactive routing protocols. To practically examine constraints of respective LP_models over reactive protocols, we select AODV, DSR and DYMO. It is deduced from analytical simulations of LP_models in MATLAB that quick route repair reduces routing latency and optimizations of retransmission attempts results efficient energy utilization. To provide quick repair, we enhance AODV and DSR. To practically examine the efficiency of enhanced protocols in different scenarios of WMhNs, we conduct simulations using NS- 2. From simulation results, enhanced DSR and AODV achieve efficient output by optimizing routing latencies and routing load in terms of retransmission attempts.
The Total Irregularity of Graphs under Graph Operations
Venue: arXiv cs.DM 2013
Year: 2013

The total irregularity of a graph $G$ is defined as $\irr_t(G)=1/2 \sum_{u,v \in V(G)}$ $|d_G(u)-d_G(v)|$, where $d_G(u)$ denotes the degree of a vertex $u \in V(G)$. In this paper we give (sharp) upper bounds on the total irregularity of graphs under several graph operations including join, lexicographic product, Cartesian product, strong product, direct product, corona product, disjunction and symmetric difference.
Evasive Properties of Sparse Graphs and Some Linear Equations in Primes
Venue: arXiv cs.CC 2013
Year: 2013

We give an unconditional version of a conditional, on the Extended Riemann Hypothesis, result of L. Babai, A. Banerjee, R. Kulkarni and V. Naik (2010) on the evasiveness of sparse graphs.
Numerical determination of the optimal value of quantizer's segment threshold using quadratic spline functions
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, an approximation of the optimal compressor function using the quadratic spline functions has been presented. The coefficients of the quadratic spline functions are determined by minimizing the mean-square error (MSE). Based on the obtained approximative quadratic spline functions, the design for companding quantizer for Gaussian source is done. The support region of proposed companding quantizer is divided on segments of unequal size, where the optimal value of segment threshold is numerically determined depending on maximal value of the signal to quantization noise ratio (SQNR). It is shown that by the companding quantizer proposed in this paper, the SQNR that is very close to SQNR of nonlinear optimal companding quantizer is achieved.
Amalgam width of matroids
Venue: arXiv cs.DM 2013
Year: 2013

We introduce a new matroid width parameter based on the operation of matroid amalgamation, which we call amalgam-width. The parameter is linearly related to branch-width on finitely representable matroids (which is not possible for branch-width). In particular, any property expressible in the monadic second order logic can be decided in linear time for matroids with bounded amalgam-width. We also prove that the Tutte polynomial can be computed in polynomial time for matroids with bounded amalgam width.
Software Cognitive Information Measure based on Relation Between Structures
Venue: arXiv cs.SE 2013
Year: 2013

Cognitive complexity measures quantify human difficulty in understanding the source code based on cognitive informatics foundation. The discipline derives cognitive complexity on a basis of fundamental software factors i.e, inputs, outputs, and internal processing architecture. An approach to integrating Granular Computing into the new measure called Structured Cognitive Information Measure or SCIM. The proposed measure unifies and re-organizes complexity factors analogous to human cognitive process. However, according to the methodology of software and the scope of the variables, Information Complexity Number(ICN) of variables is depended on change of variable value and cognitive complexity is measured in several ways. In this paper, we define the Scope Information Complexity Number (SICN) and present the cognitive complexity based on functional decomposition of software, including theoretical validation through nine Weyuker's properties.
MIMO Communications over Multi-Mode Optical Fibers: Capacity Analysis and Input-Output Coupling Schemes
Venue: arXiv cs.IT 2013
Year: 2013

We consider multi-input multi-output (MIMO) communications over multi-mode fibers (MMFs). Current MMF standards, such as OM3 and OM4, use fibers with core radii of 50 μm, allowing hundreds of modes to propagate. Unfortunately, due to physical and computational complexity limitations, we cannot couple and detect hundreds of data streams into and out of the fiber. In order to circumvent this issue, we present input-output coupling schemes that allow the user to couple and extract a reasonable number of signals from a fiber with many modes. This approach is particularly attractive as it is scalable; i.e., the fibers do not have to be replaced every time the number of transmitters or receivers is increased, a phenomenon that is likely to happen in the near future. We present a statistical channel model that incorporates intermodal dispersion, chromatic dispersion, mode dependent losses, mode coupling, and input-output coupling. We show that the statistics of the fiber's frequency response are independent of frequency. This simplifies the computation of the average Shannon capacity of the fiber. We also provide an input-output coupling strategy that leads to an increase in the overall capacity. This strategy can be used whenever channel state information (CSI) is available at the transmitter. We show that the capacity of an Nt by Nt MIMO system over a fiber with M>>Nt modes can approach the capacity of an Nt-mode fiber with no mode-dependent losses. We finally present a statistical input-output coupling model in order to quantify the loss in capacity when CSI is not available at the transmitter. It turns out that the loss, relative to Nt-mode fibers, is minimal (less than 0.5 dB) for a wide range of signal-to-noise ratios (SNRs) and a reasonable range of MDLs.
A problem dependent analysis of SOCP algorithms in noisy compressed sensing
Venue: arXiv cs.IT 2013
Year: 2013

Under-determined systems of linear equations with sparse solutions have been the subject of an extensive research in last several years above all due to results of \cite{CRT,CanRomTao06,DonohoPol}. In this paper we will consider \emph{noisy} under-determined linear systems. In a breakthrough \cite{CanRomTao06} it was established that in \emph{noisy} systems for any linear level of under-determinedness there is a linear sparsity that can be \emph{approximately} recovered through an SOCP (second order cone programming) optimization algorithm so that the approximate solution vector is (in an $\ell_2$-norm sense) guaranteed to be no further from the sparse unknown vector than a constant times the noise. In our recent work \cite{StojnicGenSocp10} we established an alternative framework that can be used for statistical performance analysis of the SOCP algorithms. To demonstrate how the framework works we then showed in \cite{StojnicGenSocp10} how one can use it to precisely characterize the \emph{generic} (worst-case) performance of the SOCP. In this paper we present a different set of results that can be obtained through the framework of \cite{StojnicGenSocp10}. The results will relate to \emph{problem dependent} performance analysis of SOCP's. We will consider specific types of unknown sparse vectors and characterize the SOCP performance when used for recovery of such vectors. We will also show that our theoretical predictions are in a solid agreement with the results one can get through numerical simulations.
Lambda Calculus Synopsis
Venue: arXiv cs.LO 2013
Year: 2013

This text gives a rough, but linear summary covering some key definitions, notations, and propositions from Lambda Calculus: Its Syntax and Semantics, the classical monograph by Barendregt. First, we define a theory of untyped extensional lambda calculus. Then, some syntactic sugar, a system of combinatory logic, and the fixed point theorem are described. The final section introduces a topology on the set of lambda terms which is meant to explain an illusory contradiction. Namely, functions defined on the set of lambda terms are in the set of lambda terms itself, the latter being a countable set. However, the functions on the set of lambda terms appear to be continuous with respect to a topology of trees.
Graph Induced Complex on Point Data
Venue: arXiv cs.CG 2013
Year: 2013

The efficiency of extracting topological information from point data depends largely on the complex that is built on top of the data points. From a computational viewpoint, the most favored complexes for this purpose have so far been Vietoris-Rips and witness complexes. While the Vietoris-Rips complex is simple to compute and is a good vehicle for extracting topology of sampled spaces, its size is huge--particularly in high dimensions. The witness complex on the other hand enjoys a smaller size because of a subsampling, but fails to capture the topology in high dimensions unless imposed with extra structures. We investigate a complex called the {\em graph induced complex} that, to some extent, enjoys the advantages of both. It works on a subsample but still retains the power of capturing the topology as the Vietoris-Rips complex. It only needs a graph connecting the original sample points from which it builds a complex on the subsample thus taming the size considerably. We show that, using the graph induced complex one can (i) infer the one dimensional homology of a manifold from a very lean subsample, (ii) reconstruct a surface in three dimension from a sparse subsample without computing Delaunay triangulations, (iii) infer the persistent homology groups of compact sets from a sufficiently dense sample. We provide experimental evidences in support of our theory.
Synthesizing Switching Controllers for Hybrid Systems by Continuous Invariant Generation
Venue: arXiv cs.SY 2013
Year: 2013

We extend a template-based approach for synthesizing switching controllers for semi-algebraic hybrid systems, in which all expressions are polynomials. This is achieved by combining a QE (quantifier elimination)-based method for generating continuous invariants with a qualitative approach for predefining templates. Our synthesis method is relatively complete with regard to a given family of predefined templates. Using qualitative analysis, we discuss heuristics to reduce the numbers of parameters appearing in the templates. To avoid too much human interaction in choosing templates as well as the high computational complexity caused by QE, we further investigate applications of the SOS (sum-of-squares) relaxation approach and the template polyhedra approach in continuous invariant generation, which are both well supported by efficient numerical solvers.
Efficient Generation of Correctness Certificates for the Abstract Domain of Polyhedra
Venue: arXiv cs.PL 2013
Year: 2013

Polyhedra form an established abstract domain for inferring runtime properties of programs using abstract interpretation. Computations on them need to be certified for the whole static analysis results to be trusted. In this work, we look at how far we can get down the road of a posteriori verification to lower the overhead of certification of the abstract domain of polyhedra. We demonstrate methods for making the cost of inclusion certificate generation negligible. From a performance point of view, our single-representation, constraints-based implementation compares with state-of-the-art implementations.
Passages in Graphs
Venue: arXiv cs.DM 2013
Year: 2013

Directed graphs can be partitioned in so-called passages. A passage P is a set of edges such that any two edges sharing the same initial vertex or sharing the same terminal vertex are both inside $P$ or are both outside of P. Passages were first identified in the context of process mining where they are used to successfully decompose process discovery and conformance checking problems. In this article, we examine the properties of passages. We will show that passages are closed under set operators such as union, intersection and difference. Moreover, any passage is composed of so-called minimal passages. These properties can be exploited when decomposing graph-based analysis and computation problems.
A Literature Survey on Empirical Evidence in Software Engineering
Venue: arXiv cs.SE 2013
Year: 2013

Context: Software Engineering research makes use of collections of software artifacts (corpora) to derive empirical evidence from. Goal: To improve quality and reproducibility of research, we need to understand the characteristics of used corpora. Method: For that, we perform a literature survey using grounded theory. We analyze the latest proceedings of seven relevant conferences. Results: While almost all papers use corpora of some kind with the common case of collections of source code of open-source Java projects, there are no frequently used projects or corpora across all the papers. For some conferences we can detect recurrences. We discover several forms of requirements and applied tunings for corpora which indicate more specific needs of research efforts. Conclusion: Our survey feeds into a quantitative basis for discussing the current state of empirical research in software engineering, thereby enabling ultimately improvement of research quality specifically in terms of use (and reuse) of empirical evidence.
A Seamless Flow Mobility Management Architecture for Vehicular Communication Networks
Venue: arXiv cs.NI 2013
Year: 2013

Vehicular Ad Hoc Networks (VANETs) are self-organizing, self-healing networks which provide wireless communication among vehicular and roadside devices. Applications in such networks can take advantage of the use of simultaneous connections, thereby maximizing the throughput and lowering latency. In order to take advantage of all radio interfaces of the vehicle and to provide good quality of service for vehicular applications, we de- veloped a seamless flow mobility management architecture based on vehicular network application classes with network-based mobility management. Our goal is to minimize the time of flow connection exchange in order to comply with the minimum requirements of vehicular application classes, as well as to maximize their throughput. NS3 simulations were performed to analyse the behaviour of our architecture by comparing it with other three scenarios. As a result of this work, we observed that the proposed architecture presented a low handover time, with lower packet loss and lower delay.
Kolmogorov's strong law of large numbers in game-theoretic probability: Reality's side
Venue: arXiv cs.GT 2013
Year: 2013

The game-theoretic version of Kolmogorov's strong law of large numbers says that Skeptic has a strategy forcing the statement of the law in a game of prediction involving Reality, Forecaster, and Skeptic. This note describes a simple matching strategy for Reality.
Context-Dependent Similarity
Venue: arXiv cs.AI 2013
Year: 2013

Attribute weighting and differential weighting, two major mechanisms for computing context-dependent similarity or dissimilarity measures are studied and compared. A dissimilarity measure based on subset size in the context is proposed and its metrization and application are given. It is also shown that while all attribute weighting dissimilarity measures are metrics differential weighting dissimilarity measures are usually non-metric.
What is an Optimal Diagnosis?
Venue: arXiv cs.AI 2013
Year: 2013

Within diagnostic reasoning there have been a number of proposed definitions of a diagnosis, and thus of the most likely diagnosis, including most probable posterior hypothesis, most probable interpretation, most probable covering hypothesis, etc. Most of these approaches assume that the most likely diagnosis must be computed, and that a definition of what should be computed can be made a priori, independent of what the diagnosis is used for. We argue that the diagnostic problem, as currently posed, is incomplete: it does not consider how the diagnosis is to be used, or the utility associated with the treatment of the abnormalities. In this paper we analyze several well-known definitions of diagnosis, showing that the different definitions of the most likely diagnosis have different qualitative meanings, even given the same input data. We argue that the most appropriate definition of (optimal) diagnosis needs to take into account the utility of outcomes and what the diagnosis is used for.
Kutato: An Entropy-Driven System for Construction of Probabilistic Expert Systems from Databases
Venue: arXiv cs.AI 2013
Year: 2013

Kutato is a system that takes as input a database of cases and produces a belief network that captures many of the dependence relations represented by those data. This system incorporates a module for determining the entropy of a belief network and a module for constructing belief networks based on entropy calculations. Kutato constructs an initial belief network in which all variables in the database are assumed to be marginally independent. The entropy of this belief network is calculated, and that arc is added that minimizes the entropy of the resulting belief network. Conditional probabilities for an arc are obtained directly from the database. This process continues until an entropy-based threshold is reached. We have tested the system by generating databases from networks using the probabilistic logic-sampling method, and then using those databases as input to Kutato. The system consistently reproduces the original belief networks with high fidelity.
Computationally-Optimal Real-Resource Strategies
Venue: arXiv cs.AI 2013
Year: 2013

This paper focuses on managing the cost of deliberation before action. In many problems, the overall quality of the solution reflects costs incurred and resources consumed in deliberation as well as the cost and benefit of execution, when both the resource consumption in deliberation phase, and the costs in deliberation and execution are uncertain and may be described by probability distribution functions. A feasible (in terms of resource consumption) strategy that minimizes the expected total cost is termed computationally-optimal. For a situation with several independent, uninterruptible methods to solve the problem, we develop a pseudopolynomial-time algorithm to construct generate-and-test computationally optimal strategy. We show this strategy-construction problem to be NP-complete, and apply Bellman's Optimality Principle to solve it efficiently.
Ergo: A Graphical Environment for Constructing Bayesian
Venue: arXiv cs.AI 2013
Year: 2013

We describe an environment that considerably simplifies the process of generating Bayesian belief networks. The system has been implemented on readily available, inexpensive hardware, and provides clarity and high performance. We present an introduction to Bayesian belief networks, discuss algorithms for inference with these networks, and delineate the classes of problems that can be solved with this paradigm. We then describe the hardware and software that constitute the system, and illustrate Ergo's use with several example
Robust Inference Policies
Venue: arXiv cs.AI 2013
Year: 2013

A series of monte carlo studies were performed to assess the extent to which different inference procedures robustly output reasonable belief values in the context of increasing levels of judgmental imprecision. It was found that, when compared to an equal-weights linear model, the Bayesian procedures are more likely to deduce strong support for a hypothesis. But, the Bayesian procedures are also more likely to strongly support the wrong hypothesis. Bayesian techniques are more powerful, but are also more error prone.
IDEAL: A Software Package for Analysis of Influence Diagrams
Venue: arXiv cs.AI 2013
Year: 2013

IDEAL (Influence Diagram Evaluation and Analysis in Lisp) is a software environment for creation and evaluation of belief networks and influence diagrams. IDEAL is primarily a research tool and provides an implementation of many of the latest developments in belief network and influence diagram evaluation in a unified framework. This paper describes IDEAL and some lessons learned during its development.