OpenRaiser/Intern-Atlas huggingface dataset:
Computing Stable Coalitions: Approximation Algorithms for Reward Sharing
Venue: arXiv cs.GT 2015
Year: 2015

Consider a setting where selfish agents are to be assigned to coalitions or projects from a fixed set P. Each project k is characterized by a valuation function; v_k(S) is the value generated by a set S of agents working on project k. We study the following classic problem in this setting: "how should the agents divide the value that they collectively create?". One traditional approach in cooperative game theory is to study core stability with the implicit assumption that there are infinite copies of one project, and agents can partition themselves into any number of coalitions. In contrast, we consider a model with a finite number of non-identical projects; this makes computing both high-welfare solutions and core payments highly non-trivial. The main contribution of this paper is a black-box mechanism that reduces the problem of computing a near-optimal core stable solution to the purely algorithmic problem of welfare maximization; we apply this to compute an approximately core stable solution that extracts one-fourth of the optimal social welfare for the class of subadditive valuations. We also show much stronger results for several popular sub-classes: anonymous, fractionally subadditive, and submodular valuations, as well as provide new approximation algorithms for welfare maximization with anonymous functions. Finally, we establish a connection between our setting and the well-studied simultaneous auctions with item bidding; we adapt our results to compute approximate pure Nash equilibria for these auctions.
Coarse-Grain Performance Estimator for Heterogeneous Parallel Computing Architectures like Zynq All-Programmable SoC
Venue: arXiv cs.DC 2015
Year: 2015

Heterogeneous computing is emerging as a mandatory requirement for power-efficient system design. With this aim, modern heterogeneous platforms like Zynq All-Programmable SoC, that integrates ARM-based SMP and programmable logic, have been designed. However, those platforms introduce large design cycles consisting on hardware/software partitioning, decisions on granularity and number of hardware accelerators, hardware/software integration, bitstream generation, etc. This paper presents a performance parallel heterogeneous estimation for systems where hardware/software co-design and run-time heterogeneous task scheduling are key. The results show that the programmer can quickly decide, based only on her/his OmpSs (OpenMP + extensions) application, which is the co-design that achieves nearly optimal heterogeneous parallel performance, based on the methodology presented and considering only synthesis estimation results. The methodology presented reduces the programmer co-design decision from hours to minutes and shows high potential on hardware/software heterogeneous parallel performance estimation on the Zynq All-Programmable SoC.
RC3E: Provision and Management of Reconfigurable Hardware Accelerators in a Cloud Environment
Venue: arXiv cs.DC 2015
Year: 2015

Heterogeneous systems consisting of general-purpose processors and different types of hardware accelerators are becoming more and more common in HPC systems. Especially FPGAs provide a promising opportunity to improve both performance and energy efficiency of such systems. Adding FPGAs to clouds or data centers allows easy access to such reconfigurable resources. In this paper we present our cloud service models and cloud hypervisor called RC3E, which integrates virtualized FPGA-based hardware accelerators into a cloud environment. With our hardware and software framework, multiple (virtual) user designs can be executed on a single physical FPGA device. We demonstrate the performance of our approach by implementing up to four virtual user cores on a single device and present future perspectives for FPGAs in cloud-based data environments.
The maximum time of 2-neighbor bootstrap percolation: complexity results
Venue: arXiv cs.CC 2015
Year: 2015

In 2-neighborhood bootstrap percolation on a graph G, an infection spreads according to the following deterministic rule: infected vertices of G remain infected forever and in consecutive rounds healthy vertices with at least 2 already infected neighbors become infected. Percolation occurs if eventually every vertex is infected. The maximum time t(G) is the maximum number of rounds needed to eventually infect the entire vertex set. In 2013, it was proved \cite{eurocomb13} that deciding whether $t(G)\geq k$ is polynomial time solvable for k=2, but is NP-Complete for k=4 and, if the problem is restricted to bipartite graphs, it is NP-Complete for k=7. In this paper, we solve the open questions. We obtain an $O(mn^5)$-time algorithm to decide whether $t(G)\geq 3$. For bipartite graphs, we obtain an $O(mn^3)$-time algorithm to decide whether $t(G)\geq 3$, an $O(m^2n^9)$-time algorithm to decide whether $t(G)\geq 4$ and we prove that $t(G)\geq 5$ is NP-Complete.
Cyclic codes over the ring $\mathbb{F}_p[u,v] / \langle u^k,v^2,uv-vu\rangle$
Venue: arXiv cs.IT 2015
Year: 2015

