OpenRaiser/Intern-Atlas huggingface dataset:
Approximating Majority Depth
Venue: arXiv cs.CG 2013
Year: 2013

We consider the problem of approximating the majority depth (Liu and Singh, 1993) of a point q with respect to an n-point set, S, by random sampling. At the heart of this problem is a data structures question: How can we preprocess a set of n lines so that we can quickly test whether a randomly selected vertex in the arrangement of these lines is above or below the median level. We describe a Monte-Carlo data structure for this problem that can be constructed in O(nlog n) time, can answer queries O((log n)^{4/3}) expected time, and answers correctly with high probability.
Chaotic Method for Generating q-Gaussian Random Variables
Venue: arXiv cs.IT 2013
Year: 2013

This study proposes a pseudo random number generator of q-Gaussian random variables for a range of q values, -infinity < q < 3, based on deterministic chaotic map dynamics. Our method consists of chaotic maps on the unit circle and map dynamics based on the piecewise linear map. We perform the q-Gaussian random number generator for several values of q and conduct both Kolmogorov-Smirnov (KS) and Anderson-Darling (AD) tests. The q-Gaussian samples generated by our proposed method pass the KS test at more than 5% significance level for values of q ranging from -1.0 to 2.7, while they pass the AD test at more than 5% significance level for q ranging from -1 to 2.4.
Chaotic multi-objective optimization based design of fractional order PIλDμ controller in AVR system
Venue: arXiv cs.SY 2013
Year: 2013

In this paper, a fractional order (FO) PIλDμcontroller is designed to take care of various contradictory objective functions for an Automatic Voltage Regulator (AVR) system. An improved evolutionary Non-dominated Sorting Genetic Algorithm II (NSGA II), which is augmented with a chaotic map for greater effectiveness, is used for the multi-objective optimization problem. The Pareto fronts showing the trade-off between different design criteria are obtained for the PIλDμand PID controller. A comparative analysis is done with respect to the standard PID controller to demonstrate the merits and demerits of the fractional order PIλDμcontroller.
Dexpler: Converting Android Dalvik Bytecode to Jimple for Static Analysis with Soot
Venue: arXiv cs.SE 2013
Year: 2013

This paper introduces Dexpler, a software package which converts Dalvik bytecode to Jimple. Dexpler is built on top of Dedexer and Soot. As Jimple is Soot's main internal rep- resentation of code, the Dalvik bytecode can be manipu- lated with any Jimple based tool, for instance for performing point-to or flow analysis.
Self-Healing Algorithms of Byzantine Faults
Venue: arXiv cs.CR 2013
Year: 2013

Recent years have seen significant interest in designing networks that are self-healing in the sense that they can automatically recover from adversarial attacks. Previous work shows that it is possible for a network to automatically recover, even when an adversary repeatedly deletes nodes in the network. However, there have not yet been any algorithms that self-heal in the case where an adversary takes over nodes in the network. In this paper, we address this gap. In particular, we describe a communication network over n nodes that ensures the following properties, even when an adversary controls up to t <= (1/8 - ε)n nodes, for any non-negative ε. First, the network provides a point-to-point communication with bandwidth and latency costs that are asymptotically optimal. Second, the expected total number of message corruptions is O(t(log* n)^2) before the adversarially controlled nodes are effectively quarantined so that they cause no more corruptions. Empirical results show that our algorithm can reduce the bandwidth cost by up to a factor of 70.
Iterated Space-Time Code Constructions from Cyclic Algebras
Venue: arXiv cs.IT 2013
Year: 2013

