OpenRaiser/Intern-Atlas huggingface dataset:
Speeding up Glauber Dynamics for Random Generation of Independent Sets
Venue: arXiv cs.DM 2015
Year: 2015

The maximum independent set (MIS) problem is a well-studied combinatorial optimization problem that naturally arises in many applications, such as wireless communication, information theory and statistical mechanics. MIS problem is NP-hard, thus many results in the literature focus on fast generation of maximal independent sets of high cardinality. One possibility is to combine Gibbs sampling with coupling from the past arguments to detect convergence to the stationary regime. This results in a sampling procedure with time complexity that depends on the mixing time of the Glauber dynamics Markov chain. We propose an adaptive method for random event generation in the Glauber dynamics that considers only the events that are effective in the coupling from the past scheme, accelerating the convergence time of the Gibbs sampling algorithm.
A Picture Tells a Thousand Words -- About You! User Interest Profiling from User Generated Visual Content
Venue: arXiv cs.SI 2015
Year: 2015

Inference of online social network users' attributes and interests has been an active research topic. Accurate identification of users' attributes and interests is crucial for improving the performance of personalization and recommender systems. Most of the existing works have focused on textual content generated by the users and have successfully used it for predicting users' interests and other identifying attributes. However, little attention has been paid to user generated visual content (images) that is becoming increasingly popular and pervasive in recent times. We posit that images posted by users on online social networks are a reflection of topics they are interested in and propose an approach to infer user attributes from images posted by them. We analyze the content of individual images and then aggregate the image-level knowledge to infer user-level interest distribution. We employ image-level similarity to propagate the label information between images, as well as utilize the image category information derived from the user created organization structure to further propagate the category-level knowledge for all images. A real life social network dataset created from Pinterest is used for evaluation and the experimental results demonstrate the effectiveness of our proposed approach.
An Intermediate Language and Estimator for Automated Design Space Exploration on FPGAs
Venue: arXiv cs.DC 2015
Year: 2015

We present the TyTra-IR, a new intermediate language intended as a compilation target for high-level language compilers and a front-end for HDL code generators. We develop the requirements of this new language based on the design-space of FPGAs that it should be able to express and the estimation-space in which each configuration from the design-space should be mappable in an automated design flow. We use a simple kernel to illustrate multiple configurations using the semantics of TyTra-IR. The key novelty of this work is the cost model for resource-costs and throughput for different configurations of interest for a particular kernel. Through the realistic example of a Successive Over-Relaxation kernel implemented both in TyTra-IR and HDL, we demonstrate both the expressiveness of the IR and the accuracy of our cost model.
MISO Broadcast Channel with Hybrid CSIT: Beyond Two Users
Venue: arXiv cs.IT 2015
Year: 2015

We study the impact of heterogeneity of channel-state-information available at the transmitters (CSIT) on the capacity of broadcast channels with a multiple-antenna transmitter and $k$ single-antenna receivers (MISO BC). In particular, we consider the $k$-user MISO BC, where the CSIT with respect to each receiver can be either instantaneous/perfect, delayed, or not available; and we study the impact of this heterogeneity of CSIT on the degrees-of-freedom (DoF) of such network. We first focus on the $3$-user MISO BC; and we completely characterize the DoF region for all possible heterogeneous CSIT configurations, assuming linear encoding strategies at the transmitters. The result shows that the state-of-the-art achievable schemes in the literature are indeed sum-DoF optimal, when restricted to linear encoding schemes. To prove the result, we develop a novel bound, called Interference Decomposition Bound, which provides a lower bound on the interference dimension at a receiver which supplies delayed CSIT based on the average dimension of constituents of that interference, thereby decomposing the interference into its individual components. Furthermore, we extend our outer bound on the DoF region to the general $k$-user MISO BC, and demonstrate that it leads to an approximate characterization of linear sum-DoF to within an additive gap of $0.5$ for a broad range of CSIT configurations. Moreover, for the special case where only one receiver supplies delayed CSIT, we completely characterize the linear sum-DoF.
Performance Evaluation of Machine Learning Algorithms in Post-operative Life Expectancy in the Lung Cancer Patients
Venue: arXiv cs.LG 2015
Year: 2015

