OpenRaiser/Intern-Atlas huggingface dataset:
Using carry-truncated addition to analyze add-rotate-xor hash algorithms
Venue: arXiv cs.DM 2013
Year: 2013

We introduce a truncated addition operation on pairs of N-bit binary numbers that interpolates between ordinary addition mod 2^N and bitwise addition in (Z/2Z)^N. We use truncated addition to analyze hash functions that are built from the bit operations add, rotate, and xor, such as Blake, Skein, and Cubehash. Any ARX algorithm can be approximated by replacing ordinary addition with truncated addition, and we define a metric on such algorithms which we call the {\bf sensitivity}. This metric measures the smallest approximation agreeing with the full algorithm a statistically useful portion of the time (we use 0.1%). Because truncated addition greatly reduces the complexity of the non-linear operation in ARX algorithms, the approximated algorithms are more susceptible to both collision and pre-image attacks, and we outline a potential collision attack explicitly. We particularize some of these observations to the Skein hash function.
Probability-constrained Power Optimization for Multiuser MISO Systems with Imperfect CSI: A Bernstein Approximation Approach
Venue: arXiv cs.IT 2013
Year: 2013

We consider power allocations in downlink cellular wireless systems where the basestations are equipped with multiple transmit antennas and the mobile users are equipped with single receive antennas. Such systems can be modeled as multiuser MISO systems. We assume that the multi-antenna transmitters employ some fixed beamformers to transmit data, and the objective is to optimize the power allocation for different users to satisfy certain QoS constraints, with imperfect transmitter-side channel state information (CSI). Specifically, for MISO interference channels, we consider the transmit power minimization problem and the max-min SINR problem. For MISO broadcast channels, we consider the MSE-constrained transmit power minimization problem. All these problems are formulated as probability-constrained optimization problems. We make use of the Bernstein approximation to conservatively transform the probabilistic constraints into deterministic ones, and consequently convert the original stochastic optimization problems into convex optimization problems. However, the transformed problems cannot be straightforwardly solved using standard solver, since one of the constraints is itself an optimization problem. We employ the long-step logarithmic barrier cutting plane (LLBCP) algorithm to overcome difficulty. Extensive simulation results are provided to demonstrate the effectiveness of the proposed method, and the performance advantage over some existing methods.
NetLogo Implementation of an Evacuation Scenario
Venue: arXiv cs.MA 2013
Year: 2013

The problem of evacuating crowded closed spaces, such as discotheques, public exhibition pavilions or concert houses, has become increasingly important and gained attention both from practitioners and from public authorities. A simulation implementation using NetLogo, an agent-based simulation framework that permits the quickly creation of prototypes, is presented. Our aim is to prove that this model developed using NetLogo, albeit simple can be expanded and adapted for fire safety experts test various scenarios and validate the outcome of their design. Some preliminary experiments are carried out, whose results are presented, validated and discussed so as to illustrate their efficiency. Finally, we draw some conclusions and point out ways in which this work can be further extended.
MJ no more: Using Concurrent Wikipedia Edit Spikes with Social Network Plausibility Checks for Breaking News Detection
Venue: arXiv cs.SI 2013
Year: 2013

We have developed an application called Wikipedia Live Monitor that monitors article edits on different language versions of Wikipedia, as they happen in realtime. Wikipedia articles in different languages are highly interlinked. For example, the English article en:2013_Russian_meteor_event on the topic of the February 15 meteoroid that exploded over the region of Chelyabinsk Oblast, Russia, is interlinked with the Russian article on the same topic. As we monitor multiple language versions of Wikipedia in parallel, we can exploit this fact to detect concurrent edit spikes of Wikipedia articles covering the same topics, both in only one, and in different languages. We treat such concurrent edit spikes as signals for potential breaking news events, whose plausibility we then check with full-text cross-language searches on multiple social networks. Unlike the reverse approach of monitoring social networks first, and potentially checking plausibility on Wikipedia second, the approach proposed in this paper has the advantage of being less prone to false-positive alerts, while being equally sensitive to true-positive events, however, at only a fraction of the processing cost.
Security and Privacy Issues in Cloud Computing
Venue: arXiv cs.CR 2013
Year: 2013

