OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic Verification of SystemC with Statistical Model Checking
Venue: arXiv cs.SE 2015
Year: 2015

Many embedded and real-time systems have a inherent probabilistic behaviour (sensors data, unreliable hardware,...). In that context, it is crucial to evaluate system properties such as "the probability that a particular hardware fails". Such properties can be evaluated by using probabilistic model checking. However, this technique fails on models representing realistic embedded and real-time systems because of the state space explosion. To overcome this problem, we propose a verification framework based on Statistical Model Checking. Our framework is able to evaluate probabilistic and temporal properties on large systems modelled in SystemC, a standard system-level modelling language. It is fully implemented as an extension of the Plasma-lab statistical model checker. We illustrate our approach on a multi-lift system case study.
On the Interactions between Multiple Overlapping WLANs using Channel Bonding
Venue: arXiv cs.NI 2015
Year: 2015

Next-generation WLANs will support the use of wider channels, which is known as channel bonding, to achieve higher throughput. However, because both the channel center frequency and the channel width are autonomously selected by each WLAN, the use of wider channels may also increase the competition with other WLANs operating in the same area for the limited available spectrum, thus causing the opposite effect. In this paper, we analyse the interactions between a group of neighboring WLANs that use channel bonding and evaluate the impact of those interactions on the achievable throughput. A Continuous Time Markov Network (CTMN) model that is able to capture the coupled operation of a group of overlapping WLANs is introduced and validated. The results show that the use of channel bonding can provide significant performance gains even in scenarios with high densities of WLANs, though it may also cause unfair situations in which some WLANs cannot access the channel, while others receive most of the transmission opportunities.
Information-Sharing over Adaptive Networks with Self-interested Agents
Venue: arXiv cs.MA 2015
Year: 2015

We examine the behavior of multi-agent networks where information-sharing is subject to a positive communications cost over the edges linking the agents. We consider a general mean-square-error formulation where all agents are interested in estimating the same target vector. We first show that, in the absence of any incentives to cooperate, the optimal strategy for the agents is to behave in a selfish manner with each agent seeking the optimal solution independently of the other agents. Pareto inefficiency arises as a result of the fact that agents are not using historical data to predict the behavior of their neighbors and to know whether they will reciprocate and participate in sharing information. Motivated by this observation, we develop a reputation protocol to summarize the opponent's past actions into a reputation score, which can then be used to form a belief about the opponent's subsequent actions. The reputation protocol entices agents to cooperate and turns their optimal strategy into an action-choosing strategy that enhances the overall social benefit of the network. In particular, we show that when the communications cost becomes large, the expected social benefit of the proposed protocol outperforms the social benefit that is obtained by cooperative agents that always share data. We perform a detailed mean-square-error analysis of the evolution of the network over three domains: far field, near-field, and middle-field, and show that the network behavior is stable for sufficiently small step-sizes. The various theoretical results are illustrated by numerical simulations.
Mining Rooted Ordered Trees under Subtree Homeomorphism
Venue: arXiv cs.DB 2015
Year: 2015

Mining frequent tree patterns has many applications in different areas such as XML data, bioinformatics and World Wide Web. The crucial step in frequent pattern mining is frequency counting, which involves a matching operator to find occurrences (instances) of a tree pattern in a given collection of trees. A widely used matching operator for tree-structured data is subtree homeomorphism, where an edge in the tree pattern is mapped onto an ancestor-descendant relationship in the given tree. Tree patterns that are frequent under subtree homeomorphism are usually called embedded patterns. In this paper, we present an efficient algorithm for subtree homeomorphism with application to frequent pattern mining. We propose a compact data-structure, called occ, which stores only information about the rightmost paths of occurrences and hence can encode and represent several occurrences of a tree pattern. We then define efficient join operations on the occ data-structure, which help us count occurrences of tree patterns according to occurrences of their proper subtrees. Based on the proposed subtree homeomorphism method, we develop an effective pattern mining algorithm, called TPMiner. We evaluate the efficiency of TPMiner on several real-world and synthetic datasets. Our extensive experiments confirm that TPMiner always outperforms well-known existing algorithms, and in several cases the improvement with respect to existing algorithms is significant.
Information Exchange and Learning Dynamics over Weakly-Connected Adaptive Networks
Venue: arXiv cs.MA 2015
Year: 2015

