OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Identity Testing and Polynomial Factorization over Non-associative Free Rings
Venue: arXiv cs.CC 2017
Year: 2017

In this paper we study arithmetic computations in the nonassociative, and noncommutative free polynomial ring $\mathbb{F}\{x_1,x_2,\ldots,x_n\}$. Prior to this work, nonassociative arithmetic computation was considered by Hrubes, Wigderson, and Yehudayoff [HWY10], and they showed lower bounds and proved completeness results. We consider Polynomial Identity Testing (PIT) and polynomial factorization over $\mathbb{F}\{x_1,x_2,\ldots,x_n\}$ and show the following results. (1) Given an arithmetic circuit $C$ of size $s$ computing a polynomial $f\in \mathbb{F} \{x_1,x_2,\ldots,x_n\}$ of degree $d$, we give a deterministic $poly(n,s,d)$ algorithm to decide if $f$ is identically zero polynomial or not. Our result is obtained by a suitable adaptation of the PIT algorithm of Raz-Shpilka [RS05] for noncommutative ABPs. (2) Given an arithmetic circuit $C$ of size $s$ computing a polynomial $f\in \mathbb{F} \{x_1,x_2,\ldots,x_n\}$ of degree $d$, we give an efficient deterministic algorithm to compute circuits for the irreducible factors of $f$ in time $poly(n,s,d)$ when $\mathbb{F}=\mathbb{Q}$. Over finite fields of characteristic $p$, our algorithm runs in time $poly(n,s,d,p)$.
Curious Minds Wonder Alike: Studying Multimodal Behavioral Dynamics to Design Social Scaffolding of Curiosity
Venue: arXiv cs.HC 2017
Year: 2017

Curiosity is the strong desire to learn or know more about something or someone. Since learning is often a social endeavor, social dynamics in collaborative learning may inevitably influence curiosity. There is a scarcity of research, however, focusing on how curiosity can be evoked in group learning contexts. Inspired by a recently proposed theoretical framework that articulates an integrated socio-cognitive infrastructure of curiosity, in this work, we use data-driven approaches to identify fine-grained social scaffolding of curiosity in child-child interaction, and propose how they can be used to elicit and maintain curiosity in technology-enhanced learning environments. For example, we discovered sequential patterns of multimodal behaviors across group members and we describe those that maximize an individual's utility, or likelihood, of demonstrating curiosity during open-ended problem-solving in group work. We also discovered, and describe here, behaviors that directly or in a mediated manner cause curiosity related conversational behaviors in the interaction, with twice as many interpersonal causal influences compared to intrapersonal ones. We explain how these findings form a solid foundation for developing curiosity-increasing learning technologies or even assisting a human coach to induce curiosity among learners.
A sub-mW IoT-endnode for always-on visual monitoring and smart triggering
Venue: arXiv cs.OH 2017
Year: 2017

This work presents a fully-programmable Internet of Things (IoT) visual sensing node that targets sub-mW power consumption in always-on monitoring scenarios. The system features a spatial-contrast $128\mathrm{x}64$ binary pixel imager with focal-plane processing. The sensor, when working at its lowest power mode ($10μW$ at 10 fps), provides as output the number of changed pixels. Based on this information, a dedicated camera interface, implemented on a low-power FPGA, wakes up an ultra-low-power parallel processing unit to extract context-aware visual information. We evaluate the smart sensor on three always-on visual triggering application scenarios. Triggering accuracy comparable to RGB image sensors is achieved at nominal lighting conditions, while consuming an average power between $193μW$ and $277μW$, depending on context activity. The digital sub-system is extremely flexible, thanks to a fully-programmable digital signal processing engine, but still achieves 19x lower power consumption compared to MCU-based cameras with significantly lower on-board computing capabilities.
Crime Scene Re-investigation: A Postmortem Analysis of Game Account Stealers' Behaviors
Venue: arXiv cs.CR 2017
Year: 2017