The nature of clinical data makes it difficult to quickly select, tune and apply machine learning algorithms to clinical prognosis. As a result, a lot of time is spent searching for the most appropriate machine learning algorithms applicable in clinical prognosis that contains either binary-valued or multi-valued attributes. The study set out to identify and evaluate the performance of machine learning classification schemes applied in clinical prognosis of post-operative life expectancy in the lung cancer patients. Multilayer Perceptron, J48, and the Naive Bayes algorithms were used to train and test models on Thoracic Surgery datasets obtained from the University of California Irvine machine learning repository. Stratified 10-fold cross-validation was used to evaluate baseline performance accuracy of the classifiers. The comparative analysis shows that multilayer perceptron performed best with classification accuracy of 82.3%, J48 came out second with classification accuracy of 81.8%, and Naive Bayes came out the worst with classification accuracy of 74.4%. The quality and outcome of the chosen machine learning algorithms depends on the ingenuity of the clinical miner.
Local, Private, Efficient Protocols for Succinct Histograms
Venue: arXiv cs.CR 2015
Year: 2015

We give efficient protocols and matching accuracy lower bounds for frequency estimation in the local model for differential privacy. In this model, individual users randomize their data themselves, sending differentially private reports to an untrusted server that aggregates them. We study protocols that produce a succinct histogram representation of the data. A succinct histogram is a list of the most frequent items in the data (often called "heavy hitters") along with estimates of their frequencies; the frequency of all other items is implicitly estimated as 0. If there are $n$ users whose items come from a universe of size $d$, our protocols run in time polynomial in $n$ and $\log(d)$. With high probability, they estimate the accuracy of every item up to error $O\left(\sqrt{\log(d)/(ε^2n)}\right)$ where $ε$ is the privacy parameter. Moreover, we show that this much error is necessary, regardless of computational efficiency, and even for the simple setting where only one item appears with significant frequency in the data set. Previous protocols (Mishra and Sandler, 2006; Hsu, Khanna and Roth, 2012) for this task either ran in time $Ω(d)$ or had much worse error (about $\sqrt[6]{\log(d)/(ε^2n)}$), and the only known lower bound on error was $Ω(1/\sqrt{n})$. We also adapt a result of McGregor et al (2010) to the local setting. In a model with public coins, we show that each user need only send 1 bit to the server. For all known local protocols (including ours), the transformation preserves computational efficiency.
Power Splitting for Full-Duplex Relay with Wireless Information and Power Transfer
Venue: arXiv cs.IT 2015
Year: 2015

This paper investigates power splitting for full-duplex relay networks with wireless information and energy transfer. By applying power splitting as a relay transceiver architecture, the full duplex information relaying can be powered by energy harvested from the source-emitted radio frequency signal. In order to minimize outage probability, power splitting ratios have been dynamically optimized according to full channel state information (CSI) and partial CSI, respectively. Under strong loop interference, the proposed full CSI-based and partial CSI-based power splitting schemes achieve the better outage performance than the fixed power splitting scheme, whereas the partial CSI-based power splitting scheme can ensure competitive outage performance without requiring CSI of the second-hop link. It is also observed that the worst outage performance is achieved when the relay is located midway between the source and destination, whereas the outage performance of partial CSI-based power splitting scheme approaches that of full CSI-based scheme when the relay is placed close to the destination.
Towards Detecting Rumours in Social Media
Venue: arXiv cs.SI 2015
Year: 2015