Cloud computing transforms the way information technology (IT) is consumed and managed, promising improved cost efficiencies, accelerated innovation, faster time-to-market, and the ability to scale applications on demand (Leighton, 2009). According to Gartner, while the hype grew exponentially during 2008 and continued since, it is clear that there is a major shift towards the cloud computing model and that the benefits may be substantial (Gartner Hype-Cycle, 2012). However, as the shape of the cloud computing is emerging and developing rapidly both conceptually and in reality, the legal/contractual, economic, service quality, interoperability, security and privacy issues still pose significant challenges. In this chapter, we describe various service and deployment models of cloud computing and identify major challenges. In particular, we discuss three critical challenges: regulatory, security and privacy issues in cloud computing. Some solutions to mitigate these challenges are also proposed along with a brief presentation on the future trends in cloud computing deployment.
Maximum Edge-Disjoint Paths in $k$-sums of Graphs
Venue: arXiv cs.DM 2013
Year: 2013

We consider the approximability of the maximum edge-disjoint paths problem (MEDP) in undirected graphs, and in particular, the integrality gap of the natural multicommodity flow based relaxation for it. The integrality gap is known to be $Ω(\sqrt{n})$ even for planar graphs due to a simple topological obstruction and a major focus, following earlier work, has been understanding the gap if some constant congestion is allowed. In this context, it is natural to ask for which classes of graphs does a constant-factor constant-congestion property hold. It is easy to deduce that for given constant bounds on the approximation and congestion, the class of "nice" graphs is nor-closed. Is the converse true? Does every proper minor-closed family of graphs exhibit a constant factor, constant congestion bound relative to the LP relaxation? We conjecture that the answer is yes. One stumbling block has been that such bounds were not known for bounded treewidth graphs (or even treewidth 3). In this paper we give a polytime algorithm which takes a fractional routing solution in a graph of bounded treewidth and is able to integrally route a constant fraction of the LP solution's value. Note that we do not incur any edge congestion. Previously this was not known even for series parallel graphs which have treewidth 2. The algorithm is based on a more general argument that applies to $k$-sums of graphs in some graph family, as long as the graph family has a constant factor, constant congestion bound. We then use this to show that such bounds hold for the class of $k$-sums of bounded genus graphs.
Web Maps and Their Algebra
Venue: arXiv cs.DL 2013
Year: 2013

A map is an abstract visual representation of a region, taken from a given space, usually designed for final human consumption. Traditional cartography focuses on the mapping of Euclidean spaces by using some distance metric. In this paper we aim at mapping the Web space by leveraging its relational nature. We introduce a general mathematical framework for maps and an algebra and discuss the feasibility of maps suitable for interpretation not only by humans but also by machines.
Rational Univariate Representations of Bivariate Systems and Applications
Venue: arXiv cs.SC 2013
Year: 2013

We address the problem of solving systems of two bivariate polynomials of total degree at most $d$ with integer coefficients of maximum bitsize $τ$. It is known that a linear separating form, that is a linear combination of the variables that takes different values at distinct solutions of the system, can be computed in $\sOB(d^{8}+d^7τ)$ bit operations (where $O_B$ refers to bit complexities and $\sO$ to complexities where polylogarithmic factors are omitted) and we focus here on the computation of a Rational Univariate Representation (RUR) given a linear separating form. We present an algorithm for computing a RUR with worst-case bit complexity in $\sOB(d^7+d^6τ)$ and bound the bitsize of its coefficients by $\sO(d^2+dτ)$. We show in addition that isolating boxes of the solutions of the system can be computed from the RUR with $\sOB(d^{8}+d^7τ)$ bit operations. Finally, we show how a RUR can be used to evaluate the sign of a bivariate polynomial (of degree at most $d$ and bitsize at most $τ$) at one real solution of the system in $\sOB(d^{8}+d^7τ)$ bit operations and at all the $Θ(d^2)$ {real} solutions in only $O(d)$ times that for one solution.
Using evolutionary design to interactively sketch car silhouettes and stimulate designer's creativity
Venue: arXiv cs.NE 2013
Year: 2013

