OpenRaiser/Intern-Atlas huggingface dataset:
MorphoNoC: Exploring the Design Space of a Configurable Hybrid NoC using Nanophotonics
Venue: arXiv cs.OH 2017
Year: 2017

As diminishing feature sizes drive down the energy for computations, the power budget for on-chip communication is steadily rising. Furthermore, the increasing number of cores is placing a huge performance burden on the network-on-chip (NoC) infrastructure. While NoCs are designed as regular architectures that allow scaling to hundreds of cores, the lack of a flexible topology gives rise to higher latencies, lower throughput, and increased energy costs. In this paper, we explore MorphoNoCs - scalable, configurable, hybrid NoCs obtained by extending regular electrical networks with configurable nanophotonic links. In order to design MorphoNoCs, we first carry out a detailed study of the design space for Multi-Write Multi-Read (MWMR) nanophotonics links. After identifying optimum design points, we then discuss the router architecture for deploying them in hybrid electronic-photonic NoCs. We then study explore the design space at the network level, by varying the waveguide lengths and the number of hybrid routers. This affords us to carry out energy-latency trade-offs. For our evaluations, we adopt traces from synthetic benchmarks as well as the NAS Parallel Benchmark suite. Our results indicate that MorphoNoCs can achieve latency improvements of up to 3.0x or energy improvements of up to 1.37x over the base electronic network.
ImageJ2: ImageJ for the next generation of scientific image data
Venue: arXiv cs.SE 2017
Year: 2017

ImageJ is an image analysis program extensively used in the biological sciences and beyond. Due to its ease of use, recordable macro language, and extensible plug-in architecture, ImageJ enjoys contributions from non-programmers, amateur programmers, and professional developers alike. Enabling such a diversity of contributors has resulted in a large community that spans the biological and physical sciences. However, a rapidly growing user base, diverging plugin suites, and technical limitations have revealed a clear need for a concerted software engineering effort to support emerging imaging paradigms, to ensure the software's ability to handle the requirements of modern science. Due to these new and emerging challenges in scientific imaging, ImageJ is at a critical development crossroads. We present ImageJ2, a total redesign of ImageJ offering a host of new functionality. It separates concerns, fully decoupling the data model from the user interface. It emphasizes integration with external applications to maximize interoperability. Its robust new plugin framework allows everything from image formats, to scripting languages, to visualization to be extended by the community. The redesigned data model supports arbitrarily large, N-dimensional datasets, which are increasingly common in modern image acquisition. Despite the scope of these changes, backwards compatibility is maintained such that this new functionality can be seamlessly integrated with the classic ImageJ interface, allowing users and developers to migrate to these new methods at their own pace. ImageJ2 provides a framework engineered for flexibility, intended to support these requirements as well as accommodate future needs.
Asynchronous Physical-layer Network Coding: Symbol Misalignment Estimation and Its Effect on Decoding
Venue: arXiv cs.IT 2017
Year: 2017

In asynchronous physical-layer network coding (APNC) systems, the symbols from multiple transmitters to a common receiver may be misaligned. The knowledge of the amount of symbol misalignment, hence its estimation, is important to PNC decoding. This paper addresses the problem of symbol-misalignment estimation and the problem of optimal PNC decoding given the misalignment estimate, assuming the APNC system uses the root-raised-cosine pulse to carry signals (RRC-APNC). First, we put forth an optimal symbol-misalignment estimator that makes use of double baud-rate samples. Then, we devise optimal decoders for RRC-APNC in the presence of inaccurate symbol-misalignment estimates. In particular, we present a new whitening transformation to whiten the noise of the double baud-rate samples. Finally, we investigate the decoding performance of various estimation-and-decoding schemes for RRC-APNC. Extensive simulations show that: (i) Our double baud-rate estimator yields substantially more accurate symbol-misalignment estimates than the baud-rate estimator does. The mean-square-error (MSE) gains are up to 8 dB. (ii) An overall estimation-and-decoding scheme in which both estimation and decoding are based on double baud-rate samples yields much better performance than other schemes. Compared with a scheme in which both estimation and decoding are based on baud-rate samples), the double baud-rate sampling scheme yields 4.5 dB gains on symbol error rate (SER) performance in an AWGN channel, and 2 dB gains on packet error rate (PER) performance in a Rayleigh fading channel.
Nano-Intrinsic True Random Number Generation
Venue: arXiv cs.ET 2017
Year: 2017