The spread of false rumours during emergencies can jeopardise the well-being of citizens as they are monitoring the stream of news from social media to stay abreast of the latest updates. In this paper, we describe the methodology we have developed within the PHEME project for the collection and sampling of conversational threads, as well as the tool we have developed to facilitate the annotation of these threads so as to identify rumourous ones. We describe the annotation task conducted on threads collected during the 2014 Ferguson unrest and we present and analyse our findings. Our results show that we can collect effectively social media rumours and identify multiple rumours associated with a range of stories that would have been hard to identify by relying on existing techniques that need manual input of rumour-specific keywords.
Full Large-Scale Diversity Space Codes for MIMO Optical Wireless Communications
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we consider a multiple-input-multiple-output optical wireless communication (MIMO-OWC) system suffering from log-normal fading. In this scenario, a general criterion for the design of full large-scale diversity space code (FLDSC) with the maximum likelihood (ML) detector is developed. Based on our criterion, FLDSC is attained if and only if all the entries of the space coding matrix are positive. Particularly for $2\times 2$ MIMO-OWC with unipolar pulse amplitude modulation (PAM), a closed-form linear FLDSC satisfying this criterion is attained by smartly taking advantage of some available properties as well as by developing some new interesting properties on Farey sequences in number theory to rigorously attack the continuous and discrete variables mixed max-min problem. In fact, this specific design not only proves that a repetition code (RC) is the best linear FLDSC, but also uncovers a significant difference between MIMO radio frequency (RF) communications and MIMO-OWC that space-only transmission is sufficient for a full diversity achievement. Computer simulations demonstrate that FLDSC substantially outperforms spatial multiplexing with the same total optical power and spectral efficiency and the latter obtains only the small-scale diversity gain.
Infection Spreading and Source Identification: A Hide and Seek Game
Venue: arXiv cs.SI 2015
Year: 2015

The goal of an infection source node (e.g., a rumor or computer virus source) in a network is to spread its infection to as many nodes as possible, while remaining hidden from the network administrator. On the other hand, the network administrator aims to identify the source node based on knowledge of which nodes have been infected. We model the infection spreading and source identification problem as a strategic game, where the infection source and the network administrator are the two players. As the Jordan center estimator is a minimax source estimator that has been shown to be robust in recent works, we assume that the network administrator utilizes a source estimation strategy that can probe any nodes within a given radius of the Jordan center. Given any estimation strategy, we design a best-response infection strategy for the source. Given any infection strategy, we design a best-response estimation strategy for the network administrator. We derive conditions under which a Nash equilibrium of the strategic game exists. Simulations in both synthetic and real-world networks demonstrate that our proposed infection strategy infects more nodes while maintaining the same safety margin between the true source node and the Jordan center source estimator.
Can Intellectual Processes in the Sciences Also Be Simulated? The Anticipation and Visualization of Possible Future States
Venue: arXiv cs.DL 2015
Year: 2015

Socio-cognitive action reproduces and changes both social and cognitive structures. The analytical distinction between these dimensions of structure provides us with richer models of scientific development. In this study, I assume that (i) social structures organize expectations into belief structures that can be attributed to individuals and communities; (ii) expectations are specified in scholarly literature; and (iii) intellectually the sciences (disciplines, specialties) tend to self-organize as systems of rationalized expectations. Whereas social organizations remain localized, academic writings can circulate, and expectations can be stabilized and globalized using symbolically generalized codes of communication. The intellectual restructuring, however, remains latent as a second-order dynamics that can be accessed by participants only reflexively. Yet, the emerging "horizons of meaning" provide feedback to the historically developing organizations by constraining the possible future states as boundary conditions. I propose to model these possible future states using incursive and hyper-incursive equations from the computation of anticipatory systems. Simulations of these equations enable us to visualize the couplings among the historical--i.e., recursive--progression of social structures along trajectories, the evolutionary--i.e., hyper-incursive--development of systems of expectations at the regime level, and the incursive instantiations of expectations in actions, organizations, and texts.
Information Hiding as a Challenge for Malware Detection
Venue: arXiv cs.CR 2015
Year: 2015