Let $p$ be a prime number. In this paper, we discuss the structures of cyclic codes over the ring $ \mathbb{F}_p[u, v] / \langle u^k, v^2, uv-vu\rangle$. We find a unique set of generators for these codes. We also study the rank and the Hamming distance of these codes.
SentenceRacer: A Game with a Purpose for Image Sentence Annotation
Venue: arXiv cs.HC 2015
Year: 2015

Recently datasets that contain sentence descriptions of images have enabled models that can automatically generate image captions. However, collecting these datasets are still very expensive. Here, we present SentenceRacer, an online game that gathers and verifies descriptions of images at no cost. Similar to the game hangman, players compete to uncover words in a sentence that ultimately describes an image. SentenceRacer both generates and verifies that the sentences are accurate descriptions. We show that SentenceRacer generates annotations of higher quality than those generated on Amazon Mechanical Turk (AMT).
Regularized Kernel Recursive Least Square Algoirthm
Venue: arXiv cs.LG 2015
Year: 2015

In most adaptive signal processing applications, system linearity is assumed and adaptive linear filters are thus used. The traditional class of supervised adaptive filters rely on error-correction learning for their adaptive capability. The kernel method is a powerful nonparametric modeling tool for pattern analysis and statistical signal processing. Through a nonlinear mapping, kernel methods transform the data into a set of points in a Reproducing Kernel Hilbert Space. KRLS achieves high accuracy and has fast convergence rate in stationary scenario. However the good performance is obtained at a cost of high computation complexity. Sparsification in kernel methods is know to related to less computational complexity and memory consumption.
Transparent hardware synthesis of Java for predictable large-scale distributed systems
Venue: arXiv cs.DC 2015
Year: 2015

The JUNIPER project is developing a framework for the construction of large-scale distributed systems in which execution time bounds can be guaranteed. Part of this work involves the automatic implementation of input Java code on FPGAs, both for speed and predictability. An important focus of this work is to make the use of FPGAs transparent though runtime co-design and partial reconfiguration. Initial results show that the use of Java does not hamper hardware generation, and provides tight execution time estimates. This paper describes an overview the approach taken, and presents some preliminary results that demonstrate the promise in the technique.
Clone and graft: Testing scientific applications as they are built
Venue: arXiv cs.MS 2015
Year: 2015

This article describes our experience developing and maintaining automated tests for scientific applications. The main idea evolves around building on already existing tests by cloning and grafting. The idea is demonstrated on a minimal model problem written in Python.
Rational Chebyshev of Second Kind Collocation Method for Solving a Class of Astrophysics Problems
Venue: arXiv cs.NA 2015
Year: 2015

The Lane-Emden equation has been used to model several phenomenas in theoretical physics, mathematical physics and astrophysics such as the theory of stellar structure. This study is an attempt to utilize the collocation method with the Rational Chebyshev of Second Kind function (RSC) to solve the Lane-Emden equation over the semi-infinit interval [0; +infinity). According to well-known results and comparing with previous methods, it can be said that this method is efficient and applicable.
On ultralimits of sparse graph classes
Venue: arXiv cs.DM 2015
Year: 2015

The notion of nowhere denseness is one of the central concepts of the recently developed theory of sparse graphs. We study the properties of nowhere dense graph classes by investigating appropriate limit objects defined using the ultraproduct construction. It appears that different equivalent definitions of nowhere denseness, for example via quasi-wideness or the splitter game, correspond to natural notions for the limit objects that are conceptually simpler and allow for less technically involved reasonings.
Understanding Editing Behaviors in Multilingual Wikipedia
Venue: arXiv cs.SI 2015
Year: 2015

