OpenRaiser/Intern-Atlas huggingface dataset:
Support Recovery for the Drift Coefficient of High-Dimensional Diffusions
Venue: arXiv cs.IT 2013
Year: 2013

Consider the problem of learning the drift coefficient of a $p$-dimensional stochastic differential equation from a sample path of length $T$. We assume that the drift is parametrized by a high-dimensional vector, and study the support recovery problem when both $p$ and $T$ can tend to infinity. In particular, we prove a general lower bound on the sample-complexity $T$ by using a characterization of mutual information as a time integral of conditional variance, due to Kadota, Zakai, and Ziv. For linear stochastic differential equations, the drift coefficient is parametrized by a $p\times p$ matrix which describes which degrees of freedom interact under the dynamics. In this case, we analyze a $\ell_1$-regularized least squares estimator and prove an upper bound on $T$ that nearly matches the lower bound on specific classes of sparse matrices.
The Price of Anarchy is Unbounded for Congestion Games with Superpolynomial Latency Costs
Venue: arXiv cs.GT 2013
Year: 2013

We consider non-cooperative unsplittable congestion games where players share resources, and each player's strategy is pure and consists of a subset of the resources on which it applies a fixed weight. Such games represent unsplittable routing flow games and also job allocation games. The congestion of a resource is the sum of the weights of the players that use it and the player's cost function is the sum of the utilities of the resources on its strategy. The social cost is the total weighted sum of the player's costs. The quality of Nash equilibria is determined by the price of anarchy ($PoA$) which expresses how much worse is the social outcome in the worst equilibrium versus the optimal coordinated solution. In the literature the predominant work has only been on games with polynomial utility costs, where it has been proven that the price of anarchy is bounded by the degree of the polynomial. However, no results exist on general bounds for non-polynomial utility functions. Here, we consider general versions of these games in which the utility of each resource is an arbitrary non-decreasing function of the congestion. In particular, we consider a large family of superpolynomial utility functions which are asymptotically larger than any polynomial. We demonstrate that for every such function there exist games for which the price of anarchy is unbounded and increasing with the number of players (even if they have infinitesimal weights) while network resources remain fixed. We give tight lower and upper bounds which show this dependence on the number of players. Furthermore we provide an exact characterization of the $PoA$ of all congestion games whose utility costs are bounded above by a polynomial function. Heretofore such results existed only for games with polynomial cost functions.
An Investigation of the Sampling-Based Alignment Method and Its Contributions
Venue: arXiv cs.CL 2013
Year: 2013

By investigating the distribution of phrase pairs in phrase translation tables, the work in this paper describes an approach to increase the number of n-gram alignments in phrase translation tables output by a sampling-based alignment method. This approach consists in enforcing the alignment of n-grams in distinct translation subtables so as to increase the number of n-grams. Standard normal distribution is used to allot alignment time among translation subtables, which results in adjustment of the distribution of n- grams. This leads to better evaluation results on statistical machine translation tasks than the original sampling-based alignment approach. Furthermore, the translation quality obtained by merging phrase translation tables computed from the sampling-based alignment method and from MGIZA++ is examined.
Services in Android can Share Your Personal Information in Background
Venue: arXiv cs.OH 2013
Year: 2013

Mobile phones have traveled a very long journey in a very short span of time since its inception in 1973.This wonderful toy of 20th century has started playing significant role in daily life.More than 5 billion mobile users are there around the world and almost 90 percent of the entire earth is under the mobile coverage now.These days smart phones are equipped with numerous features,faster processors and high storage capacity.Android is a latest trend in this series whose popularity is growing by leaps and bounds.Android has a number of components which helps Application developers to embed distinguish features in applications.This paper explains how the Service component of Android can share your personal information to others without users interaction.
Truthful Scheduling Mechanisms for Powering Mobile Crowdsensing
Venue: arXiv cs.NI 2013
Year: 2013