We propose a full-rate iterated space-time code construction, to design 2n-dimensional codes from n-dimensional cyclic algebra based codes. We give a condition to determine whether the resulting codes satisfy the full-diversity property, and study their maximum likelihood decoding complexity with respect to sphere decoding. Particular emphasis is given to the cases n = 2, sometimes referred to as MIDO (multiple input double output) codes, and n = 3. In the process, we derive an interesting way of obtaining division algebras, and study their center and maximal subfield.
Filter-and-Forward Transparent Relay Design for OFDM Systems
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, the filter-and-forward (FF) relay design for orthogonal frequency-division multiplexing (OFDM) transmission systems is considered to improve the system performance over simple amplify-and-forward (AF) relaying. Unlike conventional OFDM relays performing OFDM demodulation and remodulation, to reduce processing complexity, the proposed FF relay directly filters the incoming signal in time domain with a finite impulse response (FIR) and forwards the filtered signal to the destination. Three design criteria are considered to optimize the relay filter. The first criterion is the minimization of the relay transmit power subject to per-subcarrier signal-to-noise ratio (SNR) constraints, the second is the maximization of the worst subcarrier channel SNR subject to source and relay transmit power constraints, and the third is the maximization of data rate subject to source and relay transmit power constraints. It is shown that the first problem reduces to a semi-definite programming (SDP) problem by semi-definite relaxation and the solution to the relaxed SDP problem has rank one under a mild condition. For the latter two problems, the problem of joint source power allocation and relay filter design is considered and an efficient algorithm is proposed for each problem based on alternating optimization and the projected gradient method (PGM). Numerical results show that the proposed FF relay significantly outperforms simple AF relays with insignificant increase in complexity. Thus, the proposed FF relay provides a practical alternative to the AF relaying scheme for OFDM transmission.
Optimal epsilon-biased sets with just a little randomness
Venue: arXiv cs.CC 2013
Year: 2013

Subsets of F_2^n that are eps-biased, meaning that the parity of any set of bits is even or odd with probability eps close to 1/2, are powerful tools for derandomization. A simple randomized construction shows that such sets exist of size O(n/eps^2), and known deterministic constructions achieve sets of size O(n/eps^3), O(n^2/eps^2), and O((n/eps^2)^{5/4}). Rather than derandomizing these sets completely in exchange for making them larger, we attempt a partial derandomization while keeping them small, constructing sets of size O(n/eps^2) with as few random bits as possible. The naive randomized construction requires O(n^2/eps^2) random bits. We give two constructions. The first uses Nisan's space-bounded pseudorandom generator to partly derandomize a folklore probabilistic construction of an error-correcting code, and requires O(n log (1/eps)) bits. Our second construction requires O(n log (n/eps)) bits, but is more elementary; it adds randomness to a Legendre symbol construction on Alon, Goldreich, Håstad, and Peralta, and uses Weil sums to bound high moments of the bias.
A History of Flips in Combinatorial Triangulations
Venue: arXiv cs.CG 2013
Year: 2013

Given two combinatorial triangulations, how many edge flips are necessary and sufficient to convert one into the other? This question has occupied researchers for over 75 years. We provide a comprehensive survey, including full proofs, of the various attempts to answer it.
Conditional Kolmogorov Complexity and Universal Probability
Venue: arXiv cs.IT 2013
Year: 2013

The Coding Theorem of L.A. Levin connects unconditional prefix Kolmogorov complexity with the discrete universal distribution. There are conditional versions referred to in several publications but as yet there exist no written proofs in English. Here we provide those proofs. They use a different definition than the standard one for the conditional version of the discrete universal distribution. Under the classic definition of conditional probability, there is no conditional version of the Coding Theorem.
CloudMine: Multi-Party Privacy-Preserving Data Analytics Service
Venue: arXiv cs.CR 2013
Year: 2013

An increasing number of businesses are replacing their data storage and computation infrastructure with cloud services. Likewise, there is an increased emphasis on performing analytics based on multiple datasets obtained from different data sources. While ensuring security of data and computation outsourced to a third party cloud is in itself challenging, supporting analytics using data distributed across multiple, independent clouds is even further from trivial. In this paper we present CloudMine, a cloud-based service which allows multiple data owners to perform privacy-preserved computation over the joint data using their clouds as delegates. CloudMine protects data privacy with respect to semi-honest data owners and semi-honest clouds. It furthermore ensures the privacy of the computation outputs from the curious clouds. It allows data owners to reliably detect if their cloud delegates have been lazy when carrying out the delegated computation. CloudMine can run as a centralized service on a single cloud, or as a distributed service over multiple, independent clouds. CloudMine supports a set of basic computations that can be used to construct a variety of highly complex, distributed privacy-preserving data analytics. We demonstrate how a simple instance of CloudMine (secure sum service) is used to implement three classical data mining tasks (classification, association rule mining and clustering) in a cloud environment. We experiment with a prototype of the service, the results of which suggest its practicality for supporting privacy-preserving data analytics as a (multi) cloud-based service.
Manipulation and Control Complexity of Schulze Voting
Venue: arXiv cs.GT 2013
Year: 2013