Recent advances in predictive data analytics and ever growing digitalization and connectivity with explosive expansions in industrial and consumer Internet-of-Things (IoT) has raised significant concerns about security of people's identities and data. It has created close to ideal environment for adversaries in terms of the amount of data that could be used for modeling and also greater accessibility for side-channel analysis of security primitives and random number generators. Random number generators (RNGs) are at the core of most security applications. Therefore, a secure and trustworthy source of randomness is required to be found. Here, we present a differential circuit for harvesting one of the most stochastic phenomenon in solid-state physics, random telegraphic noise (RTN), that is designed to demonstrate significantly lower sensitivities to other sources of noises, radiation and temperature fluctuations. We use RTN in amorphous SrTiO3-based resistive memories to evaluate the proposed true random number generator (TRNG). Successful evaluation on conventional true randomness tests (NIST tests) has been shown. Robustness against using predictive machine learning and side-channel attacks have also been demonstrated in comparison with non-differential readouts methods.
The Economics of Competition and Cooperation Between MNOs and MVNOs
Venue: arXiv cs.NI 2017
Year: 2017

In this work, we consider the economics of the interaction between Mobile Virtual Network Operators (MVNOs) and Mobile Network Operators (MNOs). We investigate the incentives of an MNO for offering some of her resources to an MVNO instead of using the resources for her own. We formulate the problem as a sequential game. We consider a market with one MNO and one MVNO, and a continuum of undecided end-users. We assume that EUs have different preferences for the MNO and the MVNO. These preferences can be because of the differences in the service they are offering or the reluctance of an EU to buy her plan from one of them. We assume that the preferences also depend on the investment level the MNO and the MVNO. We show that there exists a unique interior SPNE, i.e. the SPNE by which both SPs receive a positive mass of EUs, and characterize it. We also consider a benchmark case in which the MNO and the MVNO do not cooperate, characterize the unique SPNE of this case, and compare the results of our model to the benchmark case to assess the incentive of the MNO to invest in her infrastructure and to offer it to the MVNO.
Label Propagation on K-partite Graphs with Heterophily
Venue: arXiv cs.LG 2017
Year: 2017

In this paper, for the first time, we study label propagation in heterogeneous graphs under heterophily assumption. Homophily label propagation (i.e., two connected nodes share similar labels) in homogeneous graph (with same types of vertices and relations) has been extensively studied before. Unfortunately, real-life networks are heterogeneous, they contain different types of vertices (e.g., users, images, texts) and relations (e.g., friendships, co-tagging) and allow for each node to propagate both the same and opposite copy of labels to its neighbors. We propose a $\mathcal{K}$-partite label propagation model to handle the mystifying combination of heterogeneous nodes/relations and heterophily propagation. With this model, we develop a novel label inference algorithm framework with update rules in near-linear time complexity. Since real networks change over time, we devise an incremental approach, which supports fast updates for both new data and evidence (e.g., ground truth labels) with guaranteed efficiency. We further provide a utility function to automatically determine whether an incremental or a re-modeling approach is favored. Extensive experiments on real datasets have verified the effectiveness and efficiency of our approach, and its superiority over the state-of-the-art label propagation methods.
Lyrics-to-Audio Alignment by Unsupervised Discovery of Repetitive Patterns in Vowel Acoustics
Venue: arXiv cs.SD 2017
Year: 2017