Mobile crowdsensing leverages mobile devices (e.g., smart phones) and human mobility for pervasive information exploration and collection; it has been deemed as a promising paradigm that will revolutionize various research and application domains. Unfortunately, the practicality of mobile crowdsensing can be crippled due to the lack of incentive mechanisms that stimulate human participation. In this paper, we study incentive mechanisms for a novel Mobile Crowdsensing Scheduling (MCS) problem, where a mobile crowdsensing application owner announces a set of sensing tasks, then human users (carrying mobile devices) compete for the tasks based on their respective sensing costs and available time periods, and finally the owner schedules as well as pays the users to maximize its own sensing revenue under a certain budget. We prove that the MCS problem is NP-hard and propose polynomial-time approximation mechanisms for it. We also show that our approximation mechanisms (including both offline and online versions) achieve desirable game-theoretic properties, namely truthfulness and individual rationality, as well as O(1) performance ratios. Finally, we conduct extensive simulations to demonstrate the correctness and effectiveness of our approach.
Query Processing Performance and Searching Over Encrypted Data By Using An Efficient Algorithm
Venue: arXiv cs.DB 2013
Year: 2013

Data is the central asset of today's dynamically operating organization and their business. This data is usually stored in database. A major consideration is applied on the security of that data from the unauthorized access and intruders. Data encryption is a strong option for security of data in database and especially in those organizations where security risks are high. But there is a potential disadvantage of performance degradation. When we apply encryption on database then we should compromise between the security and efficient query processing. The work of this paper tries to fill this gap. It allows the users to query over the encrypted column directly without decrypting all the records. It's improves the performance of the system. The proposed algorithm works well in the case of range and fuzzy match queries.
Machine Code Optimization - Improving Executable Object Code
Venue: arXiv cs.PL 2013
Year: 2013

This dissertation explores classes of compiler optimization techniques that are applicable late in the compilation process, after all executable code for a program has been linked. I concentrate on techniques which, for various reasons, cannot be applied earlier in the compilation process. In addition to a theoretical treatment of this class of optimization techniques, this dissertation reports on an implementation of these techniques in a production environment. I describe the details of the implementation which allows these techniques to be re-targeted easily and report on improvements gained when optimizing production software.
POMDPs under Probabilistic Semantics
Venue: arXiv cs.AI 2013
Year: 2013

We consider partially observable Markov decision processes (POMDPs) with limit-average payoff, where a reward value in the interval [0,1] is associated to every transition, and the payoff of an infinite path is the long-run average of the rewards. We consider two types of path constraints: (i) quantitative constraint defines the set of paths where the payoff is at least a given threshold λ in (0, 1]; and (ii) qualitative constraint which is a special case of quantitative constraint with λ = 1. We consider the computation of the almost-sure winning set, where the controller needs to ensure that the path constraint is satisfied with probability 1. Our main results for qualitative path constraint are as follows: (i) the problem of deciding the existence of a finite-memory controller is EXPTIME-complete; and (ii) the problem of deciding the existence of an infinite-memory controller is undecidable. For quantitative path constraint we show that the problem of deciding the existence of a finite-memory controller is undecidable.
Optimizing Key Distribution in Peer to Peer Network Using B-Trees
Venue: arXiv cs.CR 2013
Year: 2013

Peer to peer network architecture introduces many desired features including self-scalability that led to achieving higher efficiency rate than the traditional server-client architecture. This was contributed to the highly distributed architecture of peer to peer network. Meanwhile, the lack of a centralized control unit in peer to peer network introduces some challenge. One of these challenges is key distribution and management in such an architecture. This research will explore the possibility of developing a novel scheme for distributing and managing keys in peer to peer network architecture efficiently.
Extending Similarity Measures of Interval Type-2 Fuzzy Sets to General Type-2 Fuzzy Sets
Venue: arXiv cs.AI 2013
Year: 2013