Schulze voting is a recently introduced voting system enjoying unusual popularity and a high degree of real-world use, with users including the Wikimedia foundation, several branches of the Pirate Party, and MTV. It is a Condorcet voting system that determines the winners of an election using information about paths in a graph representation of the election. We resolve the complexity of many electoral control cases for Schulze voting. We find that it falls short of the best known voting systems in terms of control resistance, demonstrating vulnerabilities of concern to some prospective users of the system.
Reachability-based Acyclicity Analysis by Abstract Interpretation
Venue: arXiv cs.PL 2013
Year: 2013

In programming languages with dynamic use of memory, such as Java, knowing that a reference variable x points to an acyclic data structure is valuable for the analysis of termination and resource usage (e.g., execution time or memory consumption). For instance, this information guarantees that the depth of the data structure to which x points is greater than the depth of the data structure pointed to by x.f for any field f of x. This, in turn, allows bounding the number of iterations of a loop which traverses the structure by its depth, which is essential in order to prove the termination or infer the resource usage of the loop. The present paper provides an Abstract-Interpretation-based formalization of a static analysis for inferring acyclicity, which works on the reduced product of two abstract domains: reachability, which models the property that the location pointed to by a variable w can be reached by dereferencing another variable v (in this case, v is said to reach w); and cyclicity, modeling the property that v can point to a cyclic data structure. The analysis is proven to be sound and optimal with respect to the chosen abstraction.
Binary Jumbled String Matching for Highly Run-Length Compressible Texts
Venue: arXiv cs.DS 2013
Year: 2013

The Binary Jumbled String Matching problem is defined as: Given a string $s$ over $\{a,b\}$ of length $n$ and a query $(x,y)$, with $x,y$ non-negative integers, decide whether $s$ has a substring $t$ with exactly $x$ $a$'s and $y$ $b$'s. Previous solutions created an index of size O(n) in a pre-processing step, which was then used to answer queries in constant time. The fastest algorithms for construction of this index have running time $O(n^2/\log n)$ [Burcsi et al., FUN 2010; Moosa and Rahman, IPL 2010], or $O(n^2/\log^2 n)$ in the word-RAM model [Moosa and Rahman, JDA 2012]. We propose an index constructed directly from the run-length encoding of $s$. The construction time of our index is $O(n+ρ^2\log ρ)$, where O(n) is the time for computing the run-length encoding of $s$ and $ρ$ is the length of this encoding---this is no worse than previous solutions if $ρ= O(n/\log n)$ and better if $ρ= o(n/\log n)$. Our index $L$ can be queried in $O(\log ρ)$ time. While $|L|= O(\min(n, ρ^{2}))$ in the worst case, preliminary investigations have indicated that $|L|$ may often be close to $ρ$. Furthermore, the algorithm for constructing the index is conceptually simple and easy to implement. In an attempt to shed light on the structure and size of our index, we characterize it in terms of the prefix normal forms of $s$ introduced in [Fici and Lipták, DLT 2011].
Information-Theoretically Secure Three-Party Computation with One Corrupted Party
Venue: arXiv cs.CR 2013
Year: 2013

The problem in which one of three pairwise interacting parties is required to securely compute a function of the inputs held by the other two, when one party may arbitrarily deviate from the computation protocol (active behavioral model), is studied. An information-theoretic characterization of unconditionally secure computation protocols under the active behavioral model is provided. A protocol for Hamming distance computation is provided and shown to be unconditionally secure under both active and passive behavioral models using the information-theoretic characterization. The difference between the notions of security under the active and passive behavioral models is illustrated through the BGW protocol for computing quadratic and Hamming distances; this protocol is secure under the passive model, but is shown to be not secure under the active model.
EVM and Achievable Data Rate Analysis of Clipped OFDM Signals in Visible Light Communication
Venue: arXiv cs.IT 2013
Year: 2013

