OpenRaiser/Intern-Atlas huggingface dataset:
Live Inspection of Spreadsheets
Venue: arXiv cs.SE 2015
Year: 2015

Existing approaches for detecting anomalies in spreadsheets can help to discover faults, but they are often applied too late in the spreadsheet lifecycle. By contrast, our approach detects anomalies immediately whenever users change their spreadsheets. This live inspection approach has been implemented as part of the Spreadsheet Inspection Framework, enabling the tool to visually report findings without disturbing the users' workflow. An advanced list representation allows users to keep track of the latest findings, prioritize open problems, and check progress on solving the issues. Results from a first user study indicate that users find the approach useful.
Dominating induced matchings in graphs containing no long claw
Venue: arXiv cs.DM 2015
Year: 2015

An induced matching $M$ in a graph $G$ is dominating if every edge not in $M$ shares exactly one vertex with an edge in $M$. The dominating induced matching problem (also known as efficient edge domination) asks whether a graph $G$ contains a dominating induced matching. This problem is generally NP-complete, but polynomial-time solvable for graphs with some special properties. In particular, it is solvable in polynomial time for claw-free graphs. In the present paper, we study this problem for graphs containing no long claw, i.e. no induced subgraph obtained from the claw by subdividing each of its edges exactly once. To solve the problem in this class, we reduce it to the following question: given a graph $G$ and a subset of its vertices, does $G$ contain a matching saturating all vertices of the subset? We show that this question can be answered in polynomial time, thus providing a polynomial-time algorithm to solve the dominating induced matching problem for graphs containing no long claw.
Performance analysis of the Kahan-enhanced scalar product on current multicore processors
Venue: arXiv cs.PF 2015
Year: 2015

We investigate the performance characteristics of a numerically enhanced scalar product (dot) kernel loop that uses the Kahan algorithm to compensate for numerical errors, and describe efficient SIMD-vectorized implementations on recent Intel processors. Using low-level instruction analysis and the execution-cache-memory (ECM) performance model we pinpoint the relevant performance bottlenecks for single-core and thread-parallel execution, and predict performance and saturation behavior. We show that the Kahan-enhanced scalar product comes at almost no additional cost compared to the naive (non-Kahan) scalar product if appropriate low-level optimizations, notably SIMD vectorization and unrolling, are applied. We also investigate the impact of architectural changes across four generations of Intel Xeon processors.
Multi-Agent Distributed Coordination Control: Developments and Directions
Venue: arXiv cs.MA 2015
Year: 2015

In this paper, the recent developments on distributed coordination control, especially the consensus and formation control, are summarized with the graph theory playing a central role, in order to present a cohesive overview of the multi-agent distributed coordination control, together with brief reviews of some closely related issues including rendezvous/alignment, swarming/flocking and containment control.In terms of the consensus problem, the recent results on consensus for the agents with different dynamics from first-order, second-order to high-order linear and nonlinear dynamics, under different communication conditions, such as cases with/without switching communication topology and varying time-delays, are reviewed, in which the algebraic graph theory is very useful in the protocol designs, stability proofs and converging analysis. In terms of the formation control problem, after reviewing the results of the algebraic graph theory employed in the formation control, we mainly pay attention to the developments of the rigid and persistent graphs. With the notions of rigidity and persistence, the formation transformation, splitting and reconstruction can be completed, and consequently the range-based formation control laws are designed with the least required information in order to maintain a formation rigid/persistent. Afterwards, the recent results on rendezvous/alignment, swarming/flocking and containment control, which are very closely related to consensus and formation control, are briefly introduced, in order to present an integrated view of the graph theory used in the coordination control problem. Finally, towards the practical applications, some directions possibly deserving investigation in coordination control are raised as well.
Unbounded-Thread Reachability via Symbolic Execution and Loop Acceleration (Technical Report)
Venue: arXiv cs.LO 2015
Year: 2015

