OpenRaiser/Intern-Atlas huggingface dataset:
Modeling and simulation of multiprocessor systems MPSoC by SystemC/TLM2
Venue: arXiv cs.AR 2014
Year: 2014

The current manufacturing technology allows the integration of a complex multiprocessor system on one piece of silicon (MPSoC for Multiprocessor System-on- Chip). One way to manage the growing complexity of these systems is to increase the level of abstraction and to address the system-level design. In this paper, we focus on the implementation in SystemC language with TLM (Transaction Level Model) to model an MPSOC platform. Our main contribution is to define a comprehensive, fast and accurate method for designing and evaluating performance for MPSoC systems. The studied MPSoC is composed of MicroBlaze microprocessors, memory, a timer, a VGA and an interrupt handler with two examples of software. This paper has two novel contributions: the first is to develop this MPSOC at CABA and TLM for ISS (Instruction Set Simulator), Native simulations and timed Programmer s View (PV+T); the second is to show that with PV+T simulations we can achieve timing fidelity with higher speeds than CABA simulations and have almost the same precision.
A case for Intranet-based 0nline portal for undergraduate Computer Science education
Venue: arXiv cs.CY 2014
Year: 2014

Our proposal for selective subjects especially those involving intensive problem-solving assignments and/or tutorials, such as Introduction to Algorithms and Data structures, Discrete Mathematics, Coding Theory, Number theory, Combinatorics and Graph Theory (CGT), Automata theory, is to supplement lectures with a moderated online forum against an intranet portal. By way of illustration we take the example of a restricted view of OEIS (http://oeis.org). The restriction can be w.r.t. sequences in OEIS that are directly relevant to say CGT. N.J.A.Sloane's OEIS is a collection of over 2,39,147 integer sequences and their properties. In particular OEIS contains definitions of many combinatorial structures, dense range of interpretations, generating functions and conjectured ones, cross references within OEIS and to outside resources, references to texts and technical articles, codes in Maple, Mathematica etc. For organizing courses such as the above mentioned, a first task is to partially create an OEIS-like instructor-moderated portal in a university intranet. During the course of lectures and tutorials students are invited to contribute to the portal and these may be augmented/approved by instructors suitably, to find a place in the portal. By this many concepts can be conveyed to the students in an interesting way with the desired results. In the arguments presented, examples related to CGT are given.
The Size of Software Projects Developed by Mexican Companies
Venue: arXiv cs.SE 2014
Year: 2014

Currently, most software projects around the world are small rather than large. Despite this, there are more methodologies, tools, frameworks, processes, and so on, for developing and managing large software projects than for small ones. Small software projects are important because they generate considerable resources. For example: apps (small mobile applications) generate around $25 billion dollars of revenue. This paper shows our findings regarding the size of the projects built by Mexican software development companies. We surveyed 107 Mexican companies and found that 92% of their developed projects are micro and small, and 8% are medium or large. In addition, according to our research, 84.1% of companies in Mexico are micro or small businesses.
Boosted Markov Networks for Activity Recognition
Venue: arXiv cs.LG 2014
Year: 2014

We explore a framework called boosted Markov networks to combine the learning capacity of boosting and the rich modeling semantics of Markov networks and applying the framework for video-based activity recognition. Importantly, we extend the framework to incorporate hidden variables. We show how the framework can be applied for both model learning and feature selection. We demonstrate that boosted Markov networks with hidden variables perform comparably with the standard maximum likelihood estimation. However, our framework is able to learn sparse models, and therefore can provide computational savings when the learned models are used for classification.
On the hopping pattern design for D2D discovery with invariant
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we focus on the hopping pattern design for device-to-device (D2D) discovery. The requirements of hopping pattern is discussed, where the impact of specific system constraints, e.g., frequency hopping, is also taken into consideration. Specifically speaking, we discover and utilize the novel feature of resource hopping, i.e., "hopping invariant" to design four new hopping patterns and analyze their performance. The hopping invariant can be used to deliver information for specific users without extra radio resources, and due to the connection between hopping invariant and resource location, receiver complexity can be significantly reduced. Furthermore, our schemes are designed to be independent of discovery frame number, which makes them more suitable to be implemented in practical systems.
Anonymizing Social Graphs via Uncertainty Semantics
Venue: arXiv cs.SI 2014
Year: 2014

Rather than anonymizing social graphs by generalizing them to super nodes/edges or adding/removing nodes and edges to satisfy given privacy parameters, recent methods exploit the semantics of uncertain graphs to achieve privacy protection of participating entities and their relationship. These techniques anonymize a deterministic graph by converting it into an uncertain form. In this paper, we propose a generalized obfuscation model based on uncertain adjacency matrices that keep expected node degrees equal to those in the unanonymized graph. We analyze two recently proposed schemes and show their fitting into the model. We also point out disadvantages in each method and present several elegant techniques to fill the gap between them. Finally, to support fair comparisons, we develop a new tradeoff quantifying framework by leveraging the concept of incorrectness in location privacy research. Experiments on large social graphs demonstrate the effectiveness of our schemes.
Racing to Learn: Statistical Inference and Learning in a Single Spiking Neuron with Adaptive Kernels
Venue: arXiv cs.NE 2014
Year: 2014

This paper describes the Synapto-dendritic Kernel Adapting Neuron (SKAN), a simple spiking neuron model that performs statistical inference and unsupervised learning of spatiotemporal spike patterns. SKAN is the first proposed neuron model to investigate the effects of dynamic synapto-dendritic kernels and demonstrate their computational power even at the single neuron scale. The rule-set defining the neuron is simple there are no complex mathematical operations such as normalization, exponentiation or even multiplication. The functionalities of SKAN emerge from the real-time interaction of simple additive and binary processes. Like a biological neuron, SKAN is robust to signal and parameter noise, and can utilize both in its operations. At the network scale neurons are locked in a race with each other with the fastest neuron to spike effectively hiding its learnt pattern from its neighbors. The robustness to noise, high speed and simple building blocks not only make SKAN an interesting neuron model in computational neuroscience, but also make it ideal for implementation in digital and analog neuromorphic systems which is demonstrated through an implementation in a Field Programmable Gate Array (FPGA).
Maximum-likelihood Soft-decision Decoding for Binary Linear Block Codes Based on Their Supercodes
Venue: arXiv cs.IT 2014
Year: 2014

Based on the notion of supercodes, we propose a two-phase maximum-likelihood soft-decision decoding (tpMLSD) algorithm for binary linear block codes in this work. The first phase applies the Viterbi algorithm backwardly to a trellis derived from the parity-check matrix of the supercode of the linear block code. Using the information retained from the first phase, the second phase employs the priority-first search algorithm to the trellis corresponding to the linear block code itself, which guarantees finding the ML decision. Simulations on Reed-Muller codes show that the proposed two-phase scheme is an order of magnitude more efficient in average decoding complexity than the recursive maximum-likelihood decoding (RMLD) [1] when the signal-to-noise ratio per information bit is 4.5 dB.
Achieving Target Equilibria in Network Routing Games without Knowing the Latency Functions
Venue: arXiv cs.GT 2014
Year: 2014

The analysis of network routing games typically assumes, right at the onset, precise and detailed information about the latency functions. Such information may, however, be unavailable or difficult to obtain. Moreover, one is often primarily interested in enforcing a desired target flow as the equilibrium by suitably influencing player behavior in the routing game. We ask whether one can achieve target flows as equilibria without knowing the underlying latency functions. Our main result gives a crisp positive answer to this question. We show that, under fairly general settings, one can efficiently compute edge tolls that induce a given target multicommodity flow in a nonatomic routing game using a polynomial number of queries to an oracle that takes candidate tolls as input and returns the resulting equilibrium flow. This result is obtained via a novel application of the ellipsoid method. Our algorithm extends easily to many other settings, such as (i) when certain edges cannot be tolled or there is an upper bound on the total toll paid by a user, and (ii) general nonatomic congestion games. We obtain tighter bounds on the query complexity for series-parallel networks, and single-commodity routing games with linear latency functions, and complement these with a query-complexity lower bound. We also obtain strong positive results for Stackelberg routing to achieve target equilibria in series-parallel graphs. Our results build upon various new techniques that we develop pertaining to the computation of, and connections between, different notions of approximate equilibrium; properties of multicommodity flows and tolls in series-parallel graphs; and sensitivity of equilibrium flow with respect to tolls. Our results demonstrate that one can indeed circumvent the potentially-onerous task of modeling latency functions, and yet obtain meaningful results for the underlying routing game.
Cryptographically Enforced Control Flow Integrity
Venue: arXiv cs.CR 2014
Year: 2014

Recent Pwn2Own competitions have demonstrated the continued effectiveness of control hijacking attacks despite deployed countermeasures including stack canaries and ASLR. A powerful defense called Control flow Integrity (CFI) offers a principled approach to preventing such attacks. However, prior CFI implementations use static analysis and must limit protection to remain practical. These limitations have enabled attacks against all known CFI systems, as demonstrated in recent work. This paper presents a cryptographic approach to control flow integrity (CCFI) that is both fine-grain and practical: using message authentication codes (MAC) to protect control flow elements such as return addresses, function pointers, and vtable pointers. MACs on these elements prevent even powerful attackers with random read/write access to memory from tampering with program control flow. We implemented CCFI in Clang/LLVM, taking advantage of recently available cryptographic CPU instructions. We evaluate our system on several large software packages (including nginx, Apache and memcache) as well as all their dependencies. The cost of protection ranges from a 3-18% decrease in request rate.
Interactive Channel Capacity Revisited
Venue: arXiv cs.DS 2014
Year: 2014

We provide the first capacity approaching coding schemes that robustly simulate any interactive protocol over an adversarial channel that corrupts any $ε$ fraction of the transmitted symbols. Our coding schemes achieve a communication rate of $1 - O(\sqrt{ε\log \log 1/ε})$ over any adversarial channel. This can be improved to $1 - O(\sqrtε)$ for random, oblivious, and computationally bounded channels, or if parties have shared randomness unknown to the channel. Surprisingly, these rates exceed the $1 - Ω(\sqrt{H(ε)}) = 1 - Ω(\sqrt{ε\log 1/ε})$ interactive channel capacity bound which [Kol and Raz; STOC'13] recently proved for random errors. We conjecture $1 - Θ(\sqrt{ε\log \log 1/ε})$ and $1 - Θ(\sqrtε)$ to be the optimal rates for their respective settings and therefore to capture the interactive channel capacity for random and adversarial errors. In addition to being very communication efficient, our randomized coding schemes have multiple other advantages. They are computationally efficient, extremely natural, and significantly simpler than prior (non-capacity approaching) schemes. In particular, our protocols do not employ any coding but allow the original protocol to be performed as-is, interspersed only by short exchanges of hash values. When hash values do not match, the parties backtrack. Our approach is, as we feel, by far the simplest and most natural explanation for why and how robust interactive communication in a noisy environment is possible.
Axiomatizing Causal Reasoning
Venue: arXiv cs.AI 2014
Year: 2014

Causal models defined in terms of a collection of equations, as defined by Pearl, are axiomatized here. Axiomatizations are provided for three successively more general classes of causal models: (1) the class of recursive theories (those without feedback), (2) the class of theories where the solutions to the equations are unique, (3) arbitrary theories (where the equations may not have solutions and, if they do, they are not necessarily unique). It is shown that to reason about causality in the most general third class, we must extend the language used by Galles and Pearl. In addition, the complexity of the decision procedures is examined for all the languages and classes of models considered.
A Logic for Reasoning about Upper Probabilities
Venue: arXiv cs.AI 2014
Year: 2014

We present a propositional logic to reason about the uncertainty of events, where the uncertainty is modeled by a set of probability measures assigning an interval of probability to each event. We give a sound and complete axiomatization for the logic, and show that the satisfiability problem is NP-complete, no harder than satisfiability for propositional logic.
Updating with incomplete observations
Venue: arXiv cs.AI 2014
Year: 2014

Currently, there is renewed interest in the problem, raised by Shafer in 1985, of updating probabilities when observations are incomplete (or set-valued). This is a fundamental problem, and of particular interest for Bayesian networks. Recently, Grunwald and Halpern have shown that commonly used updating strategies fail here, except under very special assumptions. We propose a new rule for updating probabilities with incomplete observations. Our approach is deliberately conservative: we make no or weak assumptions about the so-called incompleteness mechanism that produces incomplete observations. We model our ignorance about this mechanism by a vacuous lower prevision, a tool from the theory of imprecise probabilities, and we derive a new updating rule using coherence arguments. In general, our rule produces lower posterior probabilities, as well as partially determinate decisions. This is a logical consequence of the ignorance about the incompleteness mechanism. We show how the new rule can properly address the apparent paradox in the 'Monty Hall' puzzle. In addition, we apply it to the classification of new evidence in Bayesian networks constructed using expert knowledge. We provide an exact algorithm for this task with linear-time complexity, also for multiply connected nets.
Science vs Conspiracy: collective narratives in the age of (mis)information
Venue: arXiv cs.SI 2014
Year: 2014

The large availability of user provided contents on online social media facilitates people aggregation around common interests, worldviews and narratives. However, in spite of the enthusiastic rhetoric about the so called {\em wisdom of crowds}, unsubstantiated rumors -- as alternative explanation to main stream versions of complex phenomena -- find on the Web a natural medium for their dissemination. In this work we study, on a sample of 1.2 million of individuals, how information related to very distinct narratives -- i.e. main stream scientific and alternative news -- are consumed on Facebook. Through a thorough quantitative analysis, we show that distinct communities with similar information consumption patterns emerge around distinctive narratives. Moreover, consumers of alternative news (mainly conspiracy theories) result to be more focused on their contents, while scientific news consumers are more prone to comment on alternative news. We conclude our analysis testing the response of this social system to 4709 troll information -- i.e. parodistic imitation of alternative and conspiracy theories. We find that, despite the false and satirical vein of news, usual consumers of conspiracy news are the most prone to interact with them.
Database Queries that Explain their Work
Venue: arXiv cs.PL 2014
Year: 2014

Provenance for database queries or scientific workflows is often motivated as providing explanation, increasing understanding of the underlying data sources and processes used to compute the query, and reproducibility, the capability to recompute the results on different inputs, possibly specialized to a part of the output. Many provenance systems claim to provide such capabilities; however, most lack formal definitions or guarantees of these properties, while others provide formal guarantees only for relatively limited classes of changes. Building on recent work on provenance traces and slicing for functional programming languages, we introduce a detailed tracing model of provenance for multiset-valued Nested Relational Calculus, define trace slicing algorithms that extract subtraces needed to explain or recompute specific parts of the output, and define query slicing and differencing techniques that support explanation. We state and prove correctness properties for these techniques and present a proof-of-concept implementation in Haskell.
Low-rank SIFT: An Affine Invariant Feature for Place Recognition
Venue: arXiv cs.CV 2014
Year: 2014

In this paper, we present a novel affine-invariant feature based on SIFT, leveraging the regular appearance of man-made objects. The feature achieves full affine invariance without needing to simulate over affine parameter space. Low-rank SIFT, as we name the feature, is based on our observation that local tilt, which are caused by changes of camera axis orientation, could be normalized by converting local patches to standard low-rank forms. Rotation, translation and scaling invariance could be achieved in ways similar to SIFT. As an extension of SIFT, our method seeks to add prior to solve the ill-posed affine parameter estimation problem and normalizes them directly, and is applicable to objects with regular structures. Furthermore, owing to recent breakthrough in convex optimization, such parameter could be computed efficiently. We will demonstrate its effectiveness in place recognition as our major application. As extra contributions, we also describe our pipeline of constructing geotagged building database from the ground up, as well as an efficient scheme for automatic feature selection.
Cluster-level tuning of a shallow water equation solver on the Intel MIC architecture
Venue: arXiv cs.MS 2014
Year: 2014

The paper demonstrates the optimization of the execution environment of a hybrid OpenMP+MPI computational fluid dynamics code (shallow water equation solver) on a cluster enabled with Intel Xeon Phi coprocessors. The discussion includes: (1) Controlling the number and affinity of OpenMP threads to optimize access to memory bandwidth; (2) Tuning the inter-operation of OpenMP and MPI to partition the problem for better data locality; (3) Ordering the MPI ranks in a way that directs some of the traffic into faster communication channels; (4) Using efficient peer-to-peer communication between Xeon Phi coprocessors based on the InfiniBand fabric. With tuning, the application has 90% percent efficiency of parallel scaling up to 8 Intel Xeon Phi coprocessors in 2 compute nodes. For larger problems, scalability is even better, because of the greater computation to communication ratio. However, problems of that size do not fit in the memory of one coprocessor. The performance of the solver on one Intel Xeon Phi coprocessor 7120P exceeds the performance on a dual-socket Intel Xeon E5-2697 v2 CPU by a factor of 1.6x. In a 2-node cluster with 4 coprocessors per compute node, the MIC architecture yields 5.8x more performance than the CPUs. Only one line of legacy Fortran code had to be changed in order to achieve the reported performance on the MIC architecture (not counting changes to the command-line interface). The methodology discussed in this paper is directly applicable to other bandwidth-bound stencil algorithms utilizing a hybrid OpenMP+MPI approach.
A Report of a Significant Error On a Frequently Used Pseudo Random Number Generator
Venue: arXiv cs.MS 2014
Year: 2014

Emergence of stochastic simulations as an extensively used computational tool for scientific purposes intensified the need for more accurate ways of generating sufficiently long sequences of uncorrelated random numbers. Even though several different methods have been proposed for this end, deterministic algorithms known as pseudo-random number generators (PRNGs) emerged to be the most widely used tool as a replicable, portable and easy to use method to generate such random number sequences. Here, we introduce a simple Poisson process whose simulation gives systematic errors when the very commonly used random number generator of the GNU C Library (Glibc) is utilised. The PRNG of Glibc is an additive lagged Fibonacci generator, the family of such PRNGs are accepted as relatively safe among other PRNGs. The systematic errors indicate complex correlation relations among random numbers which requires a further explanation.
Using Learned Predictions as Feedback to Improve Control and Communication with an Artificial Limb: Preliminary Findings
Venue: arXiv cs.AI 2014
Year: 2014

Many people suffer from the loss of a limb. Learning to get by without an arm or hand can be very challenging, and existing prostheses do not yet fulfil the needs of individuals with amputations. One promising solution is to provide greater communication between a prosthesis and its user. Towards this end, we present a simple machine learning interface to supplement the control of a robotic limb with feedback to the user about what the limb will be experiencing in the near future. A real-time prediction learner was implemented to predict impact-related electrical load experienced by a robot limb; the learning system's predictions were then communicated to the device's user to aid in their interactions with a workspace. We tested this system with five able-bodied subjects. Each subject manipulated the robot arm while receiving different forms of vibrotactile feedback regarding the arm's contact with its workspace. Our trials showed that communicable predictions could be learned quickly during human control of the robot arm. Using these predictions as a basis for feedback led to a statistically significant improvement in task performance when compared to purely reactive feedback from the device. Our study therefore contributes initial evidence that prediction learning and machine intelligence can benefit not just control, but also feedback from an artificial limb. We expect that a greater level of acceptance and ownership can be achieved if the prosthesis itself takes an active role in transmitting learned knowledge about its state and its situation of use.