As item trading becomes more popular, users can change their game items or money into real money more easily. At the same time, hackers turn their eyes on stealing other users game items or money because it is much easier to earn money than traditional gold-farming by running game bots. Game companies provide various security measures to block account- theft attempts, but many security measures on the user-side are disregarded by users because of lack of usability. In this study, we propose a server-side account theft detection system base on action sequence analysis to protect game users from malicious hackers. We tested this system in the real Massively Multiplayer Online Role Playing Game (MMORPG). By analyzing users full game play log, our system can find the particular action sequences of hackers with high accuracy. Also, we can trace where the victim accounts stolen money goes.
Unimem: Runtime Data Management on Non-Volatile Memory-based Heterogeneous Main Memory
Venue: arXiv cs.DC 2017
Year: 2017

Non-volatile memory (NVM) provides a scalable and power-efficient solution to replace DRAM as main memory. However, because of relatively high latency and low bandwidth of NVM, NVM is often paired with DRAM to build a heterogeneous memory system (HMS). As a result, data objects of the application must be carefully placed to NVM and DRAM for best performance. In this paper, we introduce a lightweight runtime solution that automatically and transparently manage data placement on HMS without the requirement of hardware modifications and disruptive change to applications. Leveraging online profiling and performance models, the runtime characterizes memory access patterns associated with data objects, and minimizes unnecessary data movement. Our runtime solution effectively bridges the performance gap between NVM and DRAM. We demonstrate that using NVM to replace the majority of DRAM can be a feasible solution for future HPC systems with the assistance of a software-based data management.
Thorup-Zwick Emulators are Universally Optimal Hopsets
Venue: arXiv cs.DS 2017
Year: 2017

A $(β,ε)$-$\textit{hopset}$ is, informally, a weighted edge set that, when added to a graph, allows one to get from point $a$ to point $b$ using a path with at most $β$ edges ("hops") and length $(1+ε)\mathrm{dist}(a,b)$. In this paper we observe that Thorup and Zwick's $\textit{sublinear additive}$ emulators are also actually $(O(k/ε)^k,ε)$-hopsets for every $ε>0$, and that with a small change to the Thorup-Zwick construction, the size of the hopset can be made $O(n^{1+\frac{1}{2^{k+1}-1}})$. As corollaries, we also shave "$k$" factors off the size of Thorup and Zwick's sublinear additive emulators and the sparsest known $(1+ε,O(k/ε)^{k-1})$-spanners, due to Abboud, Bodwin, and Pettie.
Predicting Foreground Object Ambiguity and Efficiently Crowdsourcing the Segmentation(s)
Venue: arXiv cs.CV 2017
Year: 2017

We propose the ambiguity problem for the foreground object segmentation task and motivate the importance of estimating and accounting for this ambiguity when designing vision systems. Specifically, we distinguish between images which lead multiple annotators to segment different foreground objects (ambiguous) versus minor inter-annotator differences of the same object. Taking images from eight widely used datasets, we crowdsource labeling the images as "ambiguous" or "not ambiguous" to segment in order to construct a new dataset we call STATIC. Using STATIC, we develop a system that automatically predicts which images are ambiguous. Experiments demonstrate the advantage of our prediction system over existing saliency-based methods on images from vision benchmarks and images taken by blind people who are trying to recognize objects in their environment. Finally, we introduce a crowdsourcing system to achieve cost savings for collecting the diversity of all valid "ground truth" foreground object segmentations by collecting extra segmentations only when ambiguity is expected. Experiments show our system eliminates up to 47% of human effort compared to existing crowdsourcing methods with no loss in capturing the diversity of ground truths.
Middleware Technologies for Cloud of Things - a survey
Venue: arXiv cs.DC 2017
Year: 2017