We present an approach to parameterized reachability for communicating finite-state threads that formulates the analysis as a satisfiability problem. In addition to the unbounded number of threads, the main challenge for SAT/SMT-based reachability methods is the existence of unbounded loops in the program executed by a thread. We show in this paper how simple loops can be accelerated without approximation into Presburger arithmetic constraints. The constraints are obtained via symbolic execution and are satisfiable exactly if the given program state is reachable. We summarize loops nested inside other loops using recurrence relations derived from the inner loop's acceleration. This summary abstracts the loop iteration parameter and may thus overapproximate. An advantage of our symbolic approach is that the process of building the Presburger formulas may instantly reveal their unsatisfiability, before any arithmetic has been performed. We demonstrate the power of this technique for proving and refuting safety properties of unbounded-thread programs and other infinite-state transition systems.
Featherweight PINQ
Venue: arXiv cs.PL 2015
Year: 2015

Differentially private mechanisms enjoy a variety of composition properties. Leveraging these, McSherry introduced PINQ (SIGMOD 2009), a system empowering non-experts to construct new differentially private analyses. PINQ is an LINQ-like API which provides automatic privacy guarantees for all programs which use it to mediate sensitive data manipulation. In this work we introduce featherweight PINQ, a formal model capturing the essence of PINQ. We prove that any program interacting with featherweight PINQ's API is differentially private.
Long-Run Average Behaviour of Probabilistic Vector Addition Systems
Venue: arXiv cs.LO 2015
Year: 2015

We study the pattern frequency vector for runs in probabilistic Vector Addition Systems with States (pVASS). Intuitively, each configuration of a given pVASS is assigned one of finitely many patterns, and every run can thus be seen as an infinite sequence of these patterns. The pattern frequency vector assigns to each run the limit of pattern frequencies computed for longer and longer prefixes of the run. If the limit does not exist, then the vector is undefined. We show that for one-counter pVASS, the pattern frequency vector is defined and takes only finitely many values for almost all runs. Further, these values and their associated probabilities can be approximated up to an arbitrarily small relative error in polynomial time. For stable two-counter pVASS, we show the same result, but we do not provide any upper complexity bound. As a byproduct of our study, we discover counterexamples falsifying some classical results about stochastic Petri nets published in the~80s.
Simultaneous straight-line drawing of a planar graph and its rectangular dual
Venue: arXiv cs.CG 2015
Year: 2015

A natural way to represent on the plane both a planar graph and its dual is to follow the definition of the dual, thus, to place vertices inside their corresponding primal faces, and to draw the dual edges so that they only cross their corresponding primal edges. The problem of constructing such drawings has a long tradition when the drawings of both primal and dual are required to be straight-line. We consider the same problem for a planar graph and its rectangular dual. We show that the rectangular dual can be resized to host a planar straight-line drawing of its primal.
Refining the Analysis of Divide and Conquer: How and When
Venue: arXiv cs.DS 2015
Year: 2015

Divide-and-conquer is a central paradigm for the design of algorithms, through which some fundamental computational problems, such as sorting arrays and computing convex hulls, are solved in optimal time within $Θ(n\log{n})$ in the worst case over instances of size $n$. A finer analysis of those problems yields complexities within $O(n(1 + \mathcal{H}(n_1, \dots, n_k))) \subseteq O(n(1{+}\log{k})) \subseteq O(n\log{n})$ in the worst case over all instances of size $n$ composed of $k$ "easy" fragments of respective sizes $n_1, \dots, n_k$ summing to $n$, where the entropy function $\mathcal{H}(n_1, \dots, n_k) = \sum_{i=1}^k{\frac{n_i}{n}}\log{\frac{n}{n_i}}$ measures the "difficulty" of the instance. We consider whether such refined analysis can be applied to other algorithms based on divide-and-conquer, such as polynomial multiplication, input-order adaptive computation of convex hulls in 2D and 3D, and computation of Delaunay triangulations.
Perfectly secure data aggregation via shifted projections
Venue: arXiv cs.CR 2015
Year: 2015