Similarity measures provide one of the core tools that enable reasoning about fuzzy sets. While many types of similarity measures exist for type-1 and interval type-2 fuzzy sets, there are very few similarity measures that enable the comparison of general type-2 fuzzy sets. In this paper, we introduce a general method for extending existing interval type-2 similarity measures to similarity measures for general type-2 fuzzy sets. Specifically, we show how similarity measures for interval type-2 fuzzy sets can be employed in conjunction with the zSlices based general type-2 representation for fuzzy sets to provide measures of similarity which preserve all the common properties (i.e. reflexivity, symmetry, transitivity and overlapping) of the original interval type-2 similarity measure. We demonstrate examples of such extended fuzzy measures and provide comparisons between (different types of) interval and general type-2 fuzzy measures.
Sub-Nyquist Sampling for Power Spectrum Sensing in Cognitive Radios: A Unified Approach
Venue: arXiv cs.IT 2013
Year: 2013

In light of the ever-increasing demand for new spectral bands and the underutilization of those already allocated, the concept of Cognitive Radio (CR) has emerged. Opportunistic users could exploit temporarily vacant bands after detecting the absence of activity of their owners. One of the crucial tasks in the CR cycle is therefore spectrum sensing and detection which has to be precise and efficient. Yet, CRs typically deal with wideband signals whose Nyquist rates are very high. In this paper, we propose to reconstruct the power spectrum of such signals from sub-Nyquist samples, rather than the signal itself as done in previous work, in order to perform detection. We consider both sparse and non sparse signals as well as blind and non blind detection in the sparse case. For each one of those scenarii, we derive the minimal sampling rate allowing perfect reconstruction of the signal's power spectrum in a noise-free environment and provide power spectrum recovery techniques that achieve those rates. The analysis is performed for two different signal models considered in the literature, which we refer to as the analog and digital models, and shows that both lead to similar results. Simulations demonstrate power spectrum recovery at the minimal rate in noise-free settings and show the impact of several parameters on the detector performance, including signal-to-noise ratio (SNR), sensing time and sampling rate.
Locally Testable Codes and Cayley Graphs
Venue: arXiv cs.CC 2013
Year: 2013

We give two new characterizations of ($\F_2$-linear) locally testable error-correcting codes in terms of Cayley graphs over $\F_2^h$: \begin{enumerate} \item A locally testable code is equivalent to a Cayley graph over $\F_2^h$ whose set of generators is significantly larger than $h$ and has no short linear dependencies, but yields a shortest-path metric that embeds into $\ell_1$ with constant distortion. This extends and gives a converse to a result of Khot and Naor (2006), which showed that codes with large dual distance imply Cayley graphs that have no low-distortion embeddings into $\ell_1$. \item A locally testable code is equivalent to a Cayley graph over $\F_2^h$ that has significantly more than $h$ eigenvalues near 1, which have no short linear dependencies among them and which "explain" all of the large eigenvalues. This extends and gives a converse to a recent construction of Barak et al. (2012), which showed that locally testable codes imply Cayley graphs that are small-set expanders but have many large eigenvalues. \end{enumerate}
Manopt, a Matlab toolbox for optimization on manifolds
Venue: arXiv cs.MS 2013
Year: 2013

Optimization on manifolds is a rapidly developing branch of nonlinear optimization. Its focus is on problems where the smooth geometry of the search space can be leveraged to design efficient numerical algorithms. In particular, optimization on manifolds is well-suited to deal with rank and orthogonality constraints. Such structured constraints appear pervasively in machine learning applications, including low-rank matrix completion, sensor network localization, camera network registration, independent component analysis, metric learning, dimensionality reduction and so on. The Manopt toolbox, available at www.manopt.org, is a user-friendly, documented piece of software dedicated to simplify experimenting with state of the art Riemannian optimization algorithms. We aim particularly at reaching practitioners outside our field.
Multireference Alignment using Semidefinite Programming
Venue: arXiv cs.DS 2013
Year: 2013