Most of the previous approaches to lyrics-to-audio alignment used a pre-developed automatic speech recognition (ASR) system that innately suffered from several difficulties to adapt the speech model to individual singers. A significant aspect missing in previous works is the self-learnability of repetitive vowel patterns in the singing voice, where the vowel part used is more consistent than the consonant part. Based on this, our system first learns a discriminative subspace of vowel sequences, based on weighted symmetric non-negative matrix factorization (WS-NMF), by taking the self-similarity of a standard acoustic feature as an input. Then, we make use of canonical time warping (CTW), derived from a recent computer vision technique, to find an optimal spatiotemporal transformation between the text and the acoustic sequences. Experiments with Korean and English data sets showed that deploying this method after a pre-developed, unsupervised, singing source separation achieved more promising results than other state-of-the-art unsupervised approaches and an existing ASR-based system.
Neurogenesis-Inspired Dictionary Learning: Online Model Adaption in a Changing World
Venue: arXiv cs.LG 2017
Year: 2017

In this paper, we focus on online representation learning in non-stationary environments which may require continuous adaptation of model architecture. We propose a novel online dictionary-learning (sparse-coding) framework which incorporates the addition and deletion of hidden units (dictionary elements), and is inspired by the adult neurogenesis phenomenon in the dentate gyrus of the hippocampus, known to be associated with improved cognitive function and adaptation to new environments. In the online learning setting, where new input instances arrive sequentially in batches, the neuronal-birth is implemented by adding new units with random initial weights (random dictionary elements); the number of new units is determined by the current performance (representation error) of the dictionary, higher error causing an increase in the birth rate. Neuronal-death is implemented by imposing l1/l2-regularization (group sparsity) on the dictionary within the block-coordinate descent optimization at each iteration of our online alternating minimization scheme, which iterates between the code and dictionary updates. Finally, hidden unit connectivity adaptation is facilitated by introducing sparsity in dictionary elements. Our empirical evaluation on several real-life datasets (images and language) as well as on synthetic data demonstrates that the proposed approach can considerably outperform the state-of-art fixed-size (nonadaptive) online sparse coding of Mairal et al. (2009) in the presence of nonstationary data. Moreover, we identify certain properties of the data (e.g., sparse inputs with nearly non-overlapping supports) and of the model (e.g., dictionary sparsity) associated with such improvements.
Polar Coding for Block Fading Channels
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we consider the problem of polar coding for block fading channels, with emphasis on those with instantaneous channel state information (CSI) at neither the transmitter nor the receiver. Our approach is to decompose a block fading channel of $T_c$ symbols per coherent interval into $T_c$ binary-input sub-channels in a capacity-preserving way, and design a polar code for each of them. For the case when instantaneous CSI is available at the receiver, a random interleaver can be used to enable joint encoding and decoding of all sub-channels so as to enhance the finite length performance. It is shown that our proposed schemes achieve the ergodic capacity of binary-input block fading channels under various CSI assumptions.
On Practical Accuracy of Edit Distance Approximation Algorithms
Venue: arXiv cs.DS 2017
Year: 2017

The edit distance is a basic string similarity measure used in many applications such as text mining, signal processing, bioinformatics, and so on. However, the computational cost can be a problem when we repeat many distance calculations as seen in real-life searching situations. A promising solution to cope with the problem is to approximate the edit distance by another distance with a lower computational cost. There are, indeed, many distances have been proposed for approximating the edit distance. However, their approximation accuracies are evaluated only theoretically: many of them are evaluated only with big-oh (asymptotic) notations, and without experimental analysis. Therefore, it is beneficial to know their actual performance in real applications. In this study we compared existing six approximation distances in two approaches: (i) we refined their theoretical approximation accuracy by calculating up to the constant coefficients, and (ii) we conducted some experiments, in one artificial and two real-life data sets, to reveal under which situations they perform best. As a result we obtained the following results: [Batu 2006] is the best theoretically and [Andoni 2010] experimentally. Theoretical considerations show that [Batu 2006] is the best if the string length n is large enough (n >= 300). [Andoni 2010] is experimentally the best for most data sets and theoretically the second best. [Bar-Yossef 2004], [Charikar 2006] and [Sokolov 2007], despite their middle-level theoretical performance, are experimentally as good as [Andoni 2010] for pairs of strings with large alphabet size.
Understanding Workers, Developing Effective Tasks, and Enhancing Marketplace Dynamics: A Study of a Large Crowdsourcing Marketplace
Venue: arXiv cs.HC 2017
Year: 2017

