OpenRaiser/Intern-Atlas huggingface dataset:
Metric $1$-median selection: Query complexity vs. approximation ratio
Venue: arXiv cs.CC 2015
Year: 2015

Consider the problem of finding a point in a metric space $(\{1,2,\ldots,n\},d)$ with the minimum average distance to other points. We show that this problem has no deterministic $o(n^{1+1/(h-1)})$-query $(2h-Ω(1))$-approximation algorithms for any constant $h\in\mathbb{Z}^+\setminus\{1\}$.
Building a Pilot Software Quality-in-Use Benchmark Dataset
Venue: arXiv cs.SE 2015
Year: 2015

Prepared domain specific datasets plays an important role to supervised learning approaches. In this article a new sentence dataset for software quality-in-use is proposed. Three experts were chosen to annotate the data using a proposed annotation scheme. Then the data were reconciled in a (no match eliminate) process to reduce bias. The Kappa, k statistics revealed an acceptable level of agreement; moderate to substantial agreement between the experts. The built data can be used to evaluate software quality-in-use models in sentiment analysis models. Moreover, the annotation scheme can be used to extend the current dataset.
Word, graph and manifold embedding from Markov processes
Venue: arXiv cs.CL 2015
Year: 2015

Continuous vector representations of words and objects appear to carry surprisingly rich semantic content. In this paper, we advance both the conceptual and theoretical understanding of word embeddings in three ways. First, we ground embeddings in semantic spaces studied in cognitive-psychometric literature and introduce new evaluation tasks. Second, in contrast to prior work, we take metric recovery as the key object of study, unify existing algorithms as consistent metric recovery methods based on co-occurrence counts from simple Markov random walks, and propose a new recovery algorithm. Third, we generalize metric recovery to graphs and manifolds, relating co-occurence counts on random walks in graphs and random processes on manifolds to the underlying metric to be recovered, thereby reconciling manifold estimation and embedding algorithms. We compare embedding algorithms across a range of tasks, from nonlinear dimensionality reduction to three semantic language tasks, including analogies, sequence completion, and classification.
Optimizing the Convergence Rate of the Continuous Time Quantum Consensus
Venue: arXiv cs.SY 2015
Year: 2015

Inspired by the recent developments in the fields of quantum distributed computing, quantum systems are analyzed as networks of quantum nodes to reduce the complexity of the analysis. This gives rise to the distributed quantum consensus algorithms. Focus of this paper is on optimizing the convergence rate of the continuous time quantum consensus algorithm over a quantum network with $N$ qudits. It is shown that the optimal convergence rate is independent of the value of $d$ in qudits. First by classifying the induced graphs as the Schreier graphs, they are categorized in terms of the partitions of integer $N$. Then establishing the intertwining relation between one level dominant partitions in the Hasse Diagram of integer $N$, it is proved that the spectrum of the induced graph corresponding to the dominant partition is included in that of the less dominant partition. Based on this result, the proof of the Aldous' conjecture is extended to all possible induced graphs and the original optimization problem is reduced to optimizing spectral gap of the smallest induced graph. By providing the analytical solution to semidefinite programming formulation of the obtained problem, closed-form expressions for the optimal results are provided for a wide range of topologies.
Structure Preserving Bisimilarity, Supporting an Operational Petri Net Semantics of CCSP
Venue: arXiv cs.LO 2015
Year: 2015

In 1987 Ernst-Rüdiger Olderog provided an operational Petri net semantics for a subset of CCSP, the union of Milner's CCS and Hoare's CSP. It assigns to each process term in the subset a labelled, safe place/transition net. To demonstrate the correctness of the approach, Olderog established agreement (1) with the standard interleaving semantics of CCSP up to strong bisimulation equivalence, and (2) with standard denotational interpretations of CCSP operators in terms of Petri nets up to a suitable semantic equivalence that fully respects the causal structure of nets. For the latter he employed a linear-time semantic equivalence, namely having the same causal nets. This paper strengthens (2), employing a novel branching-time version of this semantics---structure preserving bisimilarity---that moreover preserves inevitability. I establish that it is a congruence for the operators of CCSP.
Exploiting Reduction Rules and Data Structures: Local Search for Minimum Vertex Cover in Massive Graphs
Venue: arXiv cs.DS 2015
Year: 2015

The Minimum Vertex Cover (MinVC) problem is a well-known NP-hard problem. Recently there has been great interest in solving this problem on real-world massive graphs. For such graphs, local search is a promising approach to finding optimal or near-optimal solutions. In this paper we propose a local search algorithm that exploits reduction rules and data structures to solve the MinVC problem in such graphs. Experimental results on a wide range of real-word massive graphs show that our algorithm finds better covers than state-of-the-art local search algorithms for MinVC. Also we present interesting results about the complexities of some well-known heuristics.
Index Coded PSK Modulation
Venue: arXiv cs.IT 2015
Year: 2015