The next wave of communication and applications rely on the new services provided by Internet of Things which is becoming an important aspect in human and machines future. The IoT services are a key solution for providing smart environments in homes, buildings and cities. In the era of a massive number of connected things and objects with a high grow rate, several challenges have been raised such as management, aggregation and storage for big produced data. In order to tackle some of these issues, cloud computing emerged to IoT as Cloud of Things (CoT) which provides virtually unlimited cloud services to enhance the large scale IoT platforms. There are several factors to be considered in design and implementation of a CoT platform. One of the most important and challenging problems is the heterogeneity of different objects. This problem can be addressed by deploying suitable "Middleware". Middleware sits between things and applications that make a reliable platform for communication among things with different interfaces, operating systems, and architectures. The main aim of this paper is to study the middleware technologies for CoT. Toward this end, we first present the main features and characteristics of middlewares. Next we study different architecture styles and service domains. Then we presents several middlewares that are suitable for CoT based platforms and lastly a list of current challenges and issues in design of CoT based middlewares is discussed.
On the Sub-optimality of Single-Letter Coding over Networks
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we establish a new bound tying together the effective length and the maximum correlation between the outputs of an arbitrary pair of Boolean functions which operate on two sequences of correlated random variables. We derive a new upper bound on the correlation between the outputs of these functions. The upper bound may find applications in problems in many areas which deal with common information. We build upon Witsenhausen's result on maximum correlation. The present upper bound takes into account the effective length of the Boolean functions in characterizing the correlation. We use the new bound to characterize the communication-cooperation tradeoff in multi-terminal communications. We investigate binary block-codes (BBC). A BBC is defined as a vector of Boolean functions. We consider an ensemble of BBCs which is randomly generated using single-letter distributions. We characterize the vector of dependency spectrums of these BBCs. We use this vector to bound the correlation between the outputs of two distributed BBCs. Finally, the upper bound is used to show that the large blocklength single-letter coding schemes studied in the literature are sub-optimal in various multi-terminal communication settings.
Orthogonal Code-based Block Transmission for Burst Transmission
Venue: arXiv cs.IT 2017
Year: 2017

This paper proposes a new multi-carrier system, called orthogonal code-based block transmission (OCBT). OCBT applies a time-spreading method with an orthogonal code to have a block signal structure and a windowing procedure to reduce the out-of-band (OOB) radiation. The proposed OCBT can transmit the quadrature amplitude modulation (QAM) signals to use the conventional multiple input multiple output techniques. Numerical results show that the proposed OCBT using QAM signal has the short burst compared to the filter-bank multi-carrier (FBMC), the low complexity compared to FBMC and windowed orthogonal frequency division multiplexing (W-OFDM) and also the low OOB radiation compared to OFDM.
Understanding the evolution of multimedia content in the Internet through BitTorrent glasses
Venue: arXiv cs.NI 2017
Year: 2017

Today's Internet traffic is mostly dominated by multimedia content and the prediction is that this trend will intensify in the future. Therefore, main Internet players, such as ISPs, content delivery platforms (e.g. Youtube, Bitorrent, Netflix, etc) or CDN operators, need to understand the evolution of multimedia content availability and popularity in order to adapt their infrastructures and resources to satisfy clients requirements while they minimize their costs. This paper presents a thorough analysis on the evolution of multimedia content available in BitTorrent. Specifically, we analyze the evolution of four relevant metrics across different content categories: content availability, content popularity, content size and user's feedback. To this end we leverage a large-scale dataset formed by 4 snapshots collected from the most popular BitTorrent portal, namely The Pirate Bay, between Nov. 2009 and Feb. 2012. Overall our dataset is formed by more than 160k content that attracted more than 185M of download sessions.
A General Framework For Task-Oriented Network Inference
Venue: arXiv cs.SI 2017
Year: 2017

We present a brief introduction to a flexible, general network inference framework which models data as a network space, sampled to optimize network structure to a particular task. We introduce a formal problem statement related to influence maximization in networks, where the network structure is not given as input, but learned jointly with an influence maximization solution.
"Liar, Liar Pants on Fire": A New Benchmark Dataset for Fake News Detection
Venue: arXiv cs.CL 2017
Year: 2017