The multireference alignment problem consists of estimating a signal from multiple noisy shifted observations. Inspired by existing Unique-Games approximation algorithms, we provide a semidefinite program (SDP) based relaxation which approximates the maximum likelihood estimator (MLE) for the multireference alignment problem. Although we show that the MLE problem is Unique-Games hard to approximate within any constant, we observe that our poly-time approximation algorithm for the MLE appears to perform quite well in typical instances, outperforming existing methods. In an attempt to explain this behavior we provide stability guarantees for our SDP under a random noise model on the observations. This case is more challenging to analyze than traditional semi-random instances of Unique-Games: the noise model is on vertices of a graph and translates into dependent noise on the edges. Interestingly, we show that if certain positivity constraints in the SDP are dropped, its solution becomes equivalent to performing phase correlation, a popular method used for pairwise alignment in imaging applications. Finally, we show how symmetry reduction techniques from matrix representation theory can simplify the analysis and computation of the SDP, greatly decreasing its computational cost.
CrowdGrader: Crowdsourcing the Evaluation of Homework Assignments
Venue: arXiv cs.SI 2013
Year: 2013

Crowdsourcing offers a practical method for ranking and scoring large amounts of items. To investigate the algorithms and incentives that can be used in crowdsourcing quality evaluations, we built CrowdGrader, a tool that lets students submit and collaboratively grade solutions to homework assignments. We present the algorithms and techniques used in CrowdGrader, and we describe our results and experience in using the tool for several computer-science assignments. CrowdGrader combines the student-provided grades into a consensus grade for each submission using a novel crowdsourcing algorithm that relies on a reputation system. The algorithm iterativerly refines inter-dependent estimates of the consensus grades, and of the grading accuracy of each student. On synthetic data, the algorithm performs better than alternatives not based on reputation. On our preliminary experimental data, the performance seems dependent on the nature of review errors, with errors that can be ascribed to the reviewer being more tractable than those arising from random external events. To provide an incentive for reviewers, the grade each student receives in an assignment is a combination of the consensus grade received by their submissions, and of a reviewing grade capturing their reviewing effort and accuracy. This incentive worked well in practice.
Anomaly Detections in Internet traffic Using Empirical Measures
Venue: arXiv cs.NI 2013
Year: 2013

Introducing Internet traffic anomaly detection mechanism based on large deviations results for empirical measures. Using past traffic traces we characterize network traffic during various time-of-day intervals, assuming that it is anomaly-free. Throughout, we compare the two approaches presenting their advantages and disadvantages to identify and classify temporal network anomalies. We also demonstrate how our framework can be used to monitor traffic from multiple network elements in order to identify both spatial and temporal anomalies. We validate our techniques by analyzing real traffic traces with time-stamped anomalies.
Edge-detection applied to moving sand dunes on Mars
Venue: arXiv cs.CV 2013
Year: 2013

Here we discuss the application of an edge detection filter, the Sobel filter of GIMP, to the recently discovered motion of some sand dunes on Mars. The filter allows a good comparison of an image HiRISE of 2007 and an image of 1999 recorded by the Mars Global Surveyor of the dunes in the Nili Patera caldera, measuring therefore the motion of the dunes on a longer period of time than that previously investigated.
An Integrated Framework for Diagnosis and Prognosis of Hybrid Systems
Venue: arXiv cs.SY 2013
Year: 2013

Complex systems are naturally hybrid: their dynamic behavior is both continuous and discrete. For these systems, maintenance and repair are an increasing part of the total cost of final product. Efficient diagnosis and prognosis techniques have to be adopted to detect, isolate and anticipate faults. This paper presents an original integrated theoretical framework for diagnosis and prognosis of hybrid systems. The formalism used for hybrid diagnosis is enriched in order to be able to follow the evolution of an aging law for each fault of the system. The paper presents a methodology for interleaving diagnosis and prognosis in a hybrid framework.
Design of a non-linear power system stabiliser using the concept of the feedback linearisation based on the back-stepping technique
Venue: arXiv cs.SY 2013
Year: 2013