Multilingualism is common offline, but we have a more limited understanding of the ways multilingualism is displayed online and the roles that multilinguals play in the spread of content between speakers of different languages. We take a computational approach to studying multilingualism using one of the largest user-generated content platforms, Wikipedia. We study multilingualism by collecting and analyzing a large dataset of the content written by multilingual editors of the English, German, and Spanish editions of Wikipedia. This dataset contains over two million paragraphs edited by over 15,000 multilingual users from July 8 to August 9, 2013. We analyze these multilingual editors in terms of their engagement, interests, and language proficiency in their primary and non-primary (secondary) languages and find that the English edition of Wikipedia displays different dynamics from the Spanish and German editions. Users primarily editing the Spanish and German editions make more complex edits than users who edit these editions as a second language. In contrast, users editing the English edition as a second language make edits that are just as complex as the edits by users who primarily edit the English edition. In this way, English serves a special role bringing together content written by multilinguals from many language editions. Nonetheless, language remains a formidable hurdle to the spread of content: we find evidence for a complexity barrier whereby editors are less likely to edit complex content in a second language. In addition, we find that multilinguals are less engaged and show lower levels of language proficiency in their second languages. We also examine the topical interests of multilingual editors and find that there is no significant difference between primary and non-primary editors in each language.
Missing Spectrum-Data Recovery in Cognitive Radio Networks Using Piecewise Constant Nonnegative Matrix Factorization
Venue: arXiv cs.OH 2015
Year: 2015

In this paper, we propose a missing spectrum data recovery technique for cognitive radio (CR) networks using Nonnegative Matrix Factorization (NMF). It is shown that the spectrum measurements collected from secondary users (SUs) can be factorized as product of a channel gain matrix times an activation matrix. Then, an NMF method with piecewise constant activation coefficients is introduced to analyze the measurements and estimate the missing spectrum data. The proposed optimization problem is solved by a Majorization-Minimization technique. The numerical simulation verifies that the proposed technique is able to accurately estimate the missing spectrum data in the presence of noise and fading.
What Soft Skills Software Architect Should Have? A Reflection from Software Industry
Venue: arXiv cs.SE 2015
Year: 2015

The job of software architect is considered very crucial in the life cycle of the software development because software architecture has a pivotal role in the success and failure of the software project in terms of cost and quality. People have different personality traits, and the way they perceive, plan and execute any assigned task is influenced by it. These personality traits are characterized by soft skills. Most of the time, software development is a team work involving several people executing different tasks. The success and failure stories of software projects revealed the human factor as one of the critical importance. In this work we are presenting an exploratory study about the soft skills requirements for a software architects job. We analyzed 124 advertised jobs in the title of software architect and explore the soft skills requirements. The results of this investigation help in understanding software skills requirement set for a job of software architect and presents the current status of their use in job advertisements.
Parametric Bilinear Generalized Approximate Message Passing
Venue: arXiv cs.IT 2015
Year: 2015

We propose a scheme to estimate the parameters $b_i$ and $c_j$ of the bilinear form $z_m=\sum_{i,j} b_i z_m^{(i,j)} c_j$ from noisy measurements $\{y_m\}_{m=1}^M$, where $y_m$ and $z_m$ are related through an arbitrary likelihood function and $z_m^{(i,j)}$ are known. Our scheme is based on generalized approximate message passing (G-AMP): it treats $b_i$ and $c_j$ as random variables and $z_m^{(i,j)}$ as an i.i.d.\ Gaussian 3-way tensor in order to derive a tractable simplification of the sum-product algorithm in the large-system limit. It generalizes previous instances of bilinear G-AMP, such as those that estimate matrices $\boldsymbol{B}$ and $\boldsymbol{C}$ from a noisy measurement of $\boldsymbol{Z}=\boldsymbol{BC}$, allowing the application of AMP methods to problems such as self-calibration, blind deconvolution, and matrix compressive sensing. Numerical experiments confirm the accuracy and computational efficiency of the proposed approach.
Compressive Video Sensing via Dictionary Learning and Forward Prediction
Venue: arXiv cs.MM 2015
Year: 2015