Automatic fake news detection is a challenging problem in deception detection, and it has tremendous real-world political and social impacts. However, statistical approaches to combating fake news has been dramatically limited by the lack of labeled benchmark datasets. In this paper, we present liar: a new, publicly available dataset for fake news detection. We collected a decade-long, 12.8K manually labeled short statements in various contexts from PolitiFact.com, which provides detailed analysis report and links to source documents for each case. This dataset can be used for fact-checking research as well. Notably, this new dataset is an order of magnitude larger than previously largest public fake news datasets of similar type. Empirically, we investigate automatic fake news detection based on surface-level linguistic patterns. We have designed a novel, hybrid convolutional neural network to integrate meta-data with text. We show that this hybrid approach can improve a text-only deep learning model.
A Distributed Method for Optimal Capacity Reservation
Venue: arXiv cs.DC 2017
Year: 2017

We consider the problem of reserving link capacity in a network in such a way that any of a given set of flow scenarios can be supported. In the optimal capacity reservation problem, we choose the reserved link capacities to minimize the reservation cost. This problem reduces to a large linear program, with the number of variables and constraints on the order of the number of links times the number of scenarios. Small and medium size problems are within the capabilities of generic linear program solvers. We develop a more scalable, distributed algorithm for the problem that alternates between solving (in parallel) one flow problem per scenario, and coordination steps, which connect the individual flows and the reservation capacities.
Limitations of OpenFlow Topology Discovery Protocol
Venue: arXiv cs.NI 2017
Year: 2017

OpenFlow Discovery Protocol (OFDP) is the de-facto protocol used by OpenFlow controllers to discover the underlying topology. In this paper, we show that OFDP has some serious security, efficiency and functionality limitations that make it non suitable for production deployments. Instead, we briefly introduce sOFTD, a new discovery protocol with a built-in security characteristics and which is more efficient than traditional OFDP.
Computing Tropical Prevarieties in Parallel
Venue: arXiv cs.MS 2017
Year: 2017

The computation of the tropical prevariety is the first step in the application of polyhedral methods to compute positive dimensional solution sets of polynomial systems. In particular, pretropisms are candidate leading exponents for the power series developments of the solutions. The computation of the power series may start as soon as one pretropism is available, so our parallel computation of the tropical prevariety has an application in a pipelined solver. We present a parallel implementation of dynamic enumeration. Our first distributed memory implementation with forked processes achieved good speedups, but quite often resulted in large variations in the execution times of the processes. The shared memory multithreaded version applies work stealing to reduce the variability of the run time. Our implementation applies the thread safe Parma Polyhedral Library (PPL), in exact arithmetic with the GNU Multiprecision Arithmetic Library (GMP), aided by the fast memory allocations of TCMalloc. Our parallel implementation is capable of computing the tropical prevariety of the cyclic 16-roots problem. We also report on computational experiments on the $n$-body and $n$-vortex problems; our computational results compare favorably with Gfan.
Optimum Decoder for Multiplicative Spread Spectrum Image Watermarking with Laplacian Modeling
Venue: arXiv cs.MM 2017
Year: 2017

This paper investigates the multiplicative spread spectrum watermarking method for the image. The information bit is spreaded into middle-frequency Discrete Cosine Transform (DCT) coefficients of each block of an image using a generated pseudo-random sequence. Unlike the conventional signal modeling, we suppose that both signal and noise are distributed with Laplacian distribution because the sample loss of digital media can be better modeled with this distribution than the Gaussian one. We derive the optimum decoder for the proposed embedding method thanks to the maximum likelihood decoding scheme. We also analyze our watermarking system in the presence of noise and provide analytical evaluations and several simulations. The results show that it has the suitable performance and transparency required for watermarking applications.
Robust, Informative Human-in-the-Loop Predictions via Empirical Reachable Sets
Venue: arXiv cs.SY 2017
Year: 2017

In order to develop provably safe human-in-the-loop systems, accurate and precise models of human behavior must be developed. In the case of intelligent vehicles, one can imagine the need for predicting driver behavior to develop minimally invasive active safety systems or to safely interact with other vehicles on the road. We present a optimization based method for approximating the stochastic reachable set for human-in-the-loop systems. This method identifies the most precise subset of states that a human driven vehicle may enter, given some dataset of observed trajectories. We phrase this problem as a mixed integer linear program, which can be solved using branch and bound methods. The resulting model uncovers the most representative subset that encapsulates the likely trajectories, up to some probability threshold, by optimally rejecting outliers in the dataset. This tool provides set predictions consisting of trajectories observed from the nonlinear dynamics and behaviors of the human driven car, and can account for modes of behavior, like the driver state or intent. This allows us to predict driving behavior over long time horizons with high accuracy. By using this realistic data and flexible algorithm, a precise and accurate driver model can be developed to capture likely behaviors. The resulting prediction can be tailored to an individual for use in semi-autonomous frameworks or generally applied for autonomous planning in interactive maneuvers.
An Authentication Protocol for Future Sensor Networks
Venue: arXiv cs.CR 2017
Year: 2017

Authentication is one of the essential security services in Wireless Sensor Networks (WSNs) for ensuring secure data sessions. Sensor node authentication ensures the confidentiality and validity of data collected by the sensor node, whereas user authentication guarantees that only legitimate users can access the sensor data. In a mobile WSN, sensor and user nodes move across the network and exchange data with multiple nodes, thus experiencing the authentication process multiple times. The integration of WSNs with Internet of Things (IoT) brings forth a new kind of WSN architecture along with stricter security requirements; for instance, a sensor node or a user node may need to establish multiple concurrent secure data sessions. With concurrent data sessions, the frequency of the re-authentication process increases in proportion to the number of concurrent connections, which makes the security issue even more challenging. The currently available authentication protocols were designed for the autonomous WSN and do not account for the above requirements. In this paper, we present a novel, lightweight and efficient key exchange and authentication protocol suite called the Secure Mobile Sensor Network (SMSN) Authentication Protocol. In the SMSN a mobile node goes through an initial authentication procedure and receives a re-authentication ticket from the base station. Later a mobile node can use this re-authentication ticket when establishing multiple data exchange sessions and/or when moving across the network. This scheme reduces the communication and computational complexity of the authentication process. We proved the strength of our protocol with rigorous security analysis and simulated the SMSN and previously proposed schemes in an automated protocol verifier tool. Finally, we compared the computational complexity and communication cost against well-known authentication protocols.
Aligned Image Sets and the Generalized Degrees of Freedom of Symmetric MIMO Interference Channel with Partial CSIT
Venue: arXiv cs.IT 2017
Year: 2017

The generalized degrees of freedom (GDoF) of the two user symmetric multiple input multiple output (MIMO) interference channel (IC) are characterized as a function of the channel strength levels and the level of channel state information at the transmitters (CSIT). In this symmetric setting, each transmitter is equipped with M antennas, each receiver is equipped with N antennas, and both cross links have the same strength parameter $α$ and the same channel uncertainty parameter $β$. The main challenge resides in the proof of the outer bound which is accomplished by a generalization of the aligned image sets approach.
Apparent Singularities of D-finite Systems
Venue: arXiv cs.SC 2017
Year: 2017

We generalize the notions of singularities and ordinary points from linear ordinary differential equations to D-finite systems. Ordinary points of a D-finite system are characterized in terms of its formal power series solutions. We also show that apparent singularities can be removed like in the univariate case by adding suitable additional solutions to the system at hand. Several algorithms are presented for removing and detecting apparent singularities. In addition, an algorithm is given for computing formal power series solutions of a D-finite system at apparent singularities.
Pointed subspace approach to incomplete data
Venue: arXiv cs.LG 2017
Year: 2017

Incomplete data are often represented as vectors with filled missing attributes joined with flag vectors indicating missing components. In this paper we generalize this approach and represent incomplete data as pointed affine subspaces. This allows to perform various affine transformations of data, as whitening or dimensionality reduction. We embed such generalized missing data into a vector space by mapping pointed affine subspace (generalized missing data point) to a vector containing imputed values joined with a corresponding projection matrix. Such an operation preserves the scalar product of the embedding defined for flag vectors and allows to input transformed incomplete data to typical classification methods.