In this paper we consider noisy index coding problem over AWGN channel. We give an algorithm to map the index coded bits to appropriate sized PSK symbols such that for the given index code, in general, the receiver with large amount of side information will gain in probability of error performance compared to the ones with lesser amount, depending upon the index code used. We call this the \textbf{PSK side information coding gain}. Also, we show that receivers with large amount of side information obtain this coding gain in addition to the bandwidth gain whereas receivers with lesser amount of side information trade off this coding gain with bandwidth gain. Moreover, in general, the difference between the best and worst performance among the receivers is shown to be proportional to the length of the index code employed.
Spotting Suspicious Reviews via (Quasi-)clique Extraction
Venue: arXiv cs.SI 2015
Year: 2015

How to tell if a review is real or fake? What does the underworld of fraudulent reviewing look like? Detecting suspicious reviews has become a major issue for many online services. We propose the use of a clique-finding approach to discover well-organized suspicious reviewers. From a Yelp dataset with over one million reviews, we construct multiple Reviewer Similarity graphs to link users that have unusually similar behavior: two reviewers are connected in the graph if they have reviewed the same set of venues within a few days. From these graphs, our algorithms extracted many large cliques and quasi-cliques, the largest one containing a striking 11 users who coordinated their review activities in identical ways. Among the detected cliques, a large portion contain Yelp Scouts who are paid by Yelp to review venues in new areas. Our work sheds light on their little-known operation.
Migration from Copper to Fiber Access Network using Passive Optical Network for Green and Dry Field Areas of Pakistan
Venue: arXiv cs.NI 2015
Year: 2015

Passive Optical Networks (PON) technology brings an evolution in the industry of Telecommunication for the provisioning of High Speed Internet (HSI) and Triple Play bundled Services that includes Voice, Data, and Video Streaming throughout the world. In Pakistan most of the service providers are offering broadband services on traditional copper OSP (Outside Plant) network since 2000. Demand for the high speed internet and broadband is increasing rapidly, it is desired with great need to migrate from traditional copper based OSP network to PON _ FTTx (Fiber To The x) infrastructure. Considering the geographical requirements in Pakistan a scalable fiber network is required which can be optimized as per the users requirements and demands with high speed bandwidth efficiency, involving the minimum losses and with ideal capital expenditure (CAPEX). In this work a platform for migration from copper to fiber access network with a scalable and optimized PON _ FTTx infrastructure in green field and dry field areas of Pakistan have been proposed using Geographic Information system (GIS). In any developing country like Pakistan having the same cultural and geographical topology, this platform can be used to migrate from copper to fiber access network to provide the PON based telecom services. The developed platform for migration from copper to PON based fiber has been studied, planned, and then simulated on a selected geographical area of Pakistan with physical execution that showed better and efficient results with reduction in capital and operational expenditures. A factual plan without ambiguities assists the operators of Pakistan to analyze and forecast bandwidth requirements of an area, optimized network planning along with the in time and efficient deployment.
Energy-Efficient Data Transmission with A Non-FIFO Packet
Venue: arXiv cs.NI 2015
Year: 2015

This paper investigates the problem of energy-efficient packet transmission with a non-FIFO Packet over a point-to-point additive white Gaussian noise (AWGN) time-invariant channel under the feasibility constraints. More specifically, we consider the scenario where there is a packet that has a deadline that is earlier than that of the previously arrived packet. For this problem, the First-In-First-Out (FIFO) transmission mode adopted in the existing literatures is no longer optimal. We first propose a novel packet split and reorder process which convert the inconsistency in the order of deadlines and arrival instants of the packet sequence into a consistent one. After the split and reorder process, the original problem considered in this paper is transformed into the problem of finding the optimal split factor. We propose an algorithm that finds the split factor which consists of checking four possibilities by applying the existing optimal transmission strategy \emph{"String Tautening"} for FIFO packets. In addition, we prove the optimality of the proposed algorithm in the presence of a non-FIFO packet by exploiting the optimality properties of the most energy efficient transmission strategy. Based on the proposed optimal offline scheme, an efficient online policy which assumes causal arrival information is also studied and shown to achieve a comparable performance to the proposed optimal offline scheme.
Botivist: Calling Volunteers to Action Using Online Bots
Venue: arXiv cs.SI 2015
Year: 2015