An Interactive Genetic Algorithm is proposed to progressively sketch the desired side-view of a car profile. It adopts a Fourier decomposition of a 2D profile as the genotype, and proposes a cross-over mechanism. In addition, a formula function of two genes' discrepancies is fitted to the perceived dissimilarity between two car profiles. This similarity index is intensively used, throughout a series of user tests, to highlight the added value of the IGA compared to a systematic car shape exploration, to prove its ability to create superior satisfactory designs and to stimulate designer's creativity. These tests have involved six designers with a design goal defined by a semantic attribute. The results reveal that if "friendly" is diversely interpreted in terms of car shapes, "sportive" denotes a very conventional representation which may be a limitation for shape renewal.
Estimating Confusions in the ASR Channel for Improved Topic-based Language Model Adaptation
Venue: arXiv cs.CL 2013
Year: 2013

Human language is a combination of elemental languages/domains/styles that change across and sometimes within discourses. Language models, which play a crucial role in speech recognizers and machine translation systems, are particularly sensitive to such changes, unless some form of adaptation takes place. One approach to speech language model adaptation is self-training, in which a language model's parameters are tuned based on automatically transcribed audio. However, transcription errors can misguide self-training, particularly in challenging settings such as conversational speech. In this work, we propose a model that considers the confusions (errors) of the ASR channel. By modeling the likely confusions in the ASR output instead of using just the 1-best, we improve self-training efficacy by obtaining a more reliable reference transcription estimate. We demonstrate improved topic-based language modeling adaptation results over both 1-best and lattice self-training using our ASR channel confusion estimates on telephone conversations.
Kernelet: High-Throughput GPU Kernel Executions with Dynamic Slicing and Scheduling
Venue: arXiv cs.DC 2013
Year: 2013

Graphics processors, or GPUs, have recently been widely used as accelerators in the shared environments such as clusters and clouds. In such shared environments, many kernels are submitted to GPUs from different users, and throughput is an important metric for performance and total ownership cost. Despite the recently improved runtime support for concurrent GPU kernel executions, the GPU can be severely underutilized, resulting in suboptimal throughput. In this paper, we propose Kernelet, a runtime system with dynamic slicing and scheduling techniques to improve the throughput of concurrent kernel executions on the GPU. With slicing, Kernelet divides a GPU kernel into multiple sub-kernels (namely slices). Each slice has tunable occupancy to allow co-scheduling with other slices and to fully utilize the GPU resources. We develop a novel and effective Markov chain based performance model to guide the scheduling decision. Our experimental results demonstrate up to 31.1% and 23.4% performance improvement on NVIDIA Tesla C2050 and GTX680 GPUs, respectively.
Algorithm for factoring some RSA and Rabin moduli
Venue: arXiv cs.CR 2013
Year: 2013

In this paper we present a new efficient algorithm for factoring the RSA and the Rabin moduli in the particular case when the difference between their two prime factors is bounded. As an extension, we also give some theoretical results on factoring integers.
Link Scheduling for Multiple Multicast Sessions in Distributed Wireless Networks
Venue: arXiv cs.NI 2013
Year: 2013

