OpenRaiser/Intern-Atlas huggingface dataset:
Flow-based reputation with uncertainty: Evidence-Based Subjective Logic
Venue: arXiv cs.DC 2015
Year: 2015

The concept of reputation is widely used as a measure of trustworthiness based on ratings from members in a community. The adoption of reputation systems, however, relies on their ability to capture the actual trustworthiness of a target. Several reputation models for aggregating trust information have been proposed in the literature. The choice of model has an impact on the reliability of the aggregated trust information as well as on the procedure used to compute reputations. Two prominent models are flow-based reputation (e.g., EigenTrust, PageRank) and Subjective Logic based reputation. Flow-based models provide an automated method to aggregate trust information, but they are not able to express the level of uncertainty in the information. In contrast, Subjective Logic extends probabilistic models with an explicit notion of uncertainty, but the calculation of reputation depends on the structure of the trust network and often requires information to be discarded. These are severe drawbacks. In this work, we observe that the `opinion discounting' operation in Subjective Logic has a number of basic problems. We resolve these problems by providing a new discounting operator that describes the flow of evidence from one party to another. The adoption of our discounting rule results in a consistent Subjective Logic algebra that is entirely based on the handling of evidence. We show that the new algebra enables the construction of an automated reputation assessment procedure for arbitrary trust networks, where the calculation no longer depends on the structure of the network, and does not need to throw away any information. Thus, we obtain the best of both worlds: flow-based reputation and consistent handling of uncertainties.
A reclaimer scheduling problem arising in coal stockyard management
Venue: arXiv cs.DS 2015
Year: 2015

We study a number of variants of an abstract scheduling problem inspired by the scheduling of reclaimers in the stockyard of a coal export terminal. We analyze the complexity of each of the variants, providing complexity proofs for some and polynomial algorithms for others. For one, especially interesting variant, we also develop a constant factor approximation algorithm.
Diffuse Reflection Radius in a Simple Polygon
Venue: arXiv cs.CG 2015
Year: 2015

It is shown that every simple polygon in general position with $n$ walls can be illuminated from a single point light source $s$ after at most $\lfloor (n-2)/4\rfloor$ diffuse reflections, and this bound is the best possible. A point $s$ with this property can be computed in $O(n\log n)$ time. It is also shown that the minimum number of diffuse reflections needed to illuminate a given simple polygon from a single point can be approximated up to an additive constant in polynomial time.
Source-specific routing
Venue: arXiv cs.NI 2015
Year: 2015

Source-specific routing (not to be confused with source routing) is a routing technique where routing decisions depend on both the source and the destination address of a packet. Source-specific routing solves some difficult problems related to multihoming, notably in edge networks, and is therefore a useful addition to the multihoming toolbox. In this paper, we describe the semantics of source-specific packet forwarding, and describe the design and implementation of a source-specific extension to the Babel routing protocol as well as its implementation - to our knowledge, the first complete implementation of a source-specific dynamic routing protocol, including a disambiguation algorithm that makes our implementation work over widely available networking APIs. We further discuss interoperability between ordinary next-hop and source-specific dynamic routing protocols. Our implementation has seen a moderate amount of deployment, notably as a testbed for the IETF Homenet working group.
The Homeostasis Protocol: Avoiding Transaction Coordination Through Program Analysis
Venue: arXiv cs.DB 2015
Year: 2015

Datastores today rely on distribution and replication to achieve improved performance and fault-tolerance. But correctness of many applications depends on strong consistency properties - something that can impose substantial overheads, since it requires coordinating the behavior of multiple nodes. This paper describes a new approach to achieving strong consistency in distributed systems while minimizing communication between nodes. The key insight is to allow the state of the system to be inconsistent during execution, as long as this inconsistency is bounded and does not affect transaction correctness. In contrast to previous work, our approach uses program analysis to extract semantic information about permissible levels of inconsistency and is fully automated. We then employ a novel homeostasis protocol to allow sites to operate independently, without communicating, as long as any inconsistency is governed by appropriate treaties between the nodes. We discuss mechanisms for optimizing treaties based on workload characteristics to minimize communication, as well as a prototype implementation and experiments that demonstrate the benefits of our approach on common transactional benchmarks.
Behavior, Organization, Substance: Three Gestalts of General Systems Theory
Venue: arXiv cs.OH 2015
Year: 2015

The term gestalt, when used in the context of general systems theory, assumes the value of "systemic touchstone", namely a figure of reference used to categorize the properties or qualities of a set of systems. Typical gestalts used in biology are those based on anatomical or physiological characteristics, which correspond respectively to architectural and organizational design choices in natural and artificial systems. In this paper we discuss three gestalts of general systems theory: behavior, organization, and substance, which refer respectively to the works of Wiener, Boulding, and Leibniz. Our major focus here is the system introduced by the latter. Through a discussion of some of the elements of the Leibnitian System, and by means of several novel interpretations of those elements in terms of today's computer science, we highlight the debt that contemporary research still has with this Giant among the giant scholars of the past.
Heap Abstractions for Static Analysis
Venue: arXiv cs.PL 2015
Year: 2015

Heap data is potentially unbounded and seemingly arbitrary. As a consequence, unlike stack and static memory, heap memory cannot be abstracted directly in terms of a fixed set of source variable names appearing in the program being analysed. This makes it an interesting topic of study and there is an abundance of literature employing heap abstractions. Although most studies have addressed similar concerns, their formulations and formalisms often seem dissimilar and some times even unrelated. Thus, the insights gained in one description of heap abstraction may not directly carry over to some other description. This survey is a result of our quest for a unifying theme in the existing descriptions of heap abstractions. In particular, our interest lies in the abstractions and not in the algorithms that construct them. In our search of a unified theme, we view a heap abstraction as consisting of two features: a heap model to represent the heap memory and a summarization technique for bounding the heap representation. We classify the models as storeless, store based, and hybrid. We describe various summarization techniques based on k-limiting, allocation sites, patterns, variables, other generic instrumentation predicates, and higher-order logics. This approach allows us to compare the insights of a large number of seemingly dissimilar heap abstractions and also paves way for creating new abstractions by mix-and-match of models and summarization techniques.
Matrix-F5 algorithms over finite-precision complete discrete valuation fields
Venue: arXiv cs.SC 2015
Year: 2015

Let $(f\_1,\dots, f\_s) \in \mathbb{Q}\_p [X\_1,\dots, X\_n]^s$ be a sequence of homogeneous polynomials with $p$-adic coefficients. Such system may happen, for example, in arithmetic geometry. Yet, since $\mathbb{Q}\_p$ is not an effective field, classical algorithm does not apply.We provide a definition for an approximate Gr{ö}bner basis with respect to a monomial order $w.$ We design a strategy to compute such a basis, when precision is enough and under the assumption that the input sequence is regular and the ideals $\langle f\_1,\dots,f\_i \rangle$ are weakly-$w$-ideals. The conjecture of Moreno-Socias states that for the grevlex ordering, such sequences are generic.Two variants of that strategy are available, depending on whether one lean more on precision or time-complexity. For the analysis of these algorithms, we study the loss of precision of the Gauss row-echelon algorithm, and apply it to an adapted Matrix-F5 algorithm. Numerical examples are provided.Moreover, the fact that under such hypotheses, Gr{ö}bner bases can be computed stably has many applications. Firstly, the mapping sending $(f\_1,\dots,f\_s)$ to the reduced Gr{ö}bner basis of the ideal they span is differentiable, and its differential can be given explicitly. Secondly, these hypotheses allows to perform lifting on the Grobner bases, from $\mathbb{Z}/p^k \mathbb{Z}$ to $\mathbb{Z}/p^{k+k'} \mathbb{Z}$ or $\mathbb{Z}.$ Finally, asking for the same hypotheses on the highest-degree homogeneous components of the entry polynomials allows to extend our strategy to the affine case.
Group Mutual Exclusion in Linear Time and Space
Venue: arXiv cs.DC 2015
Year: 2015

We present two algorithms for the Group Mutual Exclusion (GME) Problem that satisfy the properties of Mutual Exclusion, Starvation Freedom, Bounded Exit, Concurrent Entry and First Come First Served. Both our algorithms use only simple read and write instructions, have O(N) Shared Space complexity and O(N) Remote Memory Reference (RMR) complexity in the Cache Coherency (CC) model. Our first algorithm is developed by generalizing the well-known Lamport's Bakery Algorithm for the classical mutual exclusion problem, while preserving its simplicity and elegance. However, it uses unbounded shared registers. Our second algorithm uses only bounded registers and is developed by generalizing Taubenfeld's Black and White Bakery Algorithm to solve the classical mutual exclusion problem using only bounded shared registers. We show that contrary to common perception our algorithms are the first to achieve these properties with these combination of complexities.
Belief-Rule-Based Expert Systems for Evaluation of E- Government: A Case Study
Venue: arXiv cs.AI 2015
Year: 2015

Little knowledge exists on the impact and results associated with e-government projects in many specific use domains. Therefore it is necessary to evaluate the efficiency and effectiveness of e-government systems. Since the development of e-government is a continuous process of improvement, it requires continuous evaluation of the overall e-government system as well as evaluation of its various dimensions such as determinants, characteristics and results. E-government development is often complex with multiple stakeholders, large user bases and complex goals. Consequently, even experts have difficulties in evaluating these systems, especially in an integrated and comprehensive way as well as on an aggregate level. Expert systems are a candidate solution to evaluate such complex e-government systems. However, it is difficult for expert systems to cope with uncertain evaluation data that are vague, inconsistent, highly subjective or in other ways challenging to formalize. This paper presents an approach that can handle uncertainty in e-government evaluation: The combination of Belief Rule Base (BRB) knowledge representation and Evidential Reasoning (ES). This approach is illustrated with a concrete prototype, known as Belief Rule Based Expert System (BRBES) and put to use in the local e-government of Bangladesh. The results have been compared with a recently developed method of evaluating e-Government, and it is shown that the results of BRBES are more accurate and reliable. BRBES can be used to identify the factors that need to be improved to achieve the overall aim of an e-government project. In addition, various "what if" scenarios can be generated and developers and managers can get a forecast of the outcomes. In this way, the system can be used to facilitate decision making processes under uncertainty.
Optimal Design of Energy-Efficient Multi-User MIMO Systems: Is Massive MIMO the Answer?
Venue: arXiv cs.IT 2015
Year: 2015

Assume that a multi-user multiple-input multiple-output (MIMO) system is designed from scratch to uniformly cover a given area with maximal energy efficiency (EE). What are the optimal number of antennas, active users, and transmit power? The aim of this paper is to answer this fundamental question. We consider jointly the uplink and downlink with different processing schemes at the base station and propose a new realistic power consumption model that reveals how the above parameters affect the EE. Closed-form expressions for the EE-optimal value of each parameter, when the other two are fixed, are provided for zero-forcing (ZF) processing in single-cell scenarios. These expressions prove how the parameters interact. For example, in sharp contrast to common belief, the transmit power is found to increase (not to decrease) with the number of antennas. This implies that energy-efficient systems can operate in high signal-to-noise ratio regimes in which interference-suppressing signal processing is mandatory. Numerical and analytical results show that the maximal EE is achieved by a massive MIMO setup wherein hundreds of antennas are deployed to serve a relatively large number of users using ZF processing. The numerical results show the same behavior under imperfect channel state information and in symmetric multi-cell scenarios.
Design and Analysis of a Greedy Pursuit for Distributed Compressed Sensing
Venue: arXiv cs.IT 2015
Year: 2015

We consider a distributed compressed sensing scenario where many sensors measure correlated sparse signals and the sensors are connected through a network. Correlation between sparse signals is modeled by a partial common support-set. For such a scenario, the main objective of this paper is to develop a greedy pursuit algorithm. We develop a distributed parallel pursuit (DIPP) algorithm based on exchange of information about estimated support-sets at sensors. The exchange of information helps to improve estimation of the partial common support-set, that in turn helps to gradually improve estimation of support-sets in all sensors, leading to a better quality reconstruction performance. We provide restricted isometry property (RIP) based theoretical analysis on the algorithm's convergence and reconstruction performance. Under certain theoretical requirements on the quality of information exchange over network and RIP parameters of sensor nodes, we show that the DIPP algorithm converges to a performance level that depends on a scaled additive measurement noise power (convergence in theory) where the scaling coefficient is a function of RIP parameters and information processing quality parameters. Using simulations, we show practical reconstruction performance of DIPP vis-a-vis amount of undersampling, signal-to-measurement-noise ratios and network-connectivity conditions.
Interacting Hopf Algebras
Venue: arXiv cs.LO 2015
Year: 2015

We introduce the theory IH of interacting Hopf algebras, parametrised over a principal ideal domain R. The axioms of IH are derived using Lack's approach to composing PROPs: they feature two Hopf algebra and two Frobenius algebra structures on four different monoid-comonoid pairs. This construction is instrumental in showing that IH is isomorphic to the PROP of linear relations (i.e. subspaces) over the field of fractions of R.
Solvers for $\mathcal{O} (N)$ Electronic Structure in the Strong Scaling Limit
Venue: arXiv cs.NA 2015
Year: 2015

We present a hybrid OpenMP/Charm++ framework for solving the $\mathcal{O} (N)$ Self-Consistent-Field eigenvalue problem with parallelism in the strong scaling regime, $P\gg{N}$, where $P$ is the number of cores, and $N$ a measure of system size, i.e. the number of matrix rows/columns, basis functions, atoms, molecules, etc. This result is achieved with a nested approach to Spectral Projection and the Sparse Approximate Matrix Multiply [Bock and Challacombe, SIAM J.~Sci.~Comput. 35 C72, 2013], and involves a recursive, task-parallel algorithm, often employed by generalized $N$-Body solvers, to occlusion and culling of negligible products in the case of matrices with decay. Employing classic technologies associated with generalized $N$-Body solvers, including over-decomposition, recursive task parallelism, orderings that preserve locality, and persistence-based load balancing, we obtain scaling beyond hundreds of cores per molecule for small water clusters ([H${}_2$O]${}_N$, $N \in \{ 30, 90, 150 \}$, $P/N \approx \{ 819, 273, 164 \}$) and find support for an increasingly strong scalability with increasing system size $N$.
A Derivative-Free Trust Region Framework for Variational Data Assimilation
Venue: arXiv cs.NA 2015
Year: 2015

This study develops a hybrid ensemble-variational approach for solving data assimilation problems. The method, called TR-4D-EnKF, is based on a trust region framework and consists of three computational steps. First an ensemble of model runs is propagated forward in time and snapshots of the state are stored. Next, a sequence of basis vectors is built and a low-dimensional representation of the data assimilation system is obtained by projecting the model state onto the space spanned by the ensemble deviations from the mean. Finally, the low-dimensional optimization problem is solved in the reduced-space using a trust region approach; the size of the trust region is updated according to the relative decrease of the reduced order surrogate cost function. The analysis state is projected back onto the full space, and the process is repeated with the current analysis serving as a new background. A heuristic approach based on the trust region size is proposed in order to adjust the background error statistics from one iteration to the next. Experimental simulations are carried out using the Lorenz and the quasi-geostrophic models. The results show that TR-4D-EnKF is an efficient computational approach, and is more accurate than the current state of the art 4D-EnKF implementations such as the POD-4D-EnKF and the Iterative Subspace Minimization methods.
Auto-encoders: reconstruction versus compression
Venue: arXiv cs.NE 2015
Year: 2015

We discuss the similarities and differences between training an auto-encoder to minimize the reconstruction error, and training the same auto-encoder to compress the data via a generative model. Minimizing a codelength for the data using an auto-encoder is equivalent to minimizing the reconstruction error plus some correcting terms which have an interpretation as either a denoising or contractive property of the decoding function. These terms are related but not identical to those used in denoising or contractive auto-encoders [Vincent et al. 2010, Rifai et al. 2011]. In particular, the codelength viewpoint fully determines an optimal noise level for the denoising criterion.
piCholesky: Polynomial Interpolation of Multiple Cholesky Factors for Efficient Approximate Cross-Validation
Venue: arXiv cs.LG 2015
Year: 2015

The dominant cost in solving least-square problems using Newton's method is often that of factorizing the Hessian matrix over multiple values of the regularization parameter ($λ$). We propose an efficient way to interpolate the Cholesky factors of the Hessian matrix computed over a small set of $λ$ values. This approximation enables us to optimally minimize the hold-out error while incurring only a fraction of the cost compared to exact cross-validation. We provide a formal error bound for our approximation scheme and present solutions to a set of key implementation challenges that allow our approach to maximally exploit the compute power of modern architectures. We present a thorough empirical analysis over multiple datasets to show the effectiveness of our approach.
Multi-dimensional Virtual Values and Second-degree Price Discrimination
Venue: arXiv cs.GT 2015
Year: 2015

We consider a multi-dimensional screening problem of selling a product with multiple quality levels and design virtual value functions to derive conditions that imply optimality of only selling highest quality. A challenge of designing virtual values for multi-dimensional agents is that a mechanism that pointwise optimizes virtual values resulting from a general application of integration by parts is not incentive compatible, and no general methodology is known for selecting the right paths for integration by parts. We resolve this issue by first uniquely solving for paths that satisfy certain necessary conditions that the pointwise optimality of the mechanism imposes on virtual values, and then identifying distributions that ensure the resulting virtual surplus is indeed pointwise optimized by the mechanism. Our method of solving for virtual values is general, and as a second application we use it to derive conditions of optimality for selling only the grand bundle of items to an agent with additive preferences.
Estimating the Accuracy of the Return on Investment (ROI) Performance Evaluations
Venue: arXiv cs.CE 2015
Year: 2015

Return on Investment (ROI) is one of the most popular performance measurement and evaluation metrics. ROI analysis (when applied correctly) is a powerful tool in comparing solutions and making informed decisions on the acquisitions of information systems. The ROI sensitivity to error is a natural thought, and common sense suggests that ROI evaluations cannot be absolutely accurate. However, literature review revealed that in most publications and analyst firms reports, this issue is just overlooked. On the one hand, the results of the ROI calculations are implied to be produced with a mathematical rigor, possibility of errors is not mentioned and amount of errors is not estimated. On the contrary, another approach claims ROI evaluations to be absolutely inaccurate because, in view of their authors, future benefits (especially, intangible) cannot be estimated within any reasonable boundaries. The purpose of this study is to provide a systematic research of the accuracy of the ROI evaluations in the context of the information systems implementations. The main contribution of the study is that this is the first systematic effort to evaluate ROI accuracy. Analytical expressions have been derived for estimating errors of the ROI evaluations. Results of the Monte Carlo simulation will help practitioners in making informed decisions based on explicitly stated factors influencing the ROI uncertainties. The results of this research are intended for researchers in information systems, technology solutions and business management, and also for information specialists, project managers, program managers, technology directors, and information systems evaluators. Most results are applicable to ROI evaluations in a wider subject area.
On the sum of the L1 influences of bounded functions
Venue: arXiv cs.CC 2015
Year: 2015

Let $f\colon \{-1,1\}^n \to [-1,1]$ have degree $d$ as a multilinear polynomial. It is well-known that the total influence of $f$ is at most $d$. Aaronson and Ambainis asked whether the total $L_1$ influence of $f$ can also be bounded as a function of $d$. Bačkurs and Bavarian answered this question in the affirmative, providing a bound of $O(d^3)$ for general functions and $O(d^2)$ for homogeneous functions. We improve on their results by providing a bound of $d^2$ for general functions and $O(d\log d)$ for homogeneous functions. In addition, we prove a bound of $d/(2 π)+o(d)$ for monotone functions, and provide a matching example.