Information hiding techniques are increasingly utilized by the current malware to hide its existence and communication attempts. In this paper we highlight this new trend by reviewing the most notable examples of malicious software that shows this capability.
Illuminating search spaces by mapping elites
Venue: arXiv cs.AI 2015
Year: 2015

Many fields use search algorithms, which automatically explore a search space to find high-performing solutions: chemists search through the space of molecules to discover new drugs; engineers search for stronger, cheaper, safer designs, scientists search for models that best explain data, etc. The goal of search algorithms has traditionally been to return the single highest-performing solution in a search space. Here we describe a new, fundamentally different type of algorithm that is more useful because it provides a holistic view of how high-performing solutions are distributed throughout a search space. It creates a map of high-performing solutions at each point in a space defined by dimensions of variation that a user gets to choose. This Multi-dimensional Archive of Phenotypic Elites (MAP-Elites) algorithm illuminates search spaces, allowing researchers to understand how interesting attributes of solutions combine to affect performance, either positively or, equally of interest, negatively. For example, a drug company may wish to understand how performance changes as the size of molecules and their cost-to-produce vary. MAP-Elites produces a large diversity of high-performing, yet qualitatively different solutions, which can be more helpful than a single, high-performing solution. Interestingly, because MAP-Elites explores more of the search space, it also tends to find a better overall solution than state-of-the-art search algorithms. We demonstrate the benefits of this new algorithm in three different problem domains ranging from producing modular neural networks to designing simulated and real soft robots. Because MAP- Elites (1) illuminates the relationship between performance and dimensions of interest in solutions, (2) returns a set of high-performing, yet diverse solutions, and (3) improves finding a single, best solution, it will advance science and engineering.
A new separation theorem with geometric applications
Venue: arXiv cs.CG 2015
Year: 2015

Let $G=(V(G), E(G))$ be an undirected graph with a measure function $μ$ assigning non-negative values to subgraphs $H$ so that $μ(H)$ does not exceed the clique cover number of $H$. When $μ$ satisfies some additional natural conditions, we study the problem of separating $G$ into two subgraphs, each with a measure of at most $2μ(G)/3$ by removing a set of vertices that can be covered with a small number of cliques $G$. When $E(G)=E(G_1)\cap E(G_2)$, where $G_1=(V(G_1),E(G_1))$ is a graph with $V(G_1)=V(G)$, and $G_2=(V(G_2), E(G_2))$ is a chordal graph with $V(G_2)=V(G)$, we prove that there is a separator $S$ that can be covered with $O(\sqrt{lμ(G)})$ cliques in $G$, where $l=l(G,G_1)$ is a parameter similar to the bandwidth, which arises from the linear orderings of cliques covers in $G_1$. The results and the methods are then used to obtain exact and approximate algorithms which significantly improve some of the past results for several well known NP-hard geometric problems. In addition, the methods involve introducing new concepts and hence may be of an independent interest.
A Framework for General Sparse Matrix-Matrix Multiplication on GPUs and Heterogeneous Processors
Venue: arXiv cs.MS 2015
Year: 2015