In this letter we investigate link scheduling algorithms for throughput maximization in multicast wireless networks. According to our system model, each source node transmits to a multicast group that resides one hop away. We adopt the physical interference model to reflect the aggregate signal to interference and noise ratio (SINR) at each node of the multicast group. We present an ILP formulation of the aforementioned problem. The basic feature of the problem formulation is that it decomposes the single multicast session into the corresponding point-to-point links. The rationale is that a solution algorithm has more flexibility regarding the scheduling options for individual nodes. The extended MILP problem that also considers power control is solved with LP relaxation. Performance results for both the ILP and MILP problems are obtained for different traffic loads and different number of nodes per multicast group.
Achieving Efficient Strong Scaling with PETSc using Hybrid MPI/OpenMP Optimisation
Venue: arXiv cs.DC 2013
Year: 2013

The increasing number of processing elements and decreas- ing memory to core ratio in modern high-performance platforms makes efficient strong scaling a key requirement for numerical algorithms. In order to achieve efficient scalability on massively parallel systems scientific software must evolve across the entire stack to exploit the multiple levels of parallelism exposed in modern architectures. In this paper we demonstrate the use of hybrid MPI/OpenMP parallelisation to optimise parallel sparse matrix-vector multiplication in PETSc, a widely used scientific library for the scalable solution of partial differential equations. Using large matrices generated by Fluidity, an open source CFD application code which uses PETSc as its linear solver engine, we evaluate the effect of explicit communication overlap using task-based parallelism and show how to further improve performance by explicitly load balancing threads within MPI processes. We demonstrate a significant speedup over the pure-MPI mode and efficient strong scaling of sparse matrix-vector multiplication on Fujitsu PRIMEHPC FX10 and Cray XE6 systems.
Basic Properties and Stability of Fractional-Order Reset Control Systems
Venue: arXiv cs.SY 2013
Year: 2013

Reset control is introduced to overcome limitations of linear control. A reset controller includes a linear controller which resets some of states to zero when their input is zero or certain non-zero values. This paper studies the application of the fractional-order Clegg integrator (FCI) and compares its performance with both the commonly used first order reset element (FORE) and traditional Clegg integrator (CI). Moreover, stability of reset control systems is generalized for the fractional-order case. Two examples are given to illustrate the application of the stability theorem.
A simulation Method for Network Performability Estimation using Heuristically-computed Pathsets and Cutsets
Venue: arXiv cs.NI 2013
Year: 2013

Consider a set of terminal nodes K that belong to a network whose nodes are connected by links that fail independently with known probabilities. We introduce a method for estimating any performability measure that depends on the hop distance between terminal nodes. It generalises previously introduced Monte Carlo methods for estimation of the K-reliability of networks with variance reduction compared to crude Monte Carlo. They are based on using sets of edges named d-pathsets and d-cutsets for reducing the variance of the estimator. These sets of edges, considered as a priori known in previous literature, heaviliy affect the attained performance; we hereby introduce and compare a family of heuristics for their selection. Numerical examples are presented, showing the significant efficiency improvements that can be obtained by chaining the edge set selection heuristics to the proposed Monte Carlo sampling plan.
Lower bounds for k-distance approximation
Venue: arXiv cs.CG 2013
Year: 2013

Consider a set P of N random points on the unit sphere of dimension $d-1$, and the symmetrized set S = P union (-P). The halving polyhedron of S is defined as the convex hull of the set of centroids of N distinct points in S. We prove that after appropriate rescaling this halving polyhedron is Hausdorff close to the unit ball with high probability, as soon as the number of points grows like $Omega(d log(d))$. From this result, we deduce probabilistic lower bounds on the complexity of approximations of the distance to the empirical measure on the point set by distance-like functions.
Entropy and Belief Networks
Venue: arXiv cs.AI 2013
Year: 2013

The product expansion of conditional probabilities for belief nets is not maximum entropy. This appears to deny a desirable kind of assurance for the model. However, a kind of guarantee that is almost as strong as maximum entropy can be derived. Surprisingly, a variant model also exhibits the guarantee, and for many cases obtains a higher performance score than the product expansion.
Parallelizing Probabilistic Inference: Some Early Explorations
Venue: arXiv cs.AI 2013
Year: 2013