Orthogonal frequency division multiplexing (OFDM) has been considered for visible light communication (VLC) thanks to its ability to boost data rates as well as its robustness against frequency-selective fading channels. A major disadvantage of OFDM is the large dynamic range of its time-domain waveforms, making OFDM vulnerable to nonlinearity of light emitting diodes (LEDs). DC biased optical OFDM (DCO-OFDM) and asymmetrically clipped optical OFDM (ACO-OFDM) are two popular OFDM techniques developed for the VLC. In this paper, we will analyze the performance of the DCO-OFDM and ACO-OFDM signals in terms of error vector magnitude (EVM), signal-to-distortion ratio (SDR), and achievable data rates under both average optical power and dynamic optical power constraints. EVM is a commonly used metric to characterize distortions. We will describe an approach to numerically calculate the EVM for DCO-OFDM and ACO-OFDM. We will derive the optimum biasing ratio in the sense of minimizing EVM for DCO-OFDM. Additionally, we will formulate the EVM minimization problem as a convex linear optimization problem and obtain an EVM lower bound against which to compare the DCO-OFDM and ACO-OFDM techniques. We will prove that the ACO-OFDM can achieve the lower bound. Average optical power and dynamic optical power are two main constraints in VLC. We will derive the achievable data rates under these two constraints for both additive white Gaussian noise (AWGN) channel and frequency-selective channel. We will compare the performance of DCO-OFDM and ACO-OFDM under different power constraint scenarios.
Prediction of Emerging Technologies Based on Analysis of the U.S. Patent Citation Network
Venue: arXiv cs.SI 2013
Year: 2013

The network of patents connected by citations is an evolving graph, which provides a representation of the innovation process. A patent citing another implies that the cited patent reflects a piece of previously existing knowledge that the citing patent builds upon. A methodology presented here (i) identifies actual clusters of patents: i.e. technological branches, and (ii) gives predictions about the temporal changes of the structure of the clusters. A predictor, called the {citation vector}, is defined for characterizing technological development to show how a patent cited by other patents belongs to various industrial fields. The clustering technique adopted is able to detect the new emerging recombinations, and predicts emerging new technology clusters. The predictive ability of our new method is illustrated on the example of USPTO subcategory 11, Agriculture, Food, Textiles. A cluster of patents is determined based on citation data up to 1991, which shows significant overlap of the class 442 formed at the beginning of 1997. These new tools of predictive analytics could support policy decision making processes in science and technology, and help formulate recommendations for action.
Evaluating Overlapping Communities with the Conductance of their Boundary Nodes
Venue: arXiv cs.SI 2013
Year: 2013

Usually the boundary of a community in a network is drawn between nodes and thus crosses its outgoing links. If we construct overlapping communities by applying the link-clustering approach nodes and links interchange their roles. Therefore, boundaries must drawn through the nodes shared by two or more communities. For the purpose of community evaluation we define a conductance of boundary nodes of overlapping communities analogously to the graph conductance of boundary-crossing links used to partition a graph into disjoint communities. We show that conductance of boundary nodes (or normalised node cut) can be deduced from ordinary graph conductance of disjoint clusters in the network's weighted line graph introduced by Evans and Lambiotte (2009) to get overlapping communities of nodes in the original network. We test whether our definition can be used to construct meaningful overlapping communities with a local greedy algorithm of link clustering. In this note we present encouraging results we obtained for Zachary's karate-club network.
On the Confidentiality of Information Dispersal Algorithms and Their Erasure Codes
Venue: arXiv cs.IT 2013
Year: 2013