This study proposes a feedback linearisation based on the back-stepping method with simple implementation and unique design process to design a non-linear controller with a goal of improving both steady-state and transient stability. The proposed method is designed based on a standard third-order model of synchronous generator. A comparison based on simulation is then performed between the proposed method and two conventional control schemes (i.e. conventional power system stabiliser and direct feedback linearisation). The simulation results demonstrate that fast response, robustness, damping, steady-state and transient stability as well as voltage regulation are all achieved satisfactorily.
Hierarchized block wise image approximation by greedy pursuit strategies
Venue: arXiv cs.CV 2013
Year: 2013

An approach for effective implementation of greedy selection methodologies, to approximate an image partitioned into blocks, is proposed. The method is specially designed for approximating partitions on a transformed image. It evolves by selecting, at each iteration step, i) the elements for approximating each of the blocks partitioning the image and ii) the hierarchized sequence in which the blocks are approximated to reach the required global condition on sparsity.
Small-Support Approximate Correlated Equilibria
Venue: arXiv cs.GT 2013
Year: 2013

We prove the existence of approximate correlated equilibrium of support size polylogarithmic in the number of players and the number of actions per player. In particular, using the probabilistic method, we show that there exists a multiset of polylogarithmic size such that the uniform distribution over this multiset forms an approximate correlated equilibrium. Along similar lines, we establish the existence of approximate coarse correlated equilibrium with logarithmic support. We complement these results by considering the computational complexity of determining small-support approximate equilibria. We show that random sampling can be used to efficiently determine an approximate coarse correlated equilibrium with logarithmic support. But, such a tight result does not hold for correlated equilibrium, i.e., sampling might generate an approximate correlated equilibrium of support size Ω(m) where m is the number of actions per player. Finally, we show that finding an exact correlated equilibrium with smallest possible support is NP-hard under Cook reductions, even in the case of two-player zero-sum games.
Bidimensionality of Geometric Intersection Graphs
Venue: arXiv cs.DM 2013
Year: 2013

Let B be a finite collection of geometric (not necessarily convex) bodies in the plane. Clearly, this class of geometric objects naturally generalizes the class of disks, lines, ellipsoids, and even convex polygons. We consider geometric intersection graphs GB where each body of the collection B is represented by a vertex, and two vertices of GB are adjacent if the intersection of the corresponding bodies is non-empty. For such graph classes and under natural restrictions on their maximum degree or subgraph exclusion, we prove that the relation between their treewidth and the maximum size of a grid minor is linear. These combinatorial results vastly extend the applicability of all the meta-algorithmic results of the bidimensionality theory to geometrically defined graph classes.
Verification of Semantically-Enhanced Artifact Systems (Extended Version)
Venue: arXiv cs.AI 2013
Year: 2013

Artifact-Centric systems have emerged in the last years as a suitable framework to model business-relevant entities, by combining their static and dynamic aspects. In particular, the Guard-Stage-Milestone (GSM) approach has been recently proposed to model artifacts and their lifecycle in a declarative way. In this paper, we enhance GSM with a Semantic Layer, constituted by a full-fledged OWL 2 QL ontology linked to the artifact information models through mapping specifications. The ontology provides a conceptual view of the domain under study, and allows one to understand the evolution of the artifact system at a higher level of abstraction. In this setting, we present a technique to specify temporal properties expressed over the Semantic Layer, and verify them according to the evolution in the underlying GSM model. This technique has been implemented in a tool that exploits state-of-the-art ontology-based data access technologies to manipulate the temporal properties according to the ontology and the mappings, and that relies on the GSMC model checker for verification.