In this paper, we propose a new framework for compressive video sensing (CVS) that exploits the inherent spatial and temporal redundancies of a video sequence, effectively. The proposed method splits the video sequence into the key and non-key frames followed by dividing each frame into small non-overlapping blocks of equal sizes. At the decoder side, the key frames are reconstructed using adaptively learned sparsifying (ALS) basis via $\ell_0$ minimization, in order to exploit the spatial redundancy. Also, the effectiveness of three well-known dictionary learning algorithms is investigated in our method. For recovery of the non-key frames, a prediction of the current frame is initialized, by using the previous reconstructed frame, in order to exploit the temporal redundancy. The prediction is employed in a proper optimization problem to recover the current non-key frame. To compare our experimental results with the results of some other methods, we employ peak signal to noise ratio (PSNR) and structural similarity (SSIM) index as the quality assessor. The numerical results show the adequacy of our proposed method in CVS.
Online Model Evaluation in a Large-Scale Computational Advertising Platform
Venue: arXiv cs.AI 2015
Year: 2015

Online media provides opportunities for marketers through which they can deliver effective brand messages to a wide range of audiences. Advertising technology platforms enable advertisers to reach their target audience by delivering ad impressions to online users in real time. In order to identify the best marketing message for a user and to purchase impressions at the right price, we rely heavily on bid prediction and optimization models. Even though the bid prediction models are well studied in the literature, the equally important subject of model evaluation is usually overlooked. Effective and reliable evaluation of an online bidding model is crucial for making faster model improvements as well as for utilizing the marketing budgets more efficiently. In this paper, we present an experimentation framework for bid prediction models where our focus is on the practical aspects of model evaluation. Specifically, we outline the unique challenges we encounter in our platform due to a variety of factors such as heterogeneous goal definitions, varying budget requirements across different campaigns, high seasonality and the auction-based environment for inventory purchasing. Then, we introduce return on investment (ROI) as a unified model performance (i.e., success) metric and explain its merits over more traditional metrics such as click-through rate (CTR) or conversion rate (CVR). Most importantly, we discuss commonly used evaluation and metric summarization approaches in detail and propose a more accurate method for online evaluation of new experimental models against the baseline. Our meta-analysis-based approach addresses various shortcomings of other methods and yields statistically robust conclusions that allow us to conclude experiments more quickly in a reliable manner. We demonstrate the effectiveness of our evaluation strategy on real campaign data through some experiments.
Interval scheduling maximizing minimum coverage
Venue: arXiv cs.DS 2015
Year: 2015

In the classical interval scheduling type of problems, a set of $n$ jobs, characterized by their start and end time, need to be executed by a set of machines, under various constraints. In this paper we study a new variant in which the jobs need to be assigned to at most $k$ identical machines, such that the minimum number of machines that are busy at the same time is maximized. This is relevant in the context of genome sequencing and haplotyping, specifically when a set of DNA reads aligned to a genome needs to be pruned so that no more than $k$ reads overlap, while maintaining as much read coverage as possible across the entire genome. We show that the problem can be solved in time $\min\left(O(n^2\log k / \log n),O(nk\log k)\right)$ by using max-flows. We also give an $O(n\log n)$-time approximation algorithm with approximation ratio $ρ=\frac{k}{\lfloor k/2 \rfloor}$.
DSL-based Design Space Exploration for Temporal and Spatial Parallelism of Custom Stream Computing
Venue: arXiv cs.AR 2015
Year: 2015