\emph{Information Dispersal Algorithms (IDAs)} have been widely applied to reliable and secure storage and transmission of data files in distributed systems. An IDA is a method that encodes a file $F$ of size $L=|F|$ into $n$ unrecognizable pieces $F_1$, $F_2$, ..., $F_n$, each of size $L/m$ ($m<n$), so that the original file $F$ can be reconstructed from any $m$ pieces. The core of an IDA is the adopted non-systematic $m$-of-$n$ erasure code. This paper makes a systematic study on the \emph{confidentiality} of an IDA and its connection with the adopted erasure code. Two levels of confidentiality are defined: \emph{weak confidentiality} (in the case where some parts of the original file $F$ can be reconstructed explicitly from fewer than $m$ pieces) and \emph{strong confidentiality} (in the case where nothing of the original file $F$ can be reconstructed explicitly from fewer than $m$ pieces). For an IDA that adopts an arbitrary non-systematic erasure code, its confidentiality may fall into weak confidentiality. To achieve strong confidentiality, this paper explores a sufficient and feasible condition on the adopted erasure code. Then, this paper shows that Rabin's IDA has strong confidentiality. At the same time, this paper presents an effective way to construct an IDA with strong confidentiality from an arbitrary $m$-of-$(m+n)$ erasure code. Then, as an example, this paper constructs an IDA with strong confidentiality from a Reed-Solomon code, the computation complexity of which is comparable to or sometimes even lower than that of Rabin's IDA.
Cell Oscillation Resolution in Mobility Profile Building
Venue: arXiv cs.NI 2013
Year: 2013

This paper has been withdrawn by the authors. Mobility profile building became extensively examined area in Location based services (LBS) through extraction of significant locations. Mobility traces are recorded under three reference positioning systems that are Satellite based i.e. GPS, Network based i.e. GSM and Local positioning i.e. WLAN, RFID, IrDA. Satellite based and local positioning due to of high power consumption, additional resource installation, low accuracy and space limitation are less encouraging. So network based positioning i.e. GSM is only viable solution for mobility tracing through Cell global identity (CGI). CGI presents the Cell-ids to extract the significant locations from mobility history. However CGI faces cell oscillation problem, where user is assigned multiple Cell-Ids even at a stationary state for load balancing and GSM cells overlapping. In this paper we proposed two semi-supervised methodology for cell oscillation resolution i.e. semantic tagging and overlapped area clustering, the proposed methodologies are equally useful for the identification of significant places too.
An Information-Theoretic Perspective of the Poisson Approximation via the Chen-Stein Method
Venue: arXiv cs.IT 2013
Year: 2013

The first part of this work considers the entropy of the sum of (possibly dependent and non-identically distributed) Bernoulli random variables. Upper bounds on the error that follows from an approximation of this entropy by the entropy of a Poisson random variable with the same mean are derived via the Chen-Stein method. The second part of this work derives new lower bounds on the total variation (TV) distance and relative entropy between the distribution of the sum of independent Bernoulli random variables and the Poisson distribution. The starting point of the derivation of the new bounds in the second part of this work is an introduction of a new lower bound on the total variation distance, whose derivation generalizes and refines the analysis by Barbour and Hall (1984), based on the Chen-Stein method for the Poisson approximation. A new lower bound on the relative entropy between these two distributions is introduced, and this lower bound is compared to a previously reported upper bound on the relative entropy by Kontoyiannis et al. (2005). The derivation of the new lower bound on the relative entropy follows from the new lower bound on the total variation distance, combined with a distribution-dependent refinement of Pinsker's inequality by Ordentlich and Weinberger (2005). Upper and lower bounds on the Bhattacharyya parameter, Chernoff information and Hellinger distance between the distribution of the sum of independent Bernoulli random variables and the Poisson distribution with the same mean are derived as well via some relations between these quantities with the total variation distance and the relative entropy. The analysis in this work combines elements of information theory with the Chen-Stein method for the Poisson approximation. The resulting bounds are easy to compute, and their applicability is exemplified.
Optimal Dynamic Sequence Representations
Venue: arXiv cs.DS 2013
Year: 2013

We describe a data structure that supports access, rank and select queries, as well as symbol insertions and deletions, on a string $S[1,n]$ over alphabet $[1..σ]$ in time $O(\lg n/\lg\lg n)$, which is optimal even on binary sequences and in the amortized sense. Our time is worst-case for the queries and amortized for the updates. This complexity is better than the best previous ones by a $Θ(1+\lgσ/\lg\lg n)$ factor. We also design a variant where times are worst-case, yet rank and updates take $O(\lg n)$ time. Our structure uses $nH_0(S)+o(n\lgσ) + O(σ\lg n)$ bits, where $H_0(S)$ is the zero-order entropy of $S$. Finally, we pursue various extensions and applications of the result.