We conduct an experimental analysis of a dataset comprising over 27 million microtasks performed by over 70,000 workers issued to a large crowdsourcing marketplace between 2012-2016. Using this data---never before analyzed in an academic context---we shed light on three crucial aspects of crowdsourcing: (1) Task design --- helping requesters understand what constitutes an effective task, and how to go about designing one; (2) Marketplace dynamics --- helping marketplace administrators and designers understand the interaction between tasks and workers, and the corresponding marketplace load; and (3) Worker behavior --- understanding worker attention spans, lifetimes, and general behavior, for the improvement of the crowdsourcing ecosystem as a whole.
Distributed Clustering for Multiuser Networks through Coalition Formation
Venue: arXiv cs.GT 2017
Year: 2017

Clustering mechanisms are essential in certain multiuser networks for achieving efficient resource utilization. This lecture note presents the theory of coalition formation as a useful tool for distributed clustering problems. We reveal the generality of the theory, and study complexity aspects which must be considered in multiuser networks.
Election Bias: Comparing Polls and Twitter in the 2016 U.S. Election
Venue: arXiv cs.SI 2017
Year: 2017

While the polls have been the most trusted source for election predictions for decades, in the recent presidential election they were called inaccurate and biased. How inaccurate were the polls in this election and can social media beat the polls as an accurate election predictor? Polls from several news outlets and sentiment analysis on Twitter data were used, in conjunction with the results of the election, to answer this question and outline further research on the best method for predicting the outcome of future elections.
What the Language You Tweet Says About Your Occupation
Venue: arXiv cs.CY 2017
Year: 2017

Many aspects of people's lives are proven to be deeply connected to their jobs. In this paper, we first investigate the distinct characteristics of major occupation categories based on tweets. From multiple social media platforms, we gather several types of user information. From users' LinkedIn webpages, we learn their proficiencies. To overcome the ambiguity of self-reported information, a soft clustering approach is applied to extract occupations from crowd-sourced data. Eight job categories are extracted, including Marketing, Administrator, Start-up, Editor, Software Engineer, Public Relation, Office Clerk, and Designer. Meanwhile, users' posts on Twitter provide cues for understanding their linguistic styles, interests, and personalities. Our results suggest that people of different jobs have unique tendencies in certain language styles and interests. Our results also clearly reveal distinctive levels in terms of Big Five Traits for different jobs. Finally, a classifier is built to predict job types based on the features extracted from tweets. A high accuracy indicates a strong discrimination power of language features for job prediction task.
On polynomial approximations over $\mathbb{Z}/2^k\mathbb{Z}$
Venue: arXiv cs.CC 2017
Year: 2017