We report on an experimental investigation into opportunities for parallelism in beliefnet inference. Specifically, we report on a study performed of the available parallelism, on hypercube style machines, of a set of randomly generated belief nets, using factoring (SPI) style inference algorithms. Our results indicate that substantial speedup is available, but that it is available only through parallelization of individual conformal product operations, and depends critically on finding an appropriate factoring. We find negligible opportunity for parallelism at the topological, or clustering tree, level.
Bayesian Meta-Reasoning: Determining Model Adequacy from Within a Small World
Venue: arXiv cs.AI 2013
Year: 2013

This paper presents a Bayesian framework for assessing the adequacy of a model without the necessity of explicitly enumerating a specific alternate model. A test statistic is developed for tracking the performance of the model across repeated problem instances. Asymptotic methods are used to derive an approximate distribution for the test statistic. When the model is rejected, the individual components of the test statistic can be used to guide search for an alternate model.
Possibilistic Constraint Satisfaction Problems or "How to handle soft constraints?"
Venue: arXiv cs.AI 2013
Year: 2013

Many AI synthesis problems such as planning or scheduling may be modelized as constraint satisfaction problems (CSP). A CSP is typically defined as the problem of finding any consistent labeling for a fixed set of variables satisfying all given constraints between these variables. However, for many real tasks such as job-shop scheduling, time-table scheduling, design?, all these constraints have not the same significance and have not to be necessarily satisfied. A first distinction can be made between hard constraints, which every solution should satisfy and soft constraints, whose satisfaction has not to be certain. In this paper, we formalize the notion of possibilistic constraint satisfaction problems that allows the modeling of uncertainly satisfied constraints. We use a possibility distribution over labelings to represent respective possibilities of each labeling. Necessity-valued constraints allow a simple expression of the respective certainty degrees of each constraint. The main advantage of our approach is its integration in the CSP technical framework. Most classical techniques, such as Backtracking (BT), arcconsistency enforcing (AC) or Forward Checking have been extended to handle possibilistics CSP and are effectively implemented. The utility of our approach is demonstrated on a simple design problem.
Decision Making Using Probabilistic Inference Methods
Venue: arXiv cs.AI 2013
Year: 2013

The analysis of decision making under uncertainty is closely related to the analysis of probabilistic inference. Indeed, much of the research into efficient methods for probabilistic inference in expert systems has been motivated by the fundamental normative arguments of decision theory. In this paper we show how the developments underlying those efficient methods can be applied immediately to decision problems. In addition to general approaches which need know nothing about the actual probabilistic inference method, we suggest some simple modifications to the clustering family of algorithms in order to efficiently incorporate decision making capabilities.
The Nature of the Unnormalized Beliefs Encountered in the Transferable Belief Model
Venue: arXiv cs.AI 2013
Year: 2013

Within the transferable belief model, positive basic belief masses can be allocated to the empty set, leading to unnormalized belief functions. The nature of these unnormalized beliefs is analyzed.
Intuitions about Ordered Beliefs Leading to Probabilistic Models
Venue: arXiv cs.AI 2013
Year: 2013

The general use of subjective probabilities to model belief has been justified using many axiomatic schemes. For example, ?consistent betting behavior' arguments are well-known. To those not already convinced of the unique fitness and generality of probability models, such justifications are often unconvincing. The present paper explores another rationale for probability models. ?Qualitative probability,' which is known to provide stringent constraints on belief representation schemes, is derived from five simple assumptions about relationships among beliefs. While counterparts of familiar rationality concepts such as transitivity, dominance, and consistency are used, the betting context is avoided. The gap between qualitative probability and probability proper can be bridged by any of several additional assumptions. The discussion here relies on results common in the recent AI literature, introducing a sixth simple assumption. The narrative emphasizes models based on unique complete orderings, but the rationale extends easily to motivate set-valued representations of partial orderings as well.