OpenRaiser/Intern-Atlas huggingface dataset:
Privacy Architectures: Reasoning About Data Minimisation and Integrity
Venue: arXiv cs.CR 2014
Year: 2014

Privacy by design will become a legal obligation in the European Community if the Data Protection Regulation eventually gets adopted. However, taking into account privacy requirements in the design of a system is a challenging task. We propose an approach based on the specification of privacy architectures and focus on a key aspect of privacy, data minimisation, and its tension with integrity requirements. We illustrate our formal framework through a smart metering case study.
On the structure of classical realizability models of ZF
Venue: arXiv cs.LO 2014
Year: 2014

The technique of "classical realizability" is an extension of the method of "forcing"; it permits to extend the Curry-Howard correspondence between proofs and programs, to Zermelo-Fraenkel set theory and to build new models of ZF, called "realizability models". The structure of these models is, in general, much more complicated than that of the particular case of "forcing models". We show here that the class of constructible sets of any realizability model is an elementary extension of the constructibles of the ground model (a trivial fact in the case of forcing, since these classes are identical). It follows that Shoenfield absoluteness theorem applies to realizability models.
The Erdős-Hajnal Conjecture for Long Holes and Anti-holes
Venue: arXiv cs.DM 2014
Year: 2014

Erdős and Hajnal conjectured that, for every graph $H$, there exists a constant $c_H$ such that every graph $G$ on $n$ vertices which does not contain any induced copy of $H$ has a clique or a stable set of size $n^{c_H}$. We prove that for every $k$, there exists $c_k>0$ such that every graph $G$ on $n$ vertices not inducing a cycle of length at least $k$ nor its complement contains a clique or a stable set of size $n^{c_k}$.
A model of grassroots changes in linguistic systems
Venue: arXiv cs.CL 2014
Year: 2014

Linguistic norms emerge in human communities because people imitate each other. A shared linguistic system provides people with the benefits of shared knowledge and coordinated planning. Once norms are in place, why would they ever change? This question, echoing broad questions in the theory of social dynamics, has particular force in relation to language. By definition, an innovator is in the minority when the innovation first occurs. In some areas of social dynamics, important minorities can strongly influence the majority through their power, fame, or use of broadcast media. But most linguistic changes are grassroots developments that originate with ordinary people. Here, we develop a novel model of communicative behavior in communities, and identify a mechanism for arbitrary innovations by ordinary people to have a good chance of being widely adopted. To imitate each other, people must form a mental representation of what other people do. Each time they speak, they must also decide which form to produce themselves. We introduce a new decision function that enables us to smoothly explore the space between two types of behavior: probability matching (matching the probabilities of incoming experience) and regularization (producing some forms disproportionately often). Using Monte Carlo methods, we explore the interactions amongst the degree of regularization, the distribution of biases in a network, and the network position of the innovator. We identify two regimes for the widespread adoption of arbritrary innovations, viewed as informational cascades in the network. With moderate regularization of experienced input, average people (not well-connected people) are the most likely source of successful innovations. Our results shed light on a major outstanding puzzle in the theory of language change. The framework also holds promise for understanding the dynamics of other social norms.
An Evasion and Counter-Evasion Study in Malicious Websites Detection
Venue: arXiv cs.CR 2014
Year: 2014

Malicious websites are a major cyber attack vector, and effective detection of them is an important cyber defense task. The main defense paradigm in this regard is that the defender uses some kind of machine learning algorithms to train a detection model, which is then used to classify websites in question. Unlike other settings, the following issue is inherent to the problem of malicious websites detection: the attacker essentially has access to the same data that the defender uses to train its detection models. This 'symmetry' can be exploited by the attacker, at least in principle, to evade the defender's detection models. In this paper, we present a framework for characterizing the evasion and counter-evasion interactions between the attacker and the defender, where the attacker attempts to evade the defender's detection models by taking advantage of this symmetry. Within this framework, we show that an adaptive attacker can make malicious websites evade powerful detection models, but proactive training can be an effective counter-evasion defense mechanism. The framework is geared toward the popular detection model of decision tree, but can be adapted to accommodate other classifiers.
Automatic Removal of Marginal Annotations in Printed Text Document
Venue: arXiv cs.CV 2014
Year: 2014

Recovering the original printed texts from a document with added handwritten annotations in the marginal area is one of the challenging problems, especially when the original document is not available. Therefore, this paper aims at salvaging automatically the original document from the annotated document by detecting and removing any handwritten annotations that appear in the marginal area of the document without any loss of information. Here a two stage algorithm is proposed, where in the first stage due to approximate marginal boundary detection with horizontal and vertical projection profiles, all of the marginal annotations along with some part of the original printed text that may appear very close to the marginal boundary are removed. Therefore as a second stage, using the connected components, a strategy is applied to bring back the printed text components cropped during the first stage. The proposed method is validated using a dataset of 50 documents having complex handwritten annotations, which gives an overall accuracy of 89.01% in removing the marginal annotations and 97.74% in case of retrieving the original printed text document.
Blind Construction of Optimal Nonlinear Recursive Predictors for Discrete Sequences
Venue: arXiv cs.LG 2014
Year: 2014

We present a new method for nonlinear prediction of discrete random sequences under minimal structural assumptions. We give a mathematical construction for optimal predictors of such processes, in the form of hidden Markov models. We then describe an algorithm, CSSR (Causal-State Splitting Reconstruction), which approximates the ideal predictor from data. We discuss the reliability of CSSR, its data requirements, and its performance in simulations. Finally, we compare our approach to existing methods using variablelength Markov models and cross-validated hidden Markov models, and show theoretically and experimentally that our method delivers results superior to the former and at least comparable to the latter.
Robust Graphical Modeling with t-Distributions
Venue: arXiv cs.LG 2014
Year: 2014

Graphical Gaussian models have proven to be useful tools for exploring network structures based on multivariate data. Applications to studies of gene expression have generated substantial interest in these models, and resulting recent progress includes the development of fitting methodology involving penalization of the likelihood function. In this paper we advocate the use of the multivariate t and related distributions for more robust inference of graphs. In particular, we demonstrate that penalized likelihood inference combined with an application of the EM algorithm provides a simple and computationally efficient approach to model selection in the t-distribution case.
Non-Convex Rank Minimization via an Empirical Bayesian Approach
Venue: arXiv cs.LG 2014
Year: 2014

In many applications that require matrix solutions of minimal rank, the underlying cost function is non-convex leading to an intractable, NP-hard optimization problem. Consequently, the convex nuclear norm is frequently used as a surrogate penalty term for matrix rank. The problem is that in many practical scenarios there is no longer any guarantee that we can correctly estimate generative low-rank matrices of interest, theoretical special cases notwithstanding. Consequently, this paper proposes an alternative empirical Bayesian procedure build upon a variational approximation that, unlike the nuclear norm, retains the same globally minimizing point estimate as the rank function under many useful constraints. However, locally minimizing solutions are largely smoothed away via marginalization, allowing the algorithm to succeed when standard convex relaxations completely fail. While the proposed methodology is generally applicable to a wide range of low-rank applications, we focus our attention on the robust principal component analysis problem (RPCA), which involves estimating an unknown low-rank matrix with unknown sparse corruptions. Theoretical and empirical evidence are presented to show that our method is potentially superior to related MAP-based approaches, for which the convex principle component pursuit (PCP) algorithm (Candes et al., 2011) can be viewed as a special case.
POMDPs under Probabilistic Semantics
Venue: arXiv cs.AI 2014
Year: 2014

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 lambda_1 in (0,1]; and (ii) qualitative constraint which is a special case of quantitative constraint with lambda_1=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.
One-Class Support Measure Machines for Group Anomaly Detection
Venue: arXiv cs.LG 2014
Year: 2014

We propose one-class support measure machines (OCSMMs) for group anomaly detection which aims at recognizing anomalous aggregate behaviors of data points. The OCSMMs generalize well-known one-class support vector machines (OCSVMs) to a space of probability measures. By formulating the problem as quantile estimation on distributions, we can establish an interesting connection to the OCSVMs and variable kernel density estimators (VKDEs) over the input space on which the distributions are defined, bridging the gap between large-margin methods and kernel density estimators. In particular, we show that various types of VKDEs can be considered as solutions to a class of regularization problems studied in this paper. Experiments on Sloan Digital Sky Survey dataset and High Energy Particle Physics dataset demonstrate the benefits of the proposed framework in real-world applications.
Self-stabilizing algorithms for Connected Vertex Cover and Clique decomposition problems
Venue: arXiv cs.DC 2014
Year: 2014

In many wireless networks, there is no fixed physical backbone nor centralized network management. The nodes of such a network have to self-organize in order to maintain a virtual backbone used to route messages. Moreover, any node of the network can be a priori at the origin of a malicious attack. Thus, in one hand the backbone must be fault-tolerant and in other hand it can be useful to monitor all network communications to identify an attack as soon as possible. We are interested in the minimum \emph{Connected Vertex Cover} problem, a generalization of the classical minimum Vertex Cover problem, which allows to obtain a connected backbone. Recently, Delbot et al.~\cite{DelbotLP13} proposed a new centralized algorithm with a constant approximation ratio of $2$ for this problem. In this paper, we propose a distributed and self-stabilizing version of their algorithm with the same approximation guarantee. To the best knowledge of the authors, it is the first distributed and fault-tolerant algorithm for this problem. The approach followed to solve the considered problem is based on the construction of a connected minimal clique partition. Therefore, we also design the first distributed self-stabilizing algorithm for this problem, which is of independent interest.
A sub-constant improvement in approximating the positive semidefinite Grothendieck problem
Venue: arXiv cs.DS 2014
Year: 2014

Semidefinite relaxations are a powerful tool for approximately solving combinatorial optimization problems such as MAX-CUT and the Grothendieck problem. By exploiting a bounded rank property of extreme points in the semidefinite cone, we make a sub-constant improvement in the approximation ratio of one such problem. Precisely, we describe a polynomial-time algorithm for the positive semidefinite Grothendieck problem -- based on rounding from the standard relaxation -- that achieves a ratio of $2/π+ Θ(1/{\sqrt n})$, whereas the previous best is $2/π+ Θ(1/n)$. We further show a corresponding integrality gap of $2/π+\tilde{O}(1/n^{1/3})$.
The Family Holiday Gathering Problem or Fair and Periodic Scheduling of Independent Sets
Venue: arXiv cs.DS 2014
Year: 2014

We introduce and examine the {\em Holiday Gathering Problem} which models the difficulty that couples have when trying to decide with which parents should they spend the holiday. Our goal is to schedule the family gatherings so that the parents that will be {\em happy}, i.e.\ all their children will be home {\em simultaneously} for the holiday festivities, while minimizing the number of consecutive holidays in which parents are not happy. The holiday gathering problem is closely related to several classical problems in computer science, such as the {\em dining philosophers problem} on a general graph and periodic scheduling,and has applications in scheduling of transmissions made by cellular radios. We also show interesting connections between periodic scheduling, coloring, and universal prefix free encodings. The combinatorial definition of the Holiday Gathering Problem is: given a graph $G$, find an infinite sequence of independent-sets of $G$. The objective function is to minimize, for every node $v$, the maximal gap between two appearances of $v$. In good solutions this gap depends on local properties of the node (i.e., its degree) and the the solution should be periodic, i.e.\ a node appears every fixed number of periods. We show a coloring-based construction where the period of each node colored with the $c$ is at most $2^{1+\log^*c}\cdot\prod_{i=0}^{\log^*c} \log^{(i)}c$ (where $\log^{(i)}$ means iterating the $\log$ function $i$ times). This is achieved via a connection with {\it prefix-free encodings}. We prove that this is the best possible for coloring-based solutions. We also show a construction with period at most $2d$ for a node of degree $d$.
Physical Computing With No Clock to Implement the Gaussian Pyramid of SIFT Algorithm
Venue: arXiv cs.CV 2014
Year: 2014

Physical computing is a technology utilizing the nature of electronic devices and circuit topology to cope with computing tasks. In this paper, we propose an active circuit network to implement multi-scale Gaussian filter, which is also called Gaussian Pyramid in image preprocessing. Various kinds of methods have been tried to accelerate the key stage in image feature extracting algorithm these years. Compared with existing technologies, GPU parallel computing and FPGA accelerating technology, physical computing has great advantage on processing speed as well as power consumption. We have verified that processing time to implement the Gaussian pyramid of the SIFT algorithm stands on nanosecond level through the physical computing technology, while other existing methods all need at least hundreds of millisecond. With an estimate on the stray capacitance of the circuit, the power consumption is around 670pJ to filter a 256x256 image. To the best of our knowledge, this is the most fast processing technology to accelerate the SIFT algorithm, and it is also a rather energy-efficient method, thanks to the proposed physical computing technology.
Wireless Powered Communication: Opportunities and Challenges
Venue: arXiv cs.NI 2014
Year: 2014

The performance of wireless communication is fundamentally constrained by the limited battery life of wireless devices, whose operations are frequently disrupted due to the need of manual battery replacement/recharging. The recent advance in radio frequency (RF) enabled wireless energy transfer (WET) technology provides an attractive solution named wireless powered communication (WPC), where the wireless devices are powered by dedicated wireless power transmitters to provide continuous and stable microwave energy over the air. As a key enabling technology for truly perpetual communications, WPC opens up the potential to build a network with larger throughput, higher robustness, and increased flexibility compared to its battery-powered counterpart. However, the combination of wireless energy and information transmissions also raises many new research problems and implementation issues to be addressed. In this article, we provide an overview of state-of-the-art RF-enabled WET technologies and their applications to wireless communications, with highlights on the key design challenges, solutions, and opportunities ahead.
Gap-weighted subsequences for automatic cognate identification and phylogenetic inference
Venue: arXiv cs.CL 2014
Year: 2014

In this paper, we describe the problem of cognate identification and its relation to phylogenetic inference. We introduce subsequence based features for discriminating cognates from non-cognates. We show that subsequence based features perform better than the state-of-the-art string similarity measures for the purpose of cognate identification. We use the cognate judgments for the purpose of phylogenetic inference and observe that these classifiers infer a tree which is close to the gold standard tree. The contribution of this paper is the use of subsequence features for cognate identification and to employ the cognate judgments for phylogenetic inference.
FP//LINSPACE computability of Riemann zeta function in Ko-Friedman model
Venue: arXiv cs.CC 2014
Year: 2014

In the present paper, we construct an algorithm for the evaluation of real Riemann zeta function $ζ(s)$ for all real $s$, $s>1$, in polynomial time and linear space on Turing machines in Ko-Friedman model. The algorithms is based on a series expansion of real Riemann zeta function $ζ(s)$ (the series globally convergents) and uses algorithms for the evaluation of real function $(1+x)^h$ and hypergeometric series in polynomial time and linear space. The algorithm from the present paper modified in an obvious way to work with the complex numbers can be used to evaluate complex Riemann zeta function $ζ(s)$ for $s=σ+\mathbf{i}t$, $σ\ne 1$ (so, also for the case of $σ<1$), in polynomial time and linear space in $n$ wherein $2^{-n}$ is a precision of the computation; the modified algorithm will be also polynomial time and linear space in $\lceil \log_2(t)\rceil$ and exponential time and exponential space in $\lceil \log_2(σ)\rceil$.
Trace representation of pseudorandom binary sequences derived from Euler quotients
Venue: arXiv cs.CR 2014
Year: 2014

We give the trace representation of a family of binary sequences derived from Euler quotients by determining the corresponding defining polynomials. Trace representation can help us producing the sequences efficiently and analyzing their cryptographic properties, such as linear complexity.
An Algorithm for Deciding the Summability of Bivariate Rational Functions
Venue: arXiv cs.SC 2014
Year: 2014

Let $Δ_x f(x,y)=f(x+1,y)-f(x,y)$ and $Δ_y f(x,y)=f(x,y+1)-f(x,y)$ be the difference operators with respect to $x$ and $y$. A rational function $f(x,y)$ is called summable if there exist rational functions $g(x,y)$ and $h(x,y)$ such that $f(x,y)=Δ_x g(x,y) + Δ_y h(x,y)$. Recently, Chen and Singer presented a method for deciding whether a rational function is summable. To implement their method in the sense of algorithms, we need to solve two problems. The first is to determine the shift equivalence of two bivariate polynomials. We solve this problem by presenting an algorithm for computing the dispersion sets of any two bivariate polynomials. The second is to solve a univariate difference equation in an algebraically closed field. By considering the irreducible factorization of the denominator of $f(x,y)$ in a general field, we present a new criterion which requires only finding a rational solution of a bivariate difference equation. This goal can be achieved by deriving a universal denominator of the rational solutions and a degree bound on the numerator. Combining these two algorithms, we can decide the summability of a bivariate rational function.
Universal Streaming
Venue: arXiv cs.DS 2014
Year: 2014

Given a stream of data, a typical approach in streaming algorithms is to design a sophisticated algorithm with small memory that computes a specific statistic over the streaming data. Usually, if one wants to compute a different statistic after the stream is gone, it is impossible. But what if we want to compute a different statistic after the fact? In this paper, we consider the following fascinating possibility: can we collect some small amount of specific data during the stream that is "universal," i.e., where we do not know anything about the statistics we will want to later compute, other than the guarantee that had we known the statistic ahead of time, it would have been possible to do so with small memory? In other words, is it possible to collect some data in small space during the stream, such that any other statistic that can be computed with comparable space can be computed after the fact? This is indeed what we introduce (and show) in this paper with matching upper and lower bounds: we show that it is possible to collect universal statistics of polylogarithmic size, and prove that these universal statistics allow us after the fact to compute all other statistics that are computable with similar amounts of memory. We show that this is indeed possible, both for the standard unbounded streaming model and the sliding window streaming model.
Complex polynomials in engineering
Venue: arXiv cs.SY 2014
Year: 2014

Techniques for the evaluation of complex polynomials with one and two variables are introduced. Polynomials arise in may areas such as control systems, image and signal processing, coding theory, electrical networks, etc., and their evaluations are time consuming. This paper introduces new evaluation algorithms that are straightforward with fewer arithmetic operations.