General sparse matrix-matrix multiplication (SpGEMM) is a fundamental building block for numerous applications such as algebraic multigrid method (AMG), breadth first search and shortest path problem. Compared to other sparse BLAS routines, an efficient parallel SpGEMM implementation has to handle extra irregularity from three aspects: (1) the number of nonzero entries in the resulting sparse matrix is unknown in advance, (2) very expensive parallel insert operations at random positions in the resulting sparse matrix dominate the execution time, and (3) load balancing must account for sparse data in both input matrices. In this work we propose a framework for SpGEMM on GPUs and emerging CPU-GPU heterogeneous processors. This framework particularly focuses on the above three problems. Memory pre-allocation for the resulting matrix is organized by a hybrid method that saves a large amount of global memory space and efficiently utilizes the very limited on-chip scratchpad memory. Parallel insert operations of the nonzero entries are implemented through the GPU merge path algorithm that is experimentally found to be the fastest GPU merge approach. Load balancing builds on the number of necessary arithmetic operations on the nonzero entries and is guaranteed in all stages. Compared with the state-of-the-art CPU and GPU SpGEMM methods, our approach delivers excellent absolute performance and relative speedups on various benchmarks multiplying matrices with diverse sparsity structures. Furthermore, on heterogeneous processors, our SpGEMM approach achieves higher throughput by using re-allocatable shared virtual memory. The source code of this work is available at https://github.com/bhSPARSE/Benchmark_SpGEMM_using_CSR
Task-Based Algorithm for Matrix Multiplication: A Step Towards Block-Sparse Tensor Computing
Venue: arXiv cs.DC 2015
Year: 2015

Distributed-memory matrix multiplication (MM) is a key element of algorithms in many domains (machine learning, quantum physics). Conventional algorithms for dense MM rely on regular/uniform data decomposition to ensure load balance. These traits conflict with the irregular structure (block-sparse or rank-sparse within blocks) that is increasingly relevant for fast methods in quantum physics. To deal with such irregular data we present a new MM algorithm based on Scalable Universal Matrix Multiplication Algorithm (SUMMA). The novel features are: (1) multiple-issue scheduling of SUMMA iterations, and (2) fine-grained task-based formulation. The latter eliminates the need for explicit internodal synchronization; with multiple-iteration scheduling this allows load imbalance due to nonuniform matrix structure. For square MM with uniform and nonuniform block sizes (the latter simulates matrices with general irregular structure) we found excellent performance in weak and strong-scaling regimes, on commodity and high-end hardware.
Approximate Regularization Paths for Nuclear Norm Minimization Using Singular Value Bounds -- With Implementation and Extended Appendix
Venue: arXiv cs.SY 2015
Year: 2015

The widely used nuclear norm heuristic for rank minimization problems introduces a regularization parameter which is difficult to tune. We have recently proposed a method to approximate the regularization path, i.e., the optimal solution as a function of the parameter, which requires solving the problem only for a sparse set of points. In this paper, we extend the algorithm to provide error bounds for the singular values of the approximation. We exemplify the algorithms on large scale benchmark examples in model order reduction. Here, the order of a dynamical system is reduced by means of constrained minimization of the nuclear norm of a Hankel matrix.
On the complexity of computing prime tables
Venue: arXiv cs.CC 2015
Year: 2015

Many large arithmetic computations rely on tables of all primes less than $n$. For example, the fastest algorithms for computing $n!$ takes time $O(M(n\log n) + P(n))$, where $M(n)$ is the time to multiply two $n$-bit numbers, and $P(n)$ is the time to compute a prime table up to $n$. The fastest algorithm to compute $\binom{n}{n/2}$ also uses a prime table. We show that it takes time $O(M(n) + P(n))$. In various models, the best bound on $P(n)$ is greater than $M(n\log n)$, given advances in the complexity of multiplication \cite{Furer07,De08}. In this paper, we give two algorithms to computing prime tables and analyze their complexity on a multitape Turing machine, one of the standard models for analyzing such algorithms. These two algorithms run in time $O(M(n\log n))$ and $O(n\log^2 n/\log \log n)$, respectively. We achieve our results by speeding up Atkin's sieve. Given that the current best bound on $M(n)$ is $n\log n 2^{O(\log^*n)}$, the second algorithm is faster and improves on the previous best algorithm by a factor of $\log^2\log n$. Our fast prime-table algorithms speed up both the computation of $n!$ and $\binom{n}{n/2}$. Finally, we show that computing the factorial takes $Ω(M(n \log^{4/7 - ε} n))$ for any constant $ε> 0$ assuming only multiplication is allowed.