To help activists call new volunteers to action, we present Botivist: a platform that uses Twitter bots to find potential volunteers and request contributions. By leveraging different Twitter accounts, Botivist employs different strategies to encourage participation. We explore how people respond to bots calling them to action using a test case about corruption in Latin America. Our results show that the majority of volunteers (>80%) who responded to Botivist's calls to action contributed relevant proposals to address the assigned social problem. Different strategies produced differences in the quantity and relevance of contributions. Some strategies that work well offline and face-to-face appeared to hinder people's participation when used by an online bot. We analyze user behavior in response to being approached by bots with an activist purpose. We also provide strong evidence for the value of this type of civic media, and derive design implications.
Fix Your Types
Venue: arXiv cs.LO 2015
Year: 2015

When using existing ACL2 datatype frameworks, many theorems require type hypotheses. These hypotheses slow down the theorem prover, are tedious to write, and are easy to forget. We describe a principled approach to types that provides strong type safety and execution efficiency while avoiding type hypotheses, and we present a library that automates this approach. Using this approach, types help you catch programming errors and then get out of the way of theorem proving.
Second-Order Functions and Theorems in ACL2
Venue: arXiv cs.LO 2015
Year: 2015

SOFT ('Second-Order Functions and Theorems') is a tool to mimic second-order functions and theorems in the first-order logic of ACL2. Second-order functions are mimicked by first-order functions that reference explicitly designated uninterpreted functions that mimic function variables. First-order theorems over these second-order functions mimic second-order theorems universally quantified over function variables. Instances of second-order functions and theorems are systematically generated by replacing function variables with functions. SOFT can be used to carry out program refinement inside ACL2, by constructing a sequence of increasingly stronger second-order predicates over one or more target functions: the sequence starts with a predicate that specifies requirements for the target functions, and ends with a predicate that provides executable definitions for the target functions.
Extending ACL2 with SMT Solvers
Venue: arXiv cs.LO 2015
Year: 2015

We present our extension of ACL2 with Satisfiability Modulo Theories (SMT) solvers using ACL2's trusted clause processor mechanism. We are particularly interested in the verification of physical systems including Analog and Mixed-Signal (AMS) designs. ACL2 offers strong induction abilities for reasoning about sequences and SMT complements deduction methods like ACL2 with fast nonlinear arithmetic solving procedures. While SAT solvers have been integrated into ACL2 in previous work, SMT methods raise new issues because of their support for a broader range of domains including real numbers and uninterpreted functions. This paper presents Smtlink, our clause processor for integrating SMT solvers into ACL2. We describe key design and implementation issues and describe our experience with its use.
An Immersive Visualization Tool for Teaching and Simulation of Smart Grid Technologies
Venue: arXiv cs.HC 2015
Year: 2015

Intelligent power grid research, i.e. smart grid, involves many simultaneous users spread over a relatively large geographical area. A tool for advancing research and community education is presented utilizing large-scale visualization centers, e.g. planetariums, in simulating smart grid interactions. This approach immerses the user in virtual smart grid visualization and allows the user, with several other users, to interact in real time. This facilitates community education by demonstrating how the power grid functions with smart technologies. The simulation is sophisticated enough to also be used as a research tool for industry and higher education to test software algorithms, deployment strategies, communications protocols, and even new hardware.
Evaluating the visualization of what a Deep Neural Network has learned
Venue: arXiv cs.CV 2015
Year: 2015

Deep Neural Networks (DNNs) have demonstrated impressive performance in complex machine learning tasks such as image classification or speech recognition. However, due to their multi-layer nonlinear structure, they are not transparent, i.e., it is hard to grasp what makes them arrive at a particular classification or recognition decision given a new unseen data sample. Recently, several approaches have been proposed enabling one to understand and interpret the reasoning embodied in a DNN for a single test image. These methods quantify the ''importance'' of individual pixels wrt the classification decision and allow a visualization in terms of a heatmap in pixel/input space. While the usefulness of heatmaps can be judged subjectively by a human, an objective quality measure is missing. In this paper we present a general methodology based on region perturbation for evaluating ordered collections of pixels such as heatmaps. We compare heatmaps computed by three different methods on the SUN397, ILSVRC2012 and MIT Places data sets. Our main result is that the recently proposed Layer-wise Relevance Propagation (LRP) algorithm qualitatively and quantitatively provides a better explanation of what made a DNN arrive at a particular classification decision than the sensitivity-based approach or the deconvolution method. We provide theoretical arguments to explain this result and discuss its practical implications. Finally, we investigate the use of heatmaps for unsupervised assessment of neural network performance.
Information-theoretic bounds for exact recovery in weighted stochastic block models using the Renyi divergence
Venue: arXiv cs.IT 2015
Year: 2015