We study a general scenario where confidential information is distributed among a group of agents who wish to share it in such a way that the data becomes common knowledge among them but an eavesdropper intercepting their communications would be unable to obtain any of said data. The information is modelled as a deck of cards dealt among the agents, so that after the information is exchanged, all of the communicating agents must know the entire deal, but the eavesdropper must remain ignorant about who holds each card. Valentin Goranko and the author previously set up this scenario as the secure aggregation of distributed information problem and constructed weakly safe protocols, where given any card $c$, the eavesdropper does not know with certainty which agent holds $c$. Here we present a perfectly safe protocol, which does not alter the eavesdropper's perceived probability that any given agent holds $c$. In our protocol, one of the communicating agents holds a larger portion of the cards than the rest, but we show how for infinitely many values of $a$, the number of cards may be chosen so that each of the $m$ agents holds more than $a$ cards and less than $2m^2a$.
Incorporating Type II Error Probabilities from Independence Tests into Score-Based Learning of Bayesian Network Structure
Venue: arXiv cs.LG 2015
Year: 2015

We give a new consistent scoring function for structure learning of Bayesian networks. In contrast to traditional approaches to score-based structure learning, such as BDeu or MDL, the complexity penalty that we propose is data-dependent and is given by the probability that a conditional independence test correctly shows that an edge cannot exist. What really distinguishes this new scoring function from earlier work is that it has the property of becoming computationally easier to maximize as the amount of data increases. We prove a polynomial sample complexity result, showing that maximizing this score is guaranteed to correctly learn a structure with no false edges and a distribution close to the generating distribution, whenever there exists a Bayesian network which is a perfect map for the data generating distribution. Although the new score can be used with any search algorithm, in our related UAI 2013 paper [BS13], we have given empirical results showing that it is particularly effective when used together with a linear programming relaxation approach to Bayesian network structure learning. The present paper contains all details of the proofs of the finite-sample complexity results in [BS13] as well as detailed explanation of the computation of the certain error probabilities called beta-values, whose precomputation and tabulation is necessary for the implementation of the algorithm in [BS13].
Privacy Risks in Mobile Dating Apps
Venue: arXiv cs.CY 2015
Year: 2015

Dating apps for mobile devices, one popular GeoSocial app category, are growing increasingly popular. These apps encourage the sharing of more personal information than conventional social media apps, including continuous location data. However, recent high profile incidents have highlighted the privacy risks inherent in using these apps. In this paper, we present a case study utilizing forensic techniques on nine popular proximity-based dating apps in order to determine the types of data that can be recovered from user devices. We recover a number of data types from these apps that raise concerns about user privacy. For example, we determine that chat messages could be recovered in at least half of the apps examined and, in some cases, the details of any users that had been discovered nearby could also be extracted.
Pfaffian Systems of A-Hypergeometric Systems II --- Holonomic Gradient Method
Venue: arXiv cs.SC 2015
Year: 2015

We give two efficient methods to derive Pfaffian systems for A-hypergeometric systems for the application to the holonomic gradient method for statistics. We utilize the Hilbert driven Buchberger algorithm and Macaulay type matrices in the two methods.
A Robust Scheme for PSS Detection and Integer Frequency Offset Recovery in LTE Systems
Venue: arXiv cs.IT 2015
Year: 2015

Before establishing a communication link in a cellular network, the user terminal must activate a synchronization procedure called initial cell search in order to acquire specific information about the serving base station. To accomplish this task, the primary synchronization signal (PSS) and secondary synchronization signal (SSS) are periodically transmitted in the downlink of a Long Term Evolution (LTE) network. Since SSS detection can be performed only after successful identification of the primary signal, in this work we present a robust scheme for joint PSS detection, sector index identification and integer frequency offset (IFO) recovery in an LTE system. The proposed algorithm relies on the maximum likelihood (ML) estimation criterion and exploits a suitable reduced-rank representation of the channel frequency response to take multipath distortions into account. We show that some PSS detection methods that were originally introduced through heuristic reasoning can be derived from our ML framework by selecting an appropriate model for the channel gains over the PSS subcarriers. Numerical simulations indicate that the proposed scheme can be effectively applied in the presence of severe multipath propagation, where existing alternatives provide unsatisfactory performance.
Comparing methods for Twitter Sentiment Analysis
Venue: arXiv cs.CL 2015
Year: 2015

This work extends the set of works which deal with the popular problem of sentiment analysis in Twitter. It investigates the most popular document ("tweet") representation methods which feed sentiment evaluation mechanisms. In particular, we study the bag-of-words, n-grams and n-gram graphs approaches and for each of them we evaluate the performance of a lexicon-based and 7 learning-based classification algorithms (namely SVM, Naïve Bayesian Networks, Logistic Regression, Multilayer Perceptrons, Best-First Trees, Functional Trees and C4.5) as well as their combinations, using a set of 4451 manually annotated tweets. The results demonstrate the superiority of learning-based methods and in particular of n-gram graphs approaches for predicting the sentiment of tweets. They also show that the combinatory approach has impressive effects on n-grams, raising the confidence up to 83.15% on the 5-Grams, using majority vote and a balanced dataset (equal number of positive, negative and neutral tweets for training). In the n-gram graph cases the improvement was small to none, reaching 94.52% on the 4-gram graphs, using Orthodromic distance and a threshold of 0.001.
The minimum bisection in the planted bisection model
Venue: arXiv cs.DM 2015
Year: 2015

In the planted bisection model a random graph $G(n,p_+,p_- )$ with $n$ vertices is created by partitioning the vertices randomly into two classes of equal size (up to $\pm1$). Any two vertices that belong to the same class are linked by an edge with probability $p_+$ and any two that belong to different classes with probability $p_- <p_+$ independently. The planted bisection model has been used extensively to benchmark graph partitioning algorithms. If $p_{\pm} =2d_{\pm} /n$ for numbers $0\leq d_- <d_+ $ that remain fixed as $n\to\infty$, then w.h.p. the ``planted'' bisection (the one used to construct the graph) will not be a minimum bisection. In this paper we derive an asymptotic formula for the minimum bisection width under the assumption that $d_+ -d_- >c\sqrt{d_+ \ln d_+ }$ for a certain constant $c>0$.
Frappe: Understanding the Usage and Perception of Mobile App Recommendations In-The-Wild
Venue: arXiv cs.IR 2015
Year: 2015

This paper describes a real world deployment of a context-aware mobile app recommender system (RS) called Frappe. Utilizing a hybrid-approach, we conducted a large-scale app market deployment with 1000 Android users combined with a small-scale local user study involving 33 users. The resulting usage logs and subjective feedback enabled us to gather key insights into (1) context-dependent app usage and (2) the perceptions and experiences of end-users while interacting with context-aware mobile app recommendations. While Frappe performs very well based on usage-centric evaluation metrics insights from the small-scale study reveal some negative user experiences. Our results point to a number of actionable lessons learned specifically related to designing, deploying and evaluating mobile context-aware RS in-the-wild with real users.
Duality between Temporal Networks and Signals: Extraction of the Temporal Network Structures
Venue: arXiv cs.SI 2015
Year: 2015

We develop a framework to track the structure of temporal networks with a signal processing approach. The method is based on the duality between networks and signals using a multidimensional scaling technique. This enables a study of the network structure using frequency patterns of the corresponding signals. An extension is proposed for temporal networks, thereby enabling a tracking of the network structure over time. A method to automatically extract the most significant frequency patterns and their activation coefficients over time is then introduced, using nonnegative matrix factorization of the temporal spectra. The framework, inspired by audio decomposition, allows transforming back these frequency patterns into networks, to highlight the evolution of the underlying structure of the network over time. The effectiveness of the method is first evidenced on a toy example, prior being used to study a temporal network of face-to-face contacts. The extraction of sub-networks highlights significant structures decomposed on time intervals.
Strong Divergence for System Approximations
Venue: arXiv cs.IT 2015
Year: 2015

In this paper we analyze the approximation of stable linear time-invariant systems, like the Hilbert transform, by sampling series for bandlimited functions in the Paley-Wiener space $\mathcal{PW}_π^{1}$. It is known that there exist systems and functions such that the approximation process is weakly divergent, i.e., divergent for certain subsequences. Here we strengthen this result by proving strong divergence, i.e., divergence for all subsequences. Further, in case of divergence, we give the divergence speed. We consider sampling at Nyquist rate as well as oversampling with adaptive choice of the kernel. Finally, connections between strong divergence and the Banach-Steinhaus theorem, which is not powerful enough to prove strong divergence, are discussed.
Actors vs Shared Memory: two models at work on Big Data application frameworks
Venue: arXiv cs.DC 2015
Year: 2015

This work aims at analyzing how two different concurrency models, namely the shared memory model and the actor model, can influence the development of applications that manage huge masses of data, distinctive of Big Data applications. The paper compares the two models by analyzing a couple of concrete projects based on the MapReduce and Bulk Synchronous Parallel algorithmic schemes. Both projects are doubly implemented on two concrete platforms: Akka Cluster and Managed X10. The result is both a conceptual comparison of models in the Big Data Analytics scenario, and an experimental analysis based on concrete executions on a cluster platform.
Binary GH Sequences for Multiparty Communication
Venue: arXiv cs.CR 2015
Year: 2015

This paper investigates cross correlation properties of sequences derived from GH sequences modulo p, where p is a prime number and presents comparison with cross correlation properties of pseudo noise sequences. For GH sequences modulo prime, a binary random sequence B(n) is constructed, based on whether the period is p-1 (or a divisor) or 2p+2 (or a divisor). We show that B(n) sequences have much less peak cross correlation compared to PN sequence fragments obtained from the same generator. Potential applications of these sequences to cryptography are sketched.
Indonesian Social Media Sentiment Analysis With Sarcasm Detection
Venue: arXiv cs.CL 2015
Year: 2015

Sarcasm is considered one of the most difficult problem in sentiment analysis. In our ob-servation on Indonesian social media, for cer-tain topics, people tend to criticize something using sarcasm. Here, we proposed two additional features to detect sarcasm after a common sentiment analysis is conducted. The features are the negativity information and the number of interjection words. We also employed translated SentiWordNet in the sentiment classification. All the classifications were conducted with machine learning algorithms. The experimental results showed that the additional features are quite effective in the sarcasm detection.
Energy Detection of Unknown Signals over Cascaded Fading Channels
Venue: arXiv cs.IT 2015
Year: 2015

Energy detection is a favorable mechanism in several applications relating to the identification of deterministic unknown signals such as in radar systems and cognitive radio communications. The present work quantifies the detrimental effects of cascaded multipath fading on energy detection and investigates the corresponding performance capability. A novel analytic solution is firstly derived for a generic integral that involves a product of the Meijer $G-$function, the Marcum $Q-$function and arbitrary power terms. This solution is subsequently employed in the derivation of an exact closed-form expression for the average probability of detection of unknown signals over $N$*Rayleigh channels. The offered results are also extended to the case of square-law selection, which is a relatively simple and effective diversity method. It is shown that the detection performance is considerably degraded by the number of cascaded channels and that these effects can be effectively mitigated by a non-substantial increase of diversity branches.
Near-optimal bounds on bounded-round quantum communication complexity of disjointness
Venue: arXiv cs.CC 2015
Year: 2015

We prove a near optimal round-communication tradeoff for the two-party quantum communication complexity of disjointness. For protocols with $r$ rounds, we prove a lower bound of $\tildeΩ(n/r + r)$ on the communication required for computing disjointness of input size $n$, which is optimal up to logarithmic factors. The previous best lower bound was $Ω(n/r^2 + r)$ due to Jain, Radhakrishnan and Sen [JRS03]. Along the way, we develop several tools for quantum information complexity, one of which is a lower bound for quantum information complexity in terms of the generalized discrepancy method. As a corollary, we get that the quantum communication complexity of any boolean function $f$ is at most $2^{O(QIC(f))}$, where $QIC(f)$ is the prior-free quantum information complexity of $f$ (with error $1/3$).