We study approximation of Boolean functions by low-degree polynomials over the ring $\mathbb{Z}/2^k\mathbb{Z}$. More precisely, given a Boolean function $F:\{0,1\}^n \rightarrow \{0,1\}$, define its $k$-lift to be $F_k:\{0,1\}^n \rightarrow \{0,2^{k-1}\}$ by $F_k(x) = 2^{k-F(x)} \pmod {2^k}$. We consider the fractional agreement (which we refer to as $γ_{d,k}(F)$) of $F_k$ with degree $d$ polynomials from $\mathbb{Z}/2^k\mathbb{Z}[x_1,\ldots,x_n]$. Our results are the following: - Increasing $k$ can help: We observe that as $k$ increases, $γ_{d,k}(F)$ cannot decrease. We give two kinds of examples where $γ_{d,k}(F)$ actually increases. The first is an infinite family of functions $F$ such that $γ_{2d,2}(F) - γ_{3d-1,1}(F) \geq Ω(1)$. The second is an infinite family of functions $F$ such that $γ_{d,1}(F)\leq\frac{1}{2}+o(1)$ -- as small as possible -- but $γ_{d,3}(F) \geq \frac{1}{2}+Ω(1)$. - Increasing $k$ doesn't always help: Adapting a proof of Green [Comput. Complexity, 9(1):16-38, 2000], we show that irrespective of the value of $k$, the Majority function $\mathrm{Maj}_n$ satisfies $γ_{d,k}(\mathrm{Maj}_n) \leq \frac{1}{2}+\frac{O(d)}{\sqrt{n}}$. In other words, polynomials over $\mathbb{Z}/2^k\mathbb{Z}$ for large $k$ do not approximate the majority function any better than polynomials over $\mathbb{Z}/2\mathbb{Z}$. We observe that the model we study subsumes the model of non-classical polynomials in the sense that proving bounds in our model implies bounds on the agreement of non-classical polynomials with Boolean functions. In particular, our results answer questions raised by Bhowmick and Lovett [In Proc. 30th Computational Complexity Conf., pages 72-87, 2015] that ask whether non-classical polynomials approximate Boolean functions better than classical polynomials of the same degree.
A New Combination of Message Passing Techniques for Receiver Design in MIMO-OFDM Systems
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we propose a new combined message passing algorithm which allows belief propagation (BP) and mean filed (MF) applied on a same factor node, so that MF can be applied to hard constraint factors. Based on the proposed message passing algorithm, a iterative receiver is designed for MIMO-OFDM systems. Both BP and MF are exploited to deal with the hard constraint factor nodes involving the multiplication of channel coefficients and data symbols to reduce the complexity of the only BP used. The numerical results show that the BER performance of the proposed low complexity receiver closely approach that of the state-of-the-art receiver, where only BP is used to handled the hard constraint factors, in the high SNRs.
Minimax Optimal Estimators for Additive Scalar Functionals of Discrete Distributions
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we consider estimators for an additive functional of $ϕ$, which is defined as $θ(P;ϕ)=\sum_{i=1}^kϕ(p_i)$, from $n$ i.i.d. random samples drawn from a discrete distribution $P=(p_1,...,p_k)$ with alphabet size $k$. We propose a minimax optimal estimator for the estimation problem of the additive functional. We reveal that the minimax optimal rate is characterized by the divergence speed of the fourth derivative of $ϕ$ if the divergence speed is high. As a result, we show there is no consistent estimator if the divergence speed of the fourth derivative of $ϕ$ is larger than $p^{-4}$. Furthermore, if the divergence speed of the fourth derivative of $ϕ$ is $p^{4-α}$ for $α\in (0,1)$, the minimax optimal rate is obtained within a universal multiplicative constant as $\frac{k^2}{(n\ln n)^{2α}} + \frac{k^{2-2α}}{n}$.
Design of an Audio Interface for Patmos
Venue: arXiv cs.AR 2017
Year: 2017

This paper describes the design and implementation of an audio interface for the Patmos processor, which runs on an Altera DE2-115 FPGA board. This board has an audio codec included, the WM8731. The interface described in this work allows to receive and send audio from and to the WM8731, and to synthesize, store or manipulate audio signals writing C programs for Patmos. The audio interface described in this paper is intended to be used with the Patmos processor. Patmos is an open source RISC ISAs with a load-store architecture, that is optimized for Real-Time Systems. Patmos is part of a project founded by the European Union called T-CREST (Time-predictable Multi-Core Architecture for Embedded Systems).[5] The structure of this project is integrated with the Patmos project: new hardware modules have been added as IOs, which allow the communication between the processor and the audio codec. These modules include a clock generator for the audio chip, ADC and DAC modules for the audio conversion from analog to digital and vice versa, and an I2C module which allows setting configuration parameters on the audio codec. Moreover, a top module has been created, which connects all the modules previously mentioned between them, to Patmos and to the WM8731, using the external pins of the FPGA.
Evaluating navigational RDF queries over the Web
Venue: arXiv cs.DB 2017
Year: 2017

Semantic Web, and its underlying data format RDF, lend themselves naturally to navigational querying due to their graph-like structure. This is particularly evident when considering RDF data on the Web, where various separately published datasets reference each other and form a giant graph known as the Web of Linked Data. And while navigational queries over singular RDF datasets are supported through SPARQL property paths, not much is known about evaluating them over Linked Data. In this paper we propose a method for evaluating property path queries over the Web based on the classical AI search algorithm A*, show its optimality in the open world setting of the Web, and test it using real world queries which access a variety of RDF datasets available online.