The paper examines the learning mechanism of adaptive agents over weakly-connected graphs and reveals an interesting behavior on how information flows through such topologies. The results clarify how asymmetries in the exchange of data can mask local information at certain agents and make them totally dependent on other agents. A leader-follower relationship develops with the performance of some agents being fully determined by the performance of other agents that are outside their domain of influence. This scenario can arise, for example, due to intruder attacks by malicious agents or as the result of failures by some critical links. The findings in this work help explain why strong-connectivity of the network topology, adaptation of the combination weights, and clustering of agents are important ingredients to equalize the learning abilities of all agents against such disturbances. The results also clarify how weak-connectivity can be helpful in reducing the effect of outlier data on learning performance.
Fast Rates by Transferring from Auxiliary Hypotheses
Venue: arXiv cs.LG 2015
Year: 2015

In this work we consider the learning setting where, in addition to the training set, the learner receives a collection of auxiliary hypotheses originating from other tasks. We focus on a broad class of ERM-based linear algorithms that can be instantiated with any non-negative smooth loss function and any strongly convex regularizer. We establish generalization and excess risk bounds, showing that, if the algorithm is fed with a good combination of source hypotheses, generalization happens at the fast rate $\mathcal{O}(1/m)$ instead of the usual $\mathcal{O}(1/\sqrt{m})$. On the other hand, if the source hypotheses combination is a misfit for the target task, we recover the usual learning rate. As a byproduct of our study, we also prove a new bound on the Rademacher complexity of the smooth loss class under weaker assumptions compared to previous works.
Exemplar Dynamics and Sound Merger in Language
Venue: arXiv cs.CL 2015
Year: 2015

We develop a model of phonological contrast in natural language. Specifically, the model describes the maintenance of contrast between different words in a language, and the elimination of such contrast when sounds in the words merge. An example of such a contrast is that provided by the two vowel sounds 'i' and 'e', which distinguish pairs of words such as 'pin' and 'pen' in most dialects of English. We model language users' knowledge of the pronunciation of a word as consisting of collections of labeled exemplars stored in memory. Each exemplar is a detailed memory of a particular utterance of the word in question. In our model an exemplar is represented by one or two phonetic variables along with a weight indicating how strong the memory of the utterance is. Starting from an exemplar-level model we derive integro-differential equations for the evolution of exemplar density fields in phonetic space. Using these latter equations we investigate under what conditions two sounds merge, thus eliminating the contrast. Our main conclusion is that for the preservation of phonological contrast, it is necessary that anomalous utterances of a given word are discarded, and not merely stored in memory as an exemplar of another word.
Joint Rate and SINR Coverage Analysis for Decoupled Uplink-Downlink Biased Cell Associations in HetNets
Venue: arXiv cs.IT 2015
Year: 2015

Load balancing by proactively offloading users onto small and otherwise lightly-loaded cells is critical for tapping the potential of dense heterogeneous cellular networks (HCNs). Offloading has mostly been studied for the downlink, where it is generally assumed that a user offloaded to a small cell will communicate with it on the uplink as well. The impact of coupled downlink-uplink offloading is not well understood. Uplink power control and spatial interference correlation further complicate the mathematical analysis as compared to the downlink. We propose an accurate and tractable model to characterize the uplink SINR and rate distribution in a multi-tier HCN as a function of the association rules and power control parameters. Joint uplink-downlink rate coverage is also characterized. Using the developed analysis, it is shown that the optimal degree of channel inversion (for uplink power control) increases with load imbalance in the network. In sharp contrast to the downlink, minimum path loss association is shown to be optimal for uplink rate. Moreover, with minimum path loss association and full channel inversion, uplink SIR is shown to be invariant of infrastructure density. It is further shown that a decoupled association---employing differing association strategies for uplink and downlink---leads to significant improvement in joint uplink-downlink rate coverage over the standard coupled association in HCNs.
$\ell_p$ Testing and Learning of Discrete Distributions
Venue: arXiv cs.DS 2015
Year: 2015

The classic problems of testing uniformity of and learning a discrete distribution, given access to independent samples from it, are examined under general $\ell_p$ metrics. The intuitions and results often contrast with the classic $\ell_1$ case. For $p > 1$, we can learn and test with a number of samples that is independent of the support size of the distribution: With an $\ell_p$ tolerance $ε$, $O(\max\{ \sqrt{1/ε^q}, 1/ε^2 \})$ samples suffice for testing uniformity and $O(\max\{ 1/ε^q, 1/ε^2\})$ samples suffice for learning, where $q=p/(p-1)$ is the conjugate of $p$. As this parallels the intuition that $O(\sqrt{n})$ and $O(n)$ samples suffice for the $\ell_1$ case, it seems that $1/ε^q$ acts as an upper bound on the "apparent" support size. For some $\ell_p$ metrics, uniformity testing becomes easier over larger supports: a 6-sided die requires fewer trials to test for fairness than a 2-sided coin, and a card-shuffler requires fewer trials than the die. In fact, this inverse dependence on support size holds if and only if $p > \frac{4}{3}$. The uniformity testing algorithm simply thresholds the number of "collisions" or "coincidences" and has an optimal sample complexity up to constant factors for all $1 \leq p \leq 2$. Another algorithm gives order-optimal sample complexity for $\ell_{\infty}$ uniformity testing. Meanwhile, the most natural learning algorithm is shown to have order-optimal sample complexity for all $\ell_p$ metrics. The author thanks Clément Canonne for discussions and contributions to this work.
How Far Removed Are You? Scalable Privacy-Preserving Estimation of Social Path Length with Social PaL
Venue: arXiv cs.CR 2015
Year: 2015

Social relationships are a natural basis on which humans make trust decisions. Online Social Networks (OSNs) are increasingly often used to let users base trust decisions on the existence and the strength of social relationships. While most OSNs allow users to discover the length of the social path to other users, they do so in a centralized way, thus requiring them to rely on the service provider and reveal their interest in each other. This paper presents Social PaL, a system supporting the privacy-preserving discovery of arbitrary-length social paths between any two social network users. We overcome the bootstrapping problem encountered in all related prior work, demonstrating that Social PaL allows its users to find all paths of length two and to discover a significant fraction of longer paths, even when only a small fraction of OSN users is in the Social PaL system - e.g., discovering 70% of all paths with only 40% of the users. We implement Social PaL using a scalable server-side architecture and a modular Android client library, allowing developers to seamlessly integrate it into their apps.
Strong edge-coloring of $(3, Δ)$-bipartite graphs
Venue: arXiv cs.DM 2015
Year: 2015

A strong edge-coloring of a graph $G$ is an assignment of colors to edges such that every color class induces a matching. We here focus on bipartite graphs whose one part is of maximum degree at most $3$ and the other part is of maximum degree $Δ$. For every such graph, we prove that a strong $4Δ$-edge-coloring can always be obtained. Together with a result of Steger and Yu, this result confirms a conjecture of Faudree, Gyárfás, Schelp and Tuza for this class of graphs.
Satisfiability of ECTL* with tree constraints
Venue: arXiv cs.LO 2015
Year: 2015

Recently, we have shown that satisfiability for $\mathsf{ECTL}^*$ with constraints over $\mathbb{Z}$ is decidable using a new technique. This approach reduces the satisfiability problem of $\mathsf{ECTL}^*$ with constraints over some structure A (or class of structures) to the problem whether A has a certain model theoretic property that we called EHD (for "existence of homomorphisms is decidable"). Here we apply this approach to concrete domains that are tree-like and obtain several results. We show that satisfiability of $\mathsf{ECTL}^*$ with constraints is decidable over (i) semi-linear orders (i.e., tree-like structures where branches form arbitrary linear orders), (ii) ordinal trees (semi-linear orders where the branches form ordinals), and (iii) infinitely branching trees of height h for each fixed $h\in \mathbb{N}$. We prove that all these classes of structures have the property EHD. In contrast, we introduce Ehrenfeucht-Fraisse-games for $\mathsf{WMSO}+\mathsf{B}$ (weak $\mathsf{MSO}$ with the bounding quantifier) and use them to show that the infinite (order) tree does not have property EHD. As a consequence, a different approach has to be taken in order to settle the question whether satisfiability of $\mathsf{ECTL}^*$ (or even $\mathsf{LTL}$) with constraints over the infinite (order) tree is decidable.
Revenue Maximization for Selling Multiple Correlated Items
Venue: arXiv cs.GT 2015
Year: 2015

We study the problem of selling $n$ items to a single buyer with an additive valuation function. We consider the valuation of the items to be correlated, i.e., desirabilities of the buyer for the items are not drawn independently. Ideally, the goal is to design a mechanism to maximize the revenue. However, it has been shown that a revenue optimal mechanism might be very complicated and as a result inapplicable to real-world auctions. Therefore, our focus is on designing a simple mechanism that achieves a constant fraction of the optimal revenue. Babaioff et al. propose a simple mechanism that achieves a constant fraction of the optimal revenue for independent setting with a single additive buyer. However, they leave the following problem as an open question: "Is there a simple, approximately optimal mechanism for a single additive buyer whose value for $n$ items is sampled from a common base-value distribution?" Babaioff et al. show a constant approximation factor of the optimal revenue can be achieved by either selling the items separately or as a whole bundle in the independent setting. We show a similar result for the correlated setting when the desirabilities of the buyer are drawn from a common base-value distribution. It is worth mentioning that the core decomposition lemma which is mainly the heart of the proofs for efficiency of the mechanisms does not hold for correlated settings. Therefore we propose a modified version of this lemma which is applicable to the correlated settings as well. Although we apply this technique to show the proposed mechanism can guarantee a constant fraction of the optimal revenue in a very weak correlation, this method alone can not directly show the efficiency of the mechanism in stronger correlations.
Super-resolution on the Sphere using Convex Optimization
Venue: arXiv cs.IT 2015
Year: 2015