Stream computation is one of the approaches suitable for FPGA-based custom computing due to its high throughput capability brought by pipelining with regular memory access. To increase performance of iterative stream computation, we can exploit both temporal and spatial parallelism by deepening and duplicating pipelines, respectively. However, the performance is constrained by several factors including available hardware resources on FPGA, an external memory bandwidth, and utilization of pipeline stages, and therefore we need to find the best mix of the different parallelism to achieve the highest performance per power. In this paper, we present a domain-specific language (DSL) based design space exploration for temporally and/or spatially parallel stream computation with FPGA. We define a DSL where we can easily design a hierarchical structure of parallel stream computation with abstract description of computation. For iterative stream computation of fluid dynamics simulation, we design hardware structures with a different mix of the temporal and spatial parallelism. By measuring the performance and the power consumption, we find the best among them.
Evolving Unipolar Memristor Spiking Neural Networks
Venue: arXiv cs.NE 2015
Year: 2015

Neuromorphic computing --- brainlike computing in hardware --- typically requires myriad CMOS spiking neurons interconnected by a dense mesh of nanoscale plastic synapses. Memristors are frequently citepd as strong synapse candidates due to their statefulness and potential for low-power implementations. To date, plentiful research has focused on the bipolar memristor synapse, which is capable of incremental weight alterations and can provide adaptive self-organisation under a Hebbian learning scheme. In this paper we consider the Unipolar memristor synapse --- a device capable of non-Hebbian switching between only two states (conductive and resistive) through application of a suitable input voltage --- and discuss its suitability for neuromorphic systems. A self-adaptive evolutionary process is used to autonomously find highly fit network configurations. Experimentation on a two robotics tasks shows that unipolar memristor networks evolve task-solving controllers faster than both bipolar memristor networks and networks containing constant nonplastic connections whilst performing at least comparably.
Sequential Information Guided Sensing
Venue: arXiv cs.IT 2015
Year: 2015

We study the value of information in sequential compressed sensing by characterizing the performance of sequential information guided sensing in practical scenarios when information is inaccurate. In particular, we assume the signal distribution is parameterized through Gaussian or Gaussian mixtures with estimated mean and covariance matrices, and we can measure compressively through a noisy linear projection or using one-sparse vectors, i.e., observing one entry of the signal each time. We establish a set of performance bounds for the bias and variance of the signal estimator via posterior mean, by capturing the conditional entropy (which is also related to the size of the uncertainty), and the additional power required due to inaccurate information to reach a desired precision. Based on this, we further study how to estimate covariance based on direct samples or covariance sketching. Numerical examples also demonstrate the superior performance of Info-Greedy Sensing algorithms compared with their random and non-adaptive counterparts.
Cooperative Relaying in Underlay Cognitive Systems with Hardware Impairments
Venue: arXiv cs.IT 2015
Year: 2015

The performance of an underlay cognitive (secondary) dual-hop relaying system with multiple antennas and hardware impairments at each transceiver is investigated. In particular, the outage probability of the end-to-end (e2e) communication is derived in closed-form, when either transmit antenna selection with maximum ratio combining (TAS/MRC), or TAS with selection combining (TAS/SC) are established in each hop. Simplified asymptotic outage expressions are also obtained, which manifest the diversity and array order of the system, the effectiveness of the balance on the number of transmit/receive antennas, and the impact of hardware impairments to the e2e communication.
Echo chambers in the age of misinformation
Venue: arXiv cs.CY 2015
Year: 2015

The wide availability of user-provided content in online social media facilitates the aggregation of people around common interests, worldviews, and narratives. Despite the enthusiastic rhetoric on the part of some that this process generates "collective intelligence", the WWW also allows the rapid dissemination of unsubstantiated conspiracy theories that often elicite rapid, large, but naive social responses such as the recent case of Jade Helm 15 -- where a simple military exercise turned out to be perceived as the beginning of the civil war in the US. We study how Facebook users consume information related to two different kinds of narrative: scientific and conspiracy news. We find that although consumers of scientific and conspiracy stories present similar consumption patterns with respect to content, the sizes of the spreading cascades differ. Homogeneity appears to be the primary driver for the diffusion of contents, but each echo chamber has its own cascade dynamics. To mimic these dynamics, we introduce a data-driven percolation model on signed networks.