We derive sharp thresholds for exact recovery of communities in a weighted stochastic block model, where observations are collected in the form of a weighted adjacency matrix, and the weight of each edge is generated independently from a distribution determined by the community membership of its endpoints. Our main result, characterizing the precise boundary between success and failure of maximum likelihood estimation when edge weights are drawn from discrete distributions, involves the Renyi divergence of order $\frac{1}{2}$ between the distributions of within-community and between-community edges. When the Renyi divergence is above a certain threshold, meaning the edge distributions are sufficiently separated, maximum likelihood succeeds with probability tending to 1; when the Renyi divergence is below the threshold, maximum likelihood fails with probability bounded away from 0. In the language of graphical channels, the Renyi divergence pinpoints the information-theoretic capacity of discrete graphical channels with binary inputs. Our results generalize previously established thresholds derived specifically for unweighted block models, and support an important natural intuition relating the intrinsic hardness of community estimation to the problem of edge classification. Along the way, we establish a general relationship between the Renyi divergence and the probability of success of the maximum likelihood estimator for arbitrary edge weight distributions. Finally, we discuss consequences of our bounds for the related problems of censored block models and submatrix localization, which may be seen as special cases of the framework developed in our paper.
Three Practical Aspects of Massive MIMO: Intermittent User Activity, Pilot Synchronism, and Asymmetric Deployment
Venue: arXiv cs.IT 2015
Year: 2015

This paper considers three aspects of Massive MIMO (multiple-input multiple-output) communication networks that have received little attention in previous works, but are important to understand when designing and implementing this promising wireless technology. First, we analyze how bursty data traffic behaviors affect the system. Using a probabilistic model for intermittent user activity, we show that the spectral efficiency (SE) scales gracefully with reduced user activity. Then, we make an analytic comparison between synchronous and asynchronous pilot signaling, and prove that the choice between these has no impact on the SE. Finally, we provide an analytical and numerical study of the SE achieved with random network deployment.
Citizen Science practices for Computational Social Sciences research: The conceptualization of Pop-Up Experiments
Venue: arXiv cs.CY 2015
Year: 2015

Under the name of Citizen Science, many innovative practices in which volunteers partner with scientist to pose and answer real-world questions are quickly growing worldwide. Citizen Science can furnish ready made solutions with the active role of citizens. However, this framework is still far from being well stablished to become a standard tool for Computational Social Sciences research. We present our experience in bridging Computational Social Sciences with Citizen Science philosophy, which in our case has taken the form of what we call Pop-Up Experiments: Non-permanent, highly participatory collective experiments which blend features developed by Big Data methodologies and Behavioural Experiments protocols with ideals of Citizen Science. The main issues to take into account whenever planning experiments of this type are classified and discused grouped in three categories: public engagement, light infrastructure and knowledge return to citizens. We explain the solutions implemented providing practical examples grounded in our own experience in urban contexts (Barcelona, Spain). We hope that this work serves as guideline to groups willing to adopt and expand such \emph{in-vivo} practices and opens the debate about the possibilities (but also the limitations) that the Citizen Science framework can offer to study social phenomena.
Performance Analysis of Joint-Sparse Recovery from Multiple Measurements and Prior Information via Convex Optimization
Venue: arXiv cs.IT 2015
Year: 2015

We address the problem of compressed sensing with multiple measurement vectors associated with prior information in order to better reconstruct an original sparse matrix signal. $\ell_{2,1}-\ell_{2,1}$ minimization is used to emphasize co-sparsity property and similarity between matrix signal and prior information. We then derive the necessary and sufficient condition of successfully reconstructing the original signal and establish the lower and upper bounds of required measurements such that the condition holds from the perspective of conic geometry. Our bounds further indicates what prior information is helpful to improve the the performance of CS. Experimental results validates the effectiveness of all our findings.
Consensus-based control for a network of diffusion PDEs with boundary local interaction
Venue: arXiv cs.SY 2015
Year: 2015

In this paper the problem of driving the state of a network of identical agents, modeled by boundary-controlled heat equations, towards a common steady-state profile is addressed. Decentralized consensus protocols are proposed to address two distinct problems. The first problem is that of steering the states of all agents towards the same constant steady-state profile which corresponds to the spatial average of the agents initial condition. A linear local interaction rule addressing this requirement is given. The second problem deals with the case where the controlled boundaries of the agents dynamics are corrupted by additive persistent disturbances. To achieve synchronization between agents, while completely rejecting the effect of the boundary disturbances, a nonlinear sliding-mode based consensus protocol is proposed. Performance of the proposed local interaction rules are analyzed by applying a Lyapunov-based approach. Simulation results are presented to support the effectiveness of the proposed algorithms.