This paper considers the problem of recovering an ensemble of Diracs on a sphere from its low resolution measurements. The Diracs can be located at any location on the sphere, not necessarily on a grid. We show that under a separation condition, one can recover the ensemble with high precision by a three-stage algorithm, which consists of solving a semi-definite program, root finding and least-square fitting. The algorithm's computation time depends solely on the number of measurements, and not on the required solution accuracy. We also show that in the special case of non-negative ensembles, a sparsity condition is sufficient for recovery. Furthermore, in the discrete setting, we estimate the recovery error in the presence of noise as a function of the noise level and the super-resolution factor.
Strategyproof Mechanisms for One-Dimensional Hybrid and Obnoxious Facility Location
Venue: arXiv cs.GT 2015
Year: 2015

We consider a strategic variant of the facility location problem. We would like to locate a facility on a closed interval. There are n agents located on that interval, divided into two types: type 1 agents, who wish for the facility to be as far from them as possible, and type 2 agents, who wish for the facility to be as close to them as possible. Our goal is to maximize a form of aggregated social benefit: maxisum- the sum of the agents' utilities, or the egalitarian objective- the minimal agent utility. The strategic aspect of the problem is that the agents' locations are not known to us, but rather reported to us by the agents- an agent might misreport his location in an attempt to move the facility away from or towards to his true location. We therefore require the facility-locating mechanism to be strategyproof, namely that reporting truthfully is a dominant strategy for each agent. As simply maximizing the social benefit is generally not strategyproof, our goal is to design strategyproof mechanisms with good approximation ratios. For the maxisum objective, in the deterministic setting, we provide a best-possible 3- approximate strategyproof mechanism; in the randomized setting, we provide a 23/13- approximate strategyproof mechanism and a lower bound of \frac{2}{\sqrt{3}}. For the egalitarian objective, we provide a lower bound of 3/2 in the randomized setting, and show that no bounded approximation ratio is attainable in the deterministic setting. To obtain our deterministic lower bounds, we characterize all deterministic strategyproof mechanisms when all agents are of type 1. Finally, we consider a generalized model that allows an agent to control more than one location, and provide best-possible 3- and 3/2- approximate strategyproof mechanisms for maxisum, in the deterministic and randomized settings respectively, when only type 1 agents are present.
Quantitative Analysis of the Italian National Scientific Qualification
Venue: arXiv cs.DL 2015
Year: 2015

The Italian National Scientific Qualification (ASN) was introduced in 2010 as part of a major reform of the national university system. Under the new regulation, the scientific qualification for a specific role (associate or full professor) and field of study is required to apply to a permanent professor position. The ASN is peculiar since it makes use of bibliometric indicators with associated thresholds as one of the parameters used to assess applicants. Overall, more than 59000 applications were submitted, and the results have been made publicly available for a short period of time, including the values of the quantitative indicators for each applicant. The availability of this wealth of information provides an opportunity to draw a fairly detailed picture of a nation-wide evaluation exercise, and to study the impact of the bibliometric indicators on the qualification results. In this paper we provide a first account of the Italian ASN from a quantitative point of view. We show that significant differences exist among scientific disciplines, in particular with respect to the fraction of qualified applicants, that can not be easily explained. Furthermore, we describe some issues related to the definition and use of the bibliometric indicators and thresholds. Our analysis aims at drawing attention to potential problems that should be addressed by decision-makers in future ASN rounds.
Defining relations on graphs: how hard is it in the presence of node partitions?
Venue: arXiv cs.DB 2015
Year: 2015

Designing query languages for graph structured data is an active field of research. Evaluating a query on a graph results in a relation on the set of its nodes. In other words, a query is a mechanism for defining relations on a graph. Some relations may not be definable by any query in a given language. This leads to the following question: given a graph, a query language and a relation on the graph, does there exist a query in the language that defines the relation? This is called the definability problem. When the given query language is standard regular expressions, the definability problem is known to be PSPACE-complete. The model of graphs can be extended by labeling nodes with values from an infinite domain. These labels induce a partition on the set of nodes: two nodes are equivalent if they are labeled by the same value. Query languages can also be extended to make use of this equivalence. Two such extensions are Regular Expressions with Memory (REM) and Regular Expressions with Equality (REE). In this paper, we study the complexity of the definability problem in this extended model when the query language is either REM or REE. We show that the definability problem is EXPSPACE-complete when the query language is REM, and it is PSPACE-complete when the query language is REE. In addition, when the query language is a union of conjunctive queries based on REM or REE, we show coNP-completeness.