OpenRaiser/Intern-Atlas huggingface dataset:
nCk sequences and their difference sequences
Venue: arXiv cs.DS 2015
Year: 2015

A nCk sequence is a sequence of n-bit numbers with k bits set. Given such a sequence C, the difference sequence D of C is subject to certain regularities that make it possible to generate D in 2|C| time, and, hence, to generate C in 3|C| time.
Condensed Unpredictability
Venue: arXiv cs.CR 2015
Year: 2015

We consider the task of deriving a key with high HILL entropy from an unpredictable source. Previous to this work, the only known way to transform unpredictability into a key that was $\eps$ indistinguishable from having min-entropy was via pseudorandomness, for example by Goldreich-Levin (GL) hardcore bits. This approach has the inherent limitation that from a source with $k$ bits of unpredictability entropy one can derive a key of length (and thus HILL entropy) at most $k-2\log(1/ε)$ bits. In many settings, e.g. when dealing with biometric data, such a $2\log(1/ε)$ bit entropy loss in not an option. Our main technical contribution is a theorem that states that in the high entropy regime, unpredictability implies HILL entropy. The loss in circuit size in this argument is exponential in the entropy gap $d$. To overcome the above restriction, we investigate if it's possible to first "condense" unpredictability entropy and make the entropy gap small. We show that any source with $k$ bits of unpredictability can be condensed into a source of length $k$ with $k-3$ bits of unpredictability entropy. Our condenser simply "abuses" the GL construction and derives a $k$ bit key from a source with $k$ bits of unpredicatibily. The original GL theorem implies nothing when extracting that many bits, but we show that in this regime, GL still behaves like a "condenser" for unpredictability. This result comes with two caveats (1) the loss in circuit size is exponential in $k$ and (2) we require that the source we start with has \emph{no} HILL entropy (equivalently, one can efficiently check if a guess is correct). We leave it as an intriguing open problem to overcome these restrictions or to prove they're inherent.
Leveraging Deep Neural Networks and Knowledge Graphs for Entity Disambiguation
Venue: arXiv cs.CL 2015
Year: 2015

Entity Disambiguation aims to link mentions of ambiguous entities to a knowledge base (e.g., Wikipedia). Modeling topical coherence is crucial for this task based on the assumption that information from the same semantic context tends to belong to the same topic. This paper presents a novel deep semantic relatedness model (DSRM) based on deep neural networks (DNN) and semantic knowledge graphs (KGs) to measure entity semantic relatedness for topical coherence modeling. The DSRM is directly trained on large-scale KGs and it maps heterogeneous types of knowledge of an entity from KGs to numerical feature vectors in a latent space such that the distance between two semantically-related entities is minimized. Compared with the state-of-the-art relatedness approach proposed by (Milne and Witten, 2008a), the DSRM obtains 19.4% and 24.5% reductions in entity disambiguation errors on two publicly available datasets respectively.
On the Global Convergence of Majorization Minimization Algorithms for Nonconvex Optimization Problems
Venue: arXiv cs.NA 2015
Year: 2015

In this paper, we study the global convergence of majorization minimization (MM) algorithms for solving nonconvex regularized optimization problems. MM algorithms have received great attention in machine learning. However, when applied to nonconvex optimization problems, the convergence of MM algorithms is a challenging issue. We introduce theory of the Kurdyka- Lojasiewicz inequality to address this issue. In particular, we show that many nonconvex problems enjoy the Kurdyka- Lojasiewicz property and establish the global convergence result of the corresponding MM procedure. We also extend our result to a well known method that called CCCP (concave-convex procedure).
Skew Cyclic codes over $\F_q+u\F_q+v\F_q+uv\F_q$
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we study skew cyclic codes over the ring $R=\F_q+u\F_q+v\F_q+uv\F_q$, where $u^{2}=u,v^{2}=v,uv=vu$, $q=p^{m}$ and $p$ is an odd prime. We investigate the structural properties of skew cyclic codes over $R$ through a decomposition theorem. Furthermore, we give a formula for the number of skew cyclic codes of length $n$ over $R.$
Inhomogeneous CTMC Model of a Call Center with Balking and Abandonment
Venue: arXiv cs.PF 2015
Year: 2015

This paper considers a nonstationary multiserver queuing model with abandonment and balking for inbound call centers. We present a continuous time Markov chain (CTMC) model which captures the important characteristics of an inbound call center and obtain a numerical solution for its transient state probabilities using uniformization method with steady-state detection. Keywords: call center, transient, Markov processes, numerical methods, uniformization, abandonment, balking
Robust hyperspectral image classification with rejection fields
Venue: arXiv cs.CV 2015
Year: 2015

In this paper we present a novel method for robust hyperspectral image classification using context and rejection. Hyperspectral image classification is generally an ill-posed image problem where pixels may belong to unknown classes, and obtaining representative and complete training sets is costly. Furthermore, the need for high classification accuracies is frequently greater than the need to classify the entire image. We approach this problem with a robust classification method that combines classification with context with classification with rejection. A rejection field that will guide the rejection is derived from the classification with contextual information obtained by using the SegSALSA algorithm. We validate our method in real hyperspectral data and show that the performance gains obtained from the rejection fields are equivalent to an increase the dimension of the training sets.
Decomposing, Comparing, and Synthesizing Access Control Expressiveness Simulations (Extended Version)
Venue: arXiv cs.CR 2015
Year: 2015

Access control is fundamental to computer security, and has thus been the subject of extensive formal study. In particular, *relative expressiveness analysis* techniques have used formal mappings called *simulations* to explore whether one access control system is capable of emulating another, thereby comparing the expressive power of these systems. Unfortunately, the notions of expressiveness simulation that have been explored vary widely, which makes it difficult to compare results in the literature, and even leads to apparent contradictions between results. Furthermore, some notions of expressiveness simulation make use of non-determinism, and thus cannot be used to define mappings between access control systems that are useful in practical scenarios. In this work, we define the minimum set of properties for an *implementable* access control simulation; i.e., a deterministic "recipe" for using one system in place of another. We then define a wide range of properties spread across several dimensions that can be enforced on top of this minimum definition. These properties define a taxonomy that can be used to separate and compare existing notions of access control simulation, many of which were previously incomparable. We position existing notions of simulation within our properties lattice by formally proving each simulation's equivalence to a corresponding set of properties. Lastly, we take steps towards bridging the gap between theory and practice by exploring the systems implications of points within our properties lattice. This shows that relative expressive analysis is more than just a theoretical tool, and can also guide the choice of the most suitable access control system for a specific application or scenario.
Exploring Integral Image Word Length Reduction Techniques for SURF Detector
Venue: arXiv cs.CV 2015
Year: 2015

Speeded Up Robust Features (SURF) is a state of the art computer vision algorithm that relies on integral image representation for performing fast detection and description of image features that are scale and rotation invariant. Integral image representation, however, has major draw back of large binary word length that leads to substantial increase in memory size. When designing a dedicated hardware to achieve real-time performance for the SURF algorithm, it is imperative to consider the adverse effects of integral image on memory size, bus width and computational resources. With the objective of minimizing hardware resources, this paper presents a novel implementation concept of a reduced word length integral image based SURF detector. It evaluates two existing word length reduction techniques for the particular case of SURF detector and extends one of these to achieve more reduction in word length. This paper also introduces a novel method to achieve integral image word length reduction for SURF detector.
Optimum Wirelessly Powered Relaying
Venue: arXiv cs.IT 2015
Year: 2015

This paper maximizes the achievable throughput of a relay-assisted wirelessly powered communications system, where an energy constrained source, helped by an energy constrained relay and both powered by a dedicated power beacon (PB), communicates with a destination. Considering the time splitting approach, the source and relay first harvest energy from the PB, which is equipped with multiple antennas, and then transmits information to the destination. Simple closed-form expressions are derived for the optimal PB energy beamforming vector and time split for energy harvesting and information transmission. Numerical results and simulations demonstrate the superior performance compared with some intuitive benchmark beamforming scheme. Also, it is found that placing the relay at the middle of the source-destination path is no longer optimal.
Multi-user lax communications: a multi-armed bandit approach
Venue: arXiv cs.LG 2015
Year: 2015

Inspired by cognitive radio networks, we consider a setting where multiple users share several channels modeled as a multi-user multi-armed bandit (MAB) problem. The characteristics of each channel are unknown and are different for each user. Each user can choose between the channels, but her success depends on the particular channel chosen as well as on the selections of other users: if two users select the same channel their messages collide and none of them manages to send any data. Our setting is fully distributed, so there is no central control. As in many communication systems, the users cannot set up a direct communication protocol, so information exchange must be limited to a minimum. We develop an algorithm for learning a stable configuration for the multi-user MAB problem. We further offer both convergence guarantees and experiments inspired by real communication networks, including comparison to state-of-the-art algorithms.
Clock Synchronization and Distributed Estimation in Highly Dynamic Networks: An Information Theoretic Approach
Venue: arXiv cs.DC 2015
Year: 2015

We consider the External Clock Synchronization problem in dynamic sensor networks. Initially, sensors obtain inaccurate estimations of an external time reference and subsequently collaborate in order to synchronize their internal clocks with the external time. For simplicity, we adopt the drift-free assumption, where internal clocks are assumed to tick at the same pace. Hence, the problem is reduced to an estimation problem, in which the sensors need to estimate the initial external time. This work is further relevant to the problem of collective approximation of environmental values by biological groups. Unlike most works on clock synchronization that assume static networks, this paper focuses on an extreme case of highly dynamic networks. Specifically, we assume a non-adaptive scheduler adversary that dictates in advance an arbitrary, yet independent, meeting pattern. Such meeting patterns fit, for example, with short-time scenarios in highly dynamic settings, where each sensor interacts with only few other arbitrary sensors. We propose an extremely simple clock synchronization algorithm that is based on weighted averages, and prove that its performance on any given independent meeting pattern is highly competitive with that of the best possible algorithm, which operates without any resource or computational restrictions, and knows the meeting pattern in advance. In particular, when all distributions involved are Gaussian, the performances of our scheme coincide with the optimal performances. Our proofs rely on an extensive use of the concept of Fisher information. We use the Cramer-Rao bound and our definition of a Fisher Channel Capacity to quantify information flows and to obtain lower bounds on collective performance. This opens the door for further rigorous quantifications of information flows within collaborative sensors.
Optimal competitiveness for the Rectilinear Steiner Arborescence problem
Venue: arXiv cs.DS 2015
Year: 2015

We present optimal online algorithms for two related known problems involving Steiner Arborescence, improving both the lower and the upper bounds. One of them is the well studied continuous problem of the {\em Rectilinear Steiner Arborescence} ($RSA$). We improve the lower bound and the upper bound on the competitive ratio for $RSA$ from $O(\log N)$ and $Ω(\sqrt{\log N})$ to $Θ(\frac{\log N}{\log \log N})$, where $N$ is the number of Steiner points. This separates the competitive ratios of $RSA$ and the Symetric-$RSA$, two problems for which the bounds of Berman and Coulston is STOC 1997 were identical. The second problem is one of the Multimedia Content Distribution problems presented by Papadimitriou et al. in several papers and Charikar et al. SODA 1998. It can be viewed as the discrete counterparts (or a network counterpart) of $RSA$. For this second problem we present tight bounds also in terms of the network size, in addition to presenting tight bounds in terms of the number of Steiner points (the latter are similar to those we derived for $RSA$).
HetHetNets: Heterogeneous Traffic Distribution in Heterogeneous Wireless Cellular Networks
Venue: arXiv cs.NI 2015
Year: 2015

A recent approach in modeling and analysis of the supply and demand in heterogeneous wireless cellular networks has been the use of two independent Poisson point processes (PPPs) for the locations of base stations (BSs) and user equipments (UEs). This popular approach has two major shortcomings. First, although the PPP model may be a fitting one for the BS locations, it is less adequate for the UE locations mainly due to the fact that the model is not adjustable (tunable) to represent the severity of the heterogeneity (non-uniformity) in the UE locations. Besides, the independence assumption between the two PPPs does not capture the often-observed correlation between the UE and BS locations. This paper presents a novel heterogeneous spatial traffic modeling which allows statistical adjustment. Simple and non-parameterized, yet sufficiently accurate, measures for capturing the traffic characteristics in space are introduced. Only two statistical parameters related to the UE distribution, namely, the coefficient of variation (the normalized second-moment), of an appropriately defined inter-UE distance measure, and correlation coefficient (the normalized cross-moment) between UE and BS locations, are adjusted to control the degree of heterogeneity and the bias towards the BS locations, respectively. This model is used in heterogeneous wireless cellular networks (HetNets) to demonstrate the impact of heterogeneous and BS-correlated traffic on the network performance. This network is called HetHetNet since it has two types of heterogeneity: heterogeneity in the infrastructure (supply), and heterogeneity in the spatial traffic distribution (demand).
Mobile Crowd Sensing and Computing: When Participatory Sensing Meets Participatory Social Media
Venue: arXiv cs.HC 2015
Year: 2015

With the development of mobile sensing and mobile social networking techniques, Mobile Crowd Sensing and Computing (MCSC), which leverages heterogeneous crowdsourced data for large-scale sensing, has become a leading paradigm. Built on top of the participatory sensing vision, MCSC has two characterizing features: (1) it leverages heterogeneous crowdsourced data from two data sources: participatory sensing and participatory social media; and (2) it presents the fusion of human and machine intelligence (HMI) in both the sensing and computing process. This paper characterizes the unique features and challenges of MCSC. We further present early efforts on MCSC to demonstrate the benefits of aggregating heterogeneous crowdsourced data.
Random Interruptions in Cooperation for Spectrum Sensing in Cognitive Radio Networks
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, a new cooperation structure for spectrum sensing in cognitive radio networks is proposed which outperforms the existing commonly-used ones in terms of energy efficiency. The efficiency is achieved in the proposed design by introducing random interruptions in the cooperation process between the sensing nodes and the fusion center, along with a compensation process at the fusion center. Regarding the hypothesis testing problem concerned, first, the proposed system behavior is thoroughly analyzed and its associated likelihood-ratio test (LRT) is provided. Next, based on a general linear fusion rule, statistics of the global test summary are derived and the sensing quality is characterized in terms of the probability of false alarm and the probability of detection. Then, optimization of the overall detection performance is formulated according to the Neyman-Pearson criterion (NPC) and it is discussed that the optimization required is indeed a decision-making process with uncertainty which incurs prohibitive computational complexity. The NPC is then modified to achieve a good affordable solution by using semidefinite programming (SDP) techniques and it is shown that this new solution is nearly optimal according to the deflection criterion. Finally, effectiveness of the proposed architecture and its associated SDP are demonstrated by simulation results.
Reachability of Consensus and Synchronizing Automata
Venue: arXiv cs.DC 2015
Year: 2015

We consider the problem of determining the existence of a sequence of matrices driving a discrete-time consensus system to consensus. We transform this problem into one of the existence of a product of the transition (stochastic) matrices that has a positive column. We then generalize some results from automata theory to sets of stochastic matrices. We obtain as a main result a polynomial-time algorithm to decide the existence of a sequence of matrices achieving consensus.
Strictly Implicit Priority Queues: On the Number of Moves and Worst-Case Time
Venue: arXiv cs.DS 2015
Year: 2015

The binary heap of Williams (1964) is a simple priority queue characterized by only storing an array containing the elements and the number of elements $n$ - here denoted a strictly implicit priority queue. We introduce two new strictly implicit priority queues. The first structure supports amortized $O(1)$ time Insert and $O(\log n)$ time ExtractMin operations, where both operations require amortized $O(1)$ element moves. No previous implicit heap with $O(1)$ time Insert supports both operations with $O(1)$ moves. The second structure supports worst-case $O(1)$ time Insert and $O(\log n)$ time (and moves) ExtractMin operations. Previous results were either amortized or needed $O(\log n)$ bits of additional state information between operations.
Applied Metamodelling: A Foundation for Language Driven Development (Third Edition)
Venue: arXiv cs.SE 2015
Year: 2015

Modern day system developers have some serious problems to contend with. The systems they develop are becoming increasingly complex as customers demand richer functionality delivered in ever shorter timescales. They have to manage a huge diversity of implementation technologies, design techniques and development processes: everything from scripting languages to web-services to the latest 'silver bullet' design abstraction. To add to that, nothing stays still: today's 'must have' technology rapidly becomes tomorrow's legacy problem that must be managed along with everything else. How can these problems be dealt with? In this book we propose that there is a common foundation to their resolution: languages. Languages are the primary way in which system developers communicate, design and implement systems. Languages provide abstractions that can encapsulate complexity, embrace the diversity of technologies and design abstractions, and unite modern and legacy systems.
Comparison Clustering using Cosine and Fuzzy set based Similarity Measures of Text Documents
Venue: arXiv cs.IR 2015
Year: 2015

Keeping in consideration the high demand for clustering, this paper focuses on understanding and implementing K-means clustering using two different similarity measures. We have tried to cluster the documents using two different measures rather than clustering it with Euclidean distance. Also a comparison is drawn based on accuracy of clustering between fuzzy and cosine similarity measure. The start time and end time parameters for formation of clusters are used in deciding optimum similarity measure.
Segmentation and Restoration of Images on Surfaces by Parametric Active Contours with Topology Changes
Venue: arXiv cs.CV 2015
Year: 2015

In this article, a new method for segmentation and restoration of images on two-dimensional surfaces is given. Active contour models for image segmentation are extended to images on surfaces. The evolving curves on the surfaces are mathematically described using a parametric approach. For image restoration, a diffusion equation with Neumann boundary conditions is solved in a postprocessing step in the individual regions. Numerical schemes are presented which allow to efficiently compute segmentations and denoised versions of images on surfaces. Also topology changes of the evolving curves are detected and performed using a fast sub-routine. Finally, several experiments are presented where the developed methods are applied on different artificial and real images defined on different surfaces.
An Improved Private Mechanism for Small Databases
Venue: arXiv cs.DS 2015
Year: 2015

We study the problem of answering a workload of linear queries $\mathcal{Q}$, on a database of size at most $n = o(|\mathcal{Q}|)$ drawn from a universe $\mathcal{U}$ under the constraint of (approximate) differential privacy. Nikolov, Talwar, and Zhang~\cite{NTZ} proposed an efficient mechanism that, for any given $\mathcal{Q}$ and $n$, answers the queries with average error that is at most a factor polynomial in $\log |\mathcal{Q}|$ and $\log |\mathcal{U}|$ worse than the best possible. Here we improve on this guarantee and give a mechanism whose competitiveness ratio is at most polynomial in $\log n$ and $\log |\mathcal{U}|$, and has no dependence on $|\mathcal{Q}|$. Our mechanism is based on the projection mechanism of Nikolov, Talwar, and Zhang, but in place of an ad-hoc noise distribution, we use a distribution which is in a sense optimal for the projection mechanism, and analyze it using convex duality and the restricted invertibility principle.