OpenRaiser/Intern-Atlas huggingface dataset:
Privacy Concerns vs. User Behavior in Community Question Answering
Venue: arXiv cs.SI 2015
Year: 2015

Community-based question answering (CQA) platforms are crowd-sourced services for sharing user expertise on various topics, from mechanical repairs to parenting. While they naturally build-in an online social network infrastructure, they carry a very different purpose from Facebook-like social networks, where users "hang-out" with their friends and tend to share more personal information. It is unclear, thus, how the privacy concerns and their correlation with user behavior in an online social network translate into a CQA platform. This study analyzes one year of recorded traces from a mature CQA platform to understand the association between users' privacy concerns as manifested by their account settings and their activity in the platform. The results show that privacy preference is correlated with behavior in the community in terms of engagement, retention, accomplishments and deviance from the norm. We find privacy-concerned users have higher qualitative and quantitative contributions, show higher retention, report more abuses, have higher perception on answer quality and have larger social circles. However, at the same time, these users also exhibit more deviant behavior than the users with public profiles.
Prediction of Cyberbullying Incidents on the Instagram Social Network
Venue: arXiv cs.IR 2015
Year: 2015

Cyberbullying is a growing problem affecting more than half of all American teens. The main goal of this paper is to investigate fundamentally new approaches to understand and automatically detect and predict incidents of cyberbullying in Instagram, a media-based mobile social network. In this work, we have collected a sample data set consisting of Instagram images and their associated comments. We then designed a labeling study and employed human contributors at the crowd-sourced CrowdFlower website to label these media sessions for cyberbullying. A detailed analysis of the labeled data is then presented, including a study of relationships between cyberbullying and a host of features such as cyberaggression, profanity, social graph features, temporal commenting behavior, linguistic content, and image content. Using the labeled data, we further design and evaluate the performance of classifiers to automatically detect and pre- dict incidents of cyberbullying and cyberaggression.
A Parallel Algorithm to Test Chordality of Graphs
Venue: arXiv cs.DC 2015
Year: 2015

We present a simple parallel algorithm to test chordality of graphs which is based on the parallel Lexicographical Breadth-First Search algorithm. In total, the algorithm takes time O(N ) on N-threads machine and it performs work O(N 2 ) , where N is the number of vertices in a graph. Our implementation of the algorithm uses a GPU environment Nvidia CUDA C. The algorithm is implemented in CUDA 4.2 and it has been tested on Nvidia GeForce GTX 560 Ti of compute capability 2.1. At the end of the thesis we present the results achieved by our implementation and compare them with the results achieved by the sequential algorithm
Translation-like Actions and Aperiodic Subshifts on Groups
Venue: arXiv cs.FL 2015
Year: 2015

It is well known that if $G$ admits a f.g. subgroup $H$ with a weaklyaperiodic SFT (resp. an undecidable domino problem), then $G$itself has a weakly aperiodic SFT (resp. an undecidable domino problem).We prove that we can replace the property "$H$ is a subgroup of $G$"by "$H$ acts translation-like on $G$", provided $H$ is finitely presented.In particular:* If $G\_1$ and $G\_2$ are f.g. infinite groups, then $G\_1 \times G\_2$ has a weakly aperiodic SFT (and actually a undecidable domino problem). In particular the Grigorchuk group has an undecidable domino problem. * Every infinite f.g. $p$-group admits a weakly aperiodic SFT.
Rate-Distortion Function for a Heegard-Berger Problem with Two Sources and Degraded Reconstruction sets
Venue: arXiv cs.IT 2015
Year: 2015

In this work, we investigate an instance of the Heegard-Berger problem with two sources and arbitrarily correlated side information sequences at two decoders, in which the reconstruction sets at the decoders are degraded. Specifically, two sources are to be encoded in a manner that one of the two is reproduced losslessly by both decoders, and the other is reproduced to within some prescribed distortion level at one of the two decoders. We establish a single-letter characterization of the rate-distortion function for this model. The investigation of this result in some special cases also sheds light on the utility of joint compression of the two sources. Furthermore, we also generalize our result to the setting in which the source component that is to be recovered by both users is reconstructed in a lossy fashion, under the requirement that all terminals (i.e., the encoder and both decoders) can share an exact copy of the compressed version of this source component, i.e., a common encoder-decoders reconstruction constraint. For this model as well, we establish a single-letter characterization of the associated rate-distortion function.
Deterministic Broadcasting and Gossiping with Beeps
Venue: arXiv cs.DC 2015
Year: 2015

Broadcasting and gossiping are fundamental communication tasks in networks. In broadcasting,one node of a network has a message that must be learned by all other nodes. In gossiping, every node has a (possibly different) message, and all messages must be learned by all nodes. We study these well-researched tasks in a very weak communication model, called the {\em beeping model}. Communication proceeds in synchronous rounds. In each round, a node can either listen, i.e., stay silent, or beep, i.e., emit a signal. A node hears a beep in a round, if it listens in this round and if one or more adjacent nodes beep in this round. All nodes have different labels from the set $\{0,\dots , L-1\}$. Our aim is to provide fast deterministic algorithms for broadcasting and gossiping in the beeping model. Let $N$ be an upper bound on the size of the network and $D$ its diameter. Let $m$ be the size of the message in broadcasting, and $M$ an upper bound on the size of all input messages in gossiping. For the task of broadcasting we give an algorithm working in time $O(D+m)$ for arbitrary networks, which is optimal. For the task of gossiping we give an algorithm working in time $O(N(M+D\log L))$ for arbitrary networks. At the time of writing this paper we were unaware of the paper: A. Czumaj, P. Davis, Communicating with Beeps, arxiv:1505.06107 [cs.DC] which contains the same results for broadcasting and a stronger upper bound for gossiping in a slightly different model.
On the regularity of $\{\lfloor\log_b(αn+β)\rfloor\}_{n\geq0}$
Venue: arXiv cs.FL 2015
Year: 2015

Let $α,β$ be real numbers and $b\geq2$ be an integer. Allouche and Shallit showed that the sequence $\{\lfloorαn+β\rfloor\}_{n\geq0}$ is $b$-regular if and only if $α$ is rational. In this paper, using a base-independent regular language, we prove a similar result that the sequence $\{\lfloor\log_b(αn+β)\rfloor\}_{n\geq0}$ is $b$-regular if and only if $α$ is rational. In particular, when $α=\sqrt{2},β=0$ and $b=2$, we answer the question of Allouche and Shallit that the sequence $\{\lfloor\frac{1}{2}+\log_2n\rfloor\}_{n\geq0}$ is not $2$-regular, which has been proved by Bell, Moshe and Rowland respectively.
Transfer Learning for Device Fingerprinting with Application to Cognitive Radio Networks
Venue: arXiv cs.CR 2015
Year: 2015

Primary user emulation (PUE) attacks are an emerging threat to cognitive radio (CR) networks in which malicious users imitate the primary users (PUs) signals to limit the access of secondary users (SUs). Ascertaining the identity of the devices is a key technical challenge that must be overcome to thwart the threat of PUE attacks. Typically, detection of PUE attacks is done by inspecting the signals coming from all the devices in the system, and then using these signals to form unique fingerprints for each device. Current detection and fingerprinting approaches require certain conditions to hold in order to effectively detect attackers. Such conditions include the need for a sufficient amount of fingerprint data for users or the existence of both the attacker and the victim PU within the same time frame. These conditions are necessary because current methods lack the ability to learn the behavior of both SUs and PUs with time. In this paper, a novel transfer learning (TL) approach is proposed, in which abstract knowledge about PUs and SUs is transferred from past time frames to improve the detection process at future time frames. The proposed approach extracts a high level representation for the environment at every time frame. This high level information is accumulated to form an abstract knowledge database. The CR system then utilizes this database to accurately detect PUE attacks even if an insufficient amount of fingerprint data is available at the current time frame. The dynamic structure of the proposed approach uses the final detection decisions to update the abstract knowledge database for future runs. Simulation results show that the proposed method can improve the performance with an average of 3.5% for only 10% relevant information between the past knowledge and the current environment signals.
SOS rule formats for convex and abstract probabilistic bisimulations
Venue: arXiv cs.LO 2015
Year: 2015

Probabilistic transition system specifications (PTSSs) in the $nt μfθ/ ntμxθ$ format provide structural operational semantics for Segala-type systems that exhibit both probabilistic and nondeterministic behavior and guarantee that bisimilarity is a congruence for all operator defined in such format. Starting from the $nt μfθ/ ntμxθ$ format, we obtain restricted formats that guarantee that three coarser bisimulation equivalences are congruences. We focus on (i) Segala's variant of bisimulation that considers combined transitions, which we call here "convex bisimulation"; (ii) the bisimulation equivalence resulting from considering Park & Milner's bisimulation on the usual stripped probabilistic transition system (translated into a labelled transition system), which we call here "probability obliterated bisimulation"; and (iii) a "probability abstracted bisimulation", which, like bisimulation, preserves the structure of the distributions but instead, it ignores the probability values. In addition, we compare these bisimulation equivalences and provide a logic characterization for each of them.
ThreadPoolComposer - An Open-Source FPGA Toolchain for Software Developers
Venue: arXiv cs.DC 2015
Year: 2015

This extended abstract presents ThreadPoolComposer, a high-level synthesis-based development framework and meta-toolchain that provides a uniform programming interface for FPGAs portable across multiple platforms.
Framework for Application Mapping over Packet-Switched Network of FPGAs: Case Studies
Venue: arXiv cs.DC 2015
Year: 2015

The algorithm-to-hardware High-level synthesis (HLS) tools today are purported to produce hardware comparable in quality to handcrafted designs, particularly with user directive driven or domains specific HLS. However, HLS tools are not readily equipped for when an application/algorithm needs to scale. We present a (work-in-progress) semi-automated framework to map applications over a packet-switched network of modules (single FPGA) and then to seamlessly partition such a network over multiple FPGAs over quasi-serial links. We illustrate the framework through three application case studies: LDPC Decoding, Particle Filter based Object Tracking, and Matrix Vector Multiplication over GF(2). Starting with high-level representations of each case application, we first express them in an intermediate message passing formulation, a model of communicating processing elements. Once the processing elements are identified, these are either handcrafted or realized using HLS. The rest of the flow is automated where the processing elements are plugged on to a configurable network-on-chip (CONNECT) topology of choice, followed by partitioning the 'on-chip' links to work seamlessly across chips/FPGAs.
On Deciding Local Theory Extensions via E-matching
Venue: arXiv cs.LO 2015
Year: 2015

Satisfiability Modulo Theories (SMT) solvers incorporate decision procedures for theories of data types that commonly occur in software. This makes them important tools for automating verification problems. A limitation frequently encountered is that verification problems are often not fully expressible in the theories supported natively by the solvers. Many solvers allow the specification of application-specific theories as quantified axioms, but their handling is incomplete outside of narrow special cases. In this work, we show how SMT solvers can be used to obtain complete decision procedures for local theory extensions, an important class of theories that are decidable using finite instantiation of axioms. We present an algorithm that uses E-matching to generate instances incrementally during the search, significantly reducing the number of generated instances compared to eager instantiation strategies. We have used two SMT solvers to implement this algorithm and conducted an extensive experimental evaluation on benchmarks derived from verification conditions for heap-manipulating programs. We believe that our results are of interest to both the users of SMT solvers as well as their developers.
The complexity of the Clar number problem and an FPT algorithm
Venue: arXiv cs.DM 2015
Year: 2015

The Clar number of a (hydro)carbon molecule, introduced by Clar [E. Clar, \emph{The aromatic sextet}, (1972).], is the maximum number of mutually disjoint resonant hexagons in the molecule. Calculating the Clar number can be formulated as an optimization problem on 2-connected planar graphs. Namely, it is the maximum number of mutually disjoint even faces a perfect matching can simultaneously alternate on. It was proved by Abeledo and Atkinson [H. G. Abeledo and G. W. Atkinson, \emph{Unimodularity of the clar number problem}, Linear algebra and its applications \textbf{420} (2007), no. 2, 441--448] that the Clar number can be computed in polynomial time if the plane graph has even faces only. We prove that calculating the Clar number in general 2-connected plane graphs is NP-hard. We also prove NP-hardness of the maximum independent set problem for 2-connected plane graphs with odd faces only, which may be of independent interest. Finally, we give an FPT algorithm that determines the Clar number of a given 2-connected plane graph. The parameter of the algorithm is the length of the shortest odd join in the planar dual graph. For fullerenes this is not yet a polynomial algorithm, but for certain carbon nanotubes it gives an efficient algorithm.
On Convergence Rate of Leader-Following Consensus of Linear Multi-Agent Systems with Communication Noises
Venue: arXiv cs.SY 2015
Year: 2015

This note further studies the previously proposed consensus protocol for linear multi-agent systems with communication noises in [15], [16]. Each agent is allowed to have its own time-varying gain to attenuate the effect of communication noises. Therefore, the common assumption in most references that all agents have the same noise-attenuation gain is not necessary. It has been proved that if all noise-attenuation gains are infinitesimal of the same order, then the mean square leader-following consensus can be reached. Furthermore, the convergence rate of the multi-agent system has been investigated. If the noise-attenuation gains belong to a class of functions which are bounded above and below by $t^{-β}$ $(β\in(0,1))$ asymptotically, then the states of all follower agents are convergent in mean square to the leader's state with the rate characterized by a function bounded above by $t^{-β}$ asymptotically.
ChirpCast: Data Transmission via Audio
Venue: arXiv cs.NI 2015
Year: 2015

In this paper we present ChirpCast, a system for broadcasting network access keys to laptops ultrasonically. This work explores several modulation techniques for sending and receiving data using sound waves through commodity speakers and built-in laptop microphones. Requiring only that laptop users run a small application, the system successfully provides robust room-specific broadcasting at data rates of 200 bits/second.
RIPL: An Efficient Image Processing DSL for FPGAs
Venue: arXiv cs.DC 2015
Year: 2015

Field programmable gate arrays (FPGAs) can accelerate image processing by exploiting fine-grained parallelism opportunities in image operations. FPGA language designs are often subsets or extensions of existing languages, though these typically lack suitable hardware computation models so compiling them to FPGAs leads to inefficient designs. Moreover, these languages lack image processing domain specificity. Our solution is RIPL, an image processing domain specific language (DSL) for FPGAs. It has algorithmic skeletons to express image processing, and these are exploited to generate deep pipelines of highly concurrent and memory-efficient image processing components.
Using System Hyper Pipelining (SHP) to Improve the Performance of a Coarse-Grained Reconfigurable Architecture (CGRA) Mapped on an FPGA
Venue: arXiv cs.AR 2015
Year: 2015

The well known method C-Slow Retiming (CSR) can be used to automatically convert a given CPU into a multithreaded CPU with independent threads. These CPUs are then called streaming or barrel processors. System Hyper Pipelining (SHP) adds a new flexibility on top of CSR by allowing a dynamic number of threads to be executed and by enabling the threads to be stalled, bypassed and reordered. SHP is now applied on the programming elements (PE) of a coarse-grained reconfigurable architecture (CGRA). By using SHP, more performance can be achieved per PE. Fork-Join operations can be implemented on a PE using the flexibility provided by SHP to dynamically adjust the number of threads per PE. Multiple threads can share the same data locally, which greatly reduces the data traffic load on the CGRA's routing structure. The paper shows the results of a CGRA using SHP-ed RISC-V cores as PEs implemented on a FPGA.
Fast Factorization of Cartesian products of Hypergraphs
Venue: arXiv cs.DM 2015
Year: 2015

Cartesian products of graphs and hypergraphs have been studied since the 1960s. For (un)directed hypergraphs, unique \emph{prime factor decomposition (PFD)} results with respect to the Cartesian product are known. However, there is still a lack of algorithms, that compute the PFD of directed hypergraphs with respect to the Cartesian product. In this contribution, we focus on the algorithmic aspects for determining the Cartesian prime factors of a finite, connected, directed hypergraph and present a first polynomial time algorithm to compute its PFD. In particular, the algorithm has time complexity $O(|E||V|r^2)$ for hypergraphs $H=(V,E)$, where the rank $r$ is the maximum number of vertices contained in an hyperedge of $H$. If $r$ is bounded, then this algorithm performs even in $O(|E|\log^2(|V|))$ time. Thus, our method additionally improves also the time complexity of PFD-algorithms designed for undirected hypergraphs that have time complexity $O(|E||V|r^6Δ^6)$, where $Δ$ is the maximum number of hyperedges a vertex is contained in.
Dynamic State Estimation under Cyber Attacks: A Comparative Study of Kalman Filters and Observers
Venue: arXiv cs.SY 2015
Year: 2015

Utilizing highly synchronized measurements from synchrophasors, dynamic state estimation (DSE) can be applied for real-time monitoring of smart grids. Concurrent DSE studies for power systems are intolerant to unknown inputs and potential attack vectors --- a research gap we will fill in this work. Particularly, we (a) present an overview of concurrent estimation techniques, highlighting key deficiencies, (b) develop DSE methods based on cubature Kalman filter and dynamic observers, (c) rigorously examine the strengths and weaknesses of the proposed methods under attack-vectors and unknown inputs, and (d) provide comprehensive recommendations for DSE. Numerical results and in-depth remarks are also presented.
Market Formation as Transitive Closure: the Evolving Pattern of Trade in Music
Venue: arXiv cs.SI 2015
Year: 2015

Where do new markets come from? I construct a network model in which national markets are nodes and flows of recorded music between them are links and conduct a longitudinal analysis of the global pattern of trade in the period 1976 to 2010. I hypothesize that new export markets are developed through a process of transitive closure in the network of international trade. When two countries' markets experience the same social influences, it brings them close enough together for new homophilous ties to be formed. The implication is that consumption of foreign products helps, not hurts, home-market producers develop overseas markets, but only in those countries that have a history of consuming the same foreign products that were consumed in the home market. Selling in a market changes what is valued in that market, and new market formation is a consequence of having social influences in common.
D4M: Bringing Associative Arrays to Database Engines
Venue: arXiv cs.DB 2015
Year: 2015

The ability to collect and analyze large amounts of data is a growing problem within the scientific community. The growing gap between data and users calls for innovative tools that address the challenges faced by big data volume, velocity and variety. Numerous tools exist that allow users to store, query and index these massive quantities of data. Each storage or database engine comes with the promise of dealing with complex data. Scientists and engineers who wish to use these systems often quickly find that there is no single technology that offers a panacea to the complexity of information. When using multiple technologies, however, there is significant trouble in designing the movement of information between storage and database engines to support an end-to-end application along with a steep learning curve associated with learning the nuances of each underlying technology. In this article, we present the Dynamic Distributed Dimensional Data Model (D4M) as a potential tool to unify database and storage engine operations. Previous articles on D4M have showcased the ability of D4M to interact with the popular NoSQL Accumulo database. Recently however, D4M now operates on a variety of backend storage or database engines while providing a federated look to the end user through the use of associative arrays. In order to showcase how new databases may be supported by D4M, we describe the process of building the D4M-SciDB connector and present performance of this connection.
Towards Automated Performance Optimization of BPMN Business Processes
Venue: arXiv cs.DB 2015
Year: 2015

Business Process Model and Notation (BPMN) provides a standard for the design of business processes. It focuses on bridging the gap between the analysis and the technical perspectives, and aims to deliver process automation. The aim of this technical report is to complement this effort by transferring knowledge from the related field of data-centric workflows aiming to provide automated performance optimization of the business process execution. Automated optimization lifts a burden from BPMN designers and increases workflow flexibility and resilience. As a key step towards this goal, the contribution of this work is to provide a methodology to map BPMNv2.0 models to annotated directed acyclic graphs, which emphasize the volume of the tokens exchanged and are amenable to existing automated optimization algorithms. In addition, concrete examples of mappings are given, while the optimization opportunities that are opened are explained, thus providing insights into the potential performance benefits and we discuss technical research issues.