OpenRaiser/Intern-Atlas huggingface dataset:
TrueTop: A Sybil-Resilient System for User Influence Measurement on Twitter
Venue: arXiv cs.SI 2015
Year: 2015

Influential users have great potential for accelerating information dissemination and acquisition on Twitter. How to measure the influence of Twitter users has attracted significant academic and industrial attention. Existing influential measurement techniques, however, are vulnerable to sybil users that are thriving on Twitter. Although sybil defenses for online social networks have been extensively investigated, they commonly assume unique mappings from human-established trust relationships to online social associations and thus do not apply to Twitter where users can freely follow each other. This paper presents TrueTop, the first sybil-resilient system to measure the influence of Twitter users. TrueTop is firmly rooted in two observations from real Twitter datasets. First, although non-sybil users may incautiously follow strangers, they tend to be more careful and selective in retweeting, replying to, and mentioning other Twitter users. Second, influential users usually get much more retweets, replies, and mentions than non-influential users. Detailed theoretical studies and synthetic simulations show that TrueTop can generate very accurate influence measurement results and also have strong resilience to sybil attacks.
Sampling of graph signals with successive local aggregations
Venue: arXiv cs.SI 2015
Year: 2015

A new scheme to sample signals defined in the nodes of a graph is proposed. The underlying assumption is that such signals admit a sparse representation in a frequency domain related to the structure of the graph, which is captured by the so-called graph-shift operator. Most of the works that have looked at this problem have focused on using the value of the signal observed at a subset of nodes to recover the signal in the entire graph. Differently, the sampling scheme proposed here uses as input observations taken at a single node. The observations correspond to sequential applications of the graph-shift operator, which are linear combinations of the information gathered by the neighbors of the node. When the graph corresponds to a directed cycle (which is the support of time-varying signals), our method is equivalent to the classical sampling in the time domain. When the graph is more general, we show that the Vandermonde structure of the sampling matrix, which is critical to guarantee recovery when sampling time-varying signals, is preserved. Sampling and interpolation are analyzed first in the absence of noise and then noise is considered. We then study the recovery of the sampled signal when the specific set of frequencies that is active is not known. Moreover, we present a more general sampling scheme, under which, either our aggregation approach or the alternative approach of sampling a graph signal by observing the value of the signal at a subset of nodes can be both viewed as particular cases. The last part of the paper presents numerical experiments that illustrate the results developed through both synthetic graph signals and a real-world graph of the economy of the United States.
Enhancing the scalability and load balancing of the parallel selected inversion algorithm via tree-based asynchronous communication
Venue: arXiv cs.DC 2015
Year: 2015

We develop a method for improving the parallel scalability of the recently developed parallel selected inversion algorithm [Jacquelin, Lin and Yang 2014], named PSelInv, on massively parallel distributed memory machines. In the PSelInv method, we compute selected elements of the inverse of a sparse matrix A that can be decomposed as A = LU, where L is lower triangular and U is upper triangular. Updating these selected elements of A-1 requires restricted collective communications among a subset of processors within each column or row communication group created by a block cyclic distribution of L and U. We describe how this type of restricted collective communication can be implemented by using asynchronous point-to-point MPI communication functions combined with a binary tree based data propagation scheme. Because multiple restricted collective communications may take place at the same time in the parallel selected inversion algorithm, we need to use a heuristic to prevent processors participating in multiple collective communications from receiving too many messages. This heuristic allows us to reduce communication load imbalance and improve the overall scalability of the selected inversion algorithm. For instance, when 6,400 processors are used, we observe over 5x speedup for test matrices. It also mitigates the performance variability introduced by an inhomogeneous network topology.
Understanding the Fisher Vector: a multimodal part model
Venue: arXiv cs.CV 2015
Year: 2015

Fisher Vectors and related orderless visual statistics have demonstrated excellent performance in object detection, sometimes superior to established approaches such as the Deformable Part Models. However, it remains unclear how these models can capture complex appearance variations using visual codebooks of limited sizes and coarse geometric information. In this work, we propose to interpret Fisher-Vector-based object detectors as part-based models. Through the use of several visualizations and experiments, we show that this is a useful insight to explain the good performance of the model. Furthermore, we reveal for the first time several interesting properties of the FV, including its ability to work well using only a small subset of input patches and visual words. Finally, we discuss the relation of the FV and DPM detectors, pointing out differences and commonalities between them.
Generalized Interlinked Cycle Cover for Index Coding
Venue: arXiv cs.IT 2015
Year: 2015

A source coding problem over a noiseless broadcast channel where the source is pre-informed about the contents of the cache of all receivers, is an index coding problem. Furthermore, if each message is requested by one receiver, then we call this an index coding problem with a unicast message setting. This problem can be represented by a directed graph. In this paper, we first define a structure (we call generalized interlinked cycles (GIC)) in directed graphs. A GIC consists of cycles which are interlinked in some manner (i.e., not disjoint), and it turns out that the GIC is a generalization of cliques and cycles. We then propose a simple scalar linear encoding scheme with linear time encoding complexity. This scheme exploits GICs in the digraph. We prove that our scheme is optimal for a class of digraphs with message packets of any length. Moreover, we show that our scheme can outperform existing techniques, e.g., partial clique cover, local chromatic number, composite-coding, and interlinked cycle cover.
Communication with Contextual Uncertainty
Venue: arXiv cs.CC 2015
Year: 2015

We introduce a simple model illustrating the role of context in communication and the challenge posed by uncertainty of knowledge of context. We consider a variant of distributional communication complexity where Alice gets some information $x$ and Bob gets $y$, where $(x,y)$ is drawn from a known distribution, and Bob wishes to compute some function $g(x,y)$ (with high probability over $(x,y)$). In our variant, Alice does not know $g$, but only knows some function $f$ which is an approximation of $g$. Thus, the function being computed forms the context for the communication, and knowing it imperfectly models (mild) uncertainty in this context. A naive solution would be for Alice and Bob to first agree on some common function $h$ that is close to both $f$ and $g$ and then use a protocol for $h$ to compute $h(x,y)$. We show that any such agreement leads to a large overhead in communication ruling out such a universal solution. In contrast, we show that if $g$ has a one-way communication protocol with complexity $k$ in the standard setting, then it has a communication protocol with complexity $O(k \cdot (1+I))$ in the uncertain setting, where $I$ denotes the mutual information between $x$ and $y$. In the particular case where the input distribution is a product distribution, the protocol in the uncertain setting only incurs a constant factor blow-up in communication and error. Furthermore, we show that the dependence on the mutual information $I$ is required. Namely, we construct a class of functions along with a non-product distribution over $(x,y)$ for which the communication complexity is a single bit in the standard setting but at least $Ω(\sqrt{n})$ bits in the uncertain setting.
Learning discriminative trajectorylet detector sets for accurate skeleton-based action recognition
Venue: arXiv cs.CV 2015
Year: 2015

The introduction of low-cost RGB-D sensors has promoted the research in skeleton-based human action recognition. Devising a representation suitable for characterising actions on the basis of noisy skeleton sequences remains a challenge, however. We here provide two insights into this challenge. First, we show that the discriminative information of a skeleton sequence usually resides in a short temporal interval and we propose a simple-but-effective local descriptor called trajectorylet to capture the static and kinematic information within this interval. Second, we further propose to encode each trajectorylet with a discriminative trajectorylet detector set which is selected from a large number of candidate detectors trained through exemplar-SVMs. The action-level representation is obtained by pooling trajectorylet encodings. Evaluating on standard datasets acquired from the Kinect sensor, it is demonstrated that our method obtains superior results over existing approaches under various experimental setups.
Connecting Multiple-unicast and Network Error Correction: Reduction and Unachievability
Venue: arXiv cs.IT 2015
Year: 2015

We show that solving a multiple-unicast network coding problem can be reduced to solving a single-unicast network error correction problem, where an adversary may jam at most a single edge in the network. Specifically, we present an efficient reduction that maps a multiple-unicast network coding instance to a network error correction instance while preserving feasibility. The reduction holds for both the zero probability of error model and the vanishing probability of error model. Previous reductions are restricted to the zero-error case. As an application of the reduction, we present a constructive example showing that the single-unicast network error correction capacity may not be achievable, a result of separate interest.
On the Symmetry of Polar Codes for Symmetric Binary-Input Discrete Memoryless Channels
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we study the symmetry of polar codes on symmetric binary-input discrete memoryless channels (B-DMC). The symmetry property of polar codes is originally pointed out in Arikan's work for general B-DMC channels. With the symmetry, the output vector $y_1^N$ ($N$ be the block length) can be divided into equivalence classes in terms of their transition probabilities. In this paper, we present a new frame of analysis on the symmetry of polar codes for B-DMC channels. Theorems are provided to characterize the symmetries among the received vectors.
Impact assessment for vulnerabilities in open-source software libraries
Venue: arXiv cs.CR 2015
Year: 2015

Software applications integrate more and more open-source software (OSS) to benefit from code reuse. As a drawback, each vulnerability discovered in bundled OSS potentially affects the application. Upon the disclosure of every new vulnerability, the application vendor has to decide whether it is exploitable in his particular usage context, hence, whether users require an urgent application patch containing a non-vulnerable version of the OSS. Current decision making is mostly based on high-level vulnerability descriptions and expert knowledge, thus, effort intense and error prone. This paper proposes a pragmatic approach to facilitate the impact assessment, describes a proof-of-concept for Java, and examines one example vulnerability as case study. The approach is independent from specific kinds of vulnerabilities or programming languages and can deliver immediate results.
Automatic Repair of Infinite Loops
Venue: arXiv cs.SE 2015
Year: 2015

Research on automatic software repair is concerned with the development of systems that automatically detect and repair bugs. One well-known class of bugs is the infinite loop. Every computer programmer or user has, at least once, experienced this type of bug. We state the problem of repairing infinite loops in the context of test-suite based software repair: given a test suite with at least one failing test, generate a patch that makes all test cases pass. Consequently, repairing infinites loop means having at least one test case that hangs by triggering the infinite loop. Our system to automatically repair infinite loops is called $Infinitel$. We develop a technique to manipulate loops so that one can dynamically analyze the number of iterations of loops; decide to interrupt the loop execution; and dynamically examine the state of the loop on a per-iteration basis. Then, in order to synthesize a new loop condition, we encode this set of program states as a code synthesis problem using a technique based on Satisfiability Modulo Theory (SMT). We evaluate our technique on seven seeded-bugs and on seven real-bugs. $Infinitel$ is able to repair all of them, within seconds up to one hour on a standard laptop configuration.
New Bounds for Permutation Codes in Ulam Metric
Venue: arXiv cs.IT 2015
Year: 2015

New bounds on the cardinality of permutation codes equipped with the Ulam distance are presented. First, an integer-programming upper bound is derived, which improves on the Singleton-type upper bound in the literature for some lengths. Second, several probabilistic lower bounds are developed, which improve on the known lower bounds for large minimum distances. The results of a computer search for permutation codes are also presented.
Application of Enhanced-2D-CWT in Topographic Images for Mapping Landslide Risk Areas
Venue: arXiv cs.CV 2015
Year: 2015

There has been lately a number of catastrophic events of landslides and mudslides in the mountainous region of Rio de Janeiro, Brazil. Those were caused by intense rain in localities where there was unplanned occupation of slopes of hills and mountains. Thus, it became imperative creating an inventory of landslide risk areas in densely populated cities. This work presents a way of demarcating risk areas by using the bidimensional Continuous Wavelet Transform (2D-CWT) applied to high resolution topographic images of the mountainous region of Rio de Janeiro.
A Simple and General Problem and its Optimal Randomized Online Algorithm Design with Competitive Analysis
Venue: arXiv cs.OH 2015
Year: 2015

The online algorithm design was proposed to handle the caching problem when the future information is unknown. And currently, it draws more and more attentions from the researchers from the areas of microgrid, where the production of renewables are unpredictable. In this note, we present a framework of randomized online algorithm design for the \textit{simple and tractable} problem. This framework hopes to provide a tractable design to design a randomized online algorithm, which can be proved to achieve the best competitive ratio by \textit{Yao's Principle}.
Automatic Face Recognition from Video
Venue: arXiv cs.CV 2015
Year: 2015

The objective of this work is to automatically recognize faces from video sequences in a realistic, unconstrained setup in which illumination conditions are extreme and greatly changing, viewpoint and user motion pattern have a wide variability, and video input is of low quality. At the centre of focus are face appearance manifolds: this thesis presents a significant advance of their understanding and application in the sphere of face recognition. The two main contributions are the Generic Shape-Illumination Manifold recognition algorithm and the Anisotropic Manifold Space clustering. The Generic Shape-Illumination Manifold is evaluated on a large data corpus acquired in real-world conditions and its performance is shown to greatly exceed that of state-of-the-art methods in the literature and the best performing commercial software. Empirical evaluation of the Anisotropic Manifold Space clustering on a popular situation comedy is also described with excellent preliminary results.
A Novel Variable Step Size NLMS Algorithm Based on the Power Estimate of the System Noise
Venue: arXiv cs.SY 2015
Year: 2015

To overcome the tradeoff of the conventional normalized least mean square (NLMS) algorithm between fast convergence rate and low steady-state misalignment, this paper proposes a variable step size (VSS) NLMS algorithm by devising a new strategy to update the step size. In this strategy, the input signal power and the cross-correlation between the input signal and the error signal are used to estimate the true tracking error power, reducing the effect of the system noise on the algorithm performance. Moreover, the steady-state performances of the algorithm are provided for Gaussian white input signal and are verified by simulations. Finally, simulation results in the context of the system identification and acoustic echo cancellation (AEC) have demonstrated that the proposed algorithm has lower steady-state misalignment than other VSS algorithms.
Key-Pose Prediction in Cyclic Human Motion
Venue: arXiv cs.CV 2015
Year: 2015

In this paper we study the problem of estimating innercyclic time intervals within repetitive motion sequences of top-class swimmers in a swimming channel. Interval limits are given by temporal occurrences of key-poses, i.e. distinctive postures of the body. A key-pose is defined by means of only one or two specific features of the complete posture. It is often difficult to detect such subtle features directly. We therefore propose the following method: Given that we observe the swimmer from the side, we build a pictorial structure of poselets to robustly identify random support poses within the regular motion of a swimmer. We formulate a maximum likelihood model which predicts a key-pose given the occurrences of multiple support poses within one stroke. The maximum likelihood can be extended with prior knowledge about the temporal location of a key-pose in order to improve the prediction recall. We experimentally show that our models reliably and robustly detect key-poses with a high precision and that their performance can be improved by extending the framework with additional camera views.
Visual analytics in FCA-based clustering
Venue: arXiv cs.IR 2015
Year: 2015

Visual analytics is a subdomain of data analysis which combines both human and machine analytical abilities and is applied mostly in decision-making and data mining tasks. Triclustering, based on Formal Concept Analysis (FCA), was developed to detect groups of objects with similar properties under similar conditions. It is used in Social Network Analysis (SNA) and is a basis for certain types of recommender systems. The problem of triclustering algorithms is that they do not always produce meaningful clusters. This article describes a specific triclustering algorithm and a prototype of a visual analytics platform for working with obtained clusters. This tool is designed as a testing frameworkis and is intended to help an analyst to grasp the results of triclustering and recommender algorithms, and to make decisions on meaningfulness of certain triclusters and recommendations.
The New South Wales iVote System: Security Failures and Verification Flaws in a Live Online Election
Venue: arXiv cs.CR 2015
Year: 2015

In the world's largest-ever deployment of online voting, the iVote Internet voting system was trusted for the return of 280,000 ballots in the 2015 state election in New South Wales, Australia. During the election, we performed an independent security analysis of parts of the live iVote system and uncovered severe vulnerabilities that could be leveraged to manipulate votes, violate ballot privacy, and subvert the verification mechanism. These vulnerabilities do not seem to have been detected by the election authorities before we disclosed them, despite a pre-election security review and despite the system having run in a live state election for five days. One vulnerability, the result of including analytics software from an insecure external server, exposed some votes to complete compromise of privacy and integrity. At least one parliamentary seat was decided by a margin much smaller than the number of votes taken while the system was vulnerable. We also found protocol flaws, including vote verification that was itself susceptible to manipulation. This incident underscores the difficulty of conducting secure elections online and carries lessons for voters, election officials, and the e-voting research community.
Rounding Methods for Neural Networks with Low Resolution Synaptic Weights
Venue: arXiv cs.NE 2015
Year: 2015

Neural network algorithms simulated on standard computing platforms typically make use of high resolution weights, with floating-point notation. However, for dedicated hardware implementations of such algorithms, fixed-point synaptic weights with low resolution are preferable. The basic approach of reducing the resolution of the weights in these algorithms by standard rounding methods incurs drastic losses in performance. To reduce the resolution further, in the extreme case even to binary weights, more advanced techniques are necessary. To this end, we propose two methods for mapping neural network algorithms with high resolution weights to corresponding algorithms that work with low resolution weights and demonstrate that their performance is substantially better than standard rounding. We further use these methods to investigate the performance of three common neural network algorithms under fixed memory size of the weight matrix with different weight resolutions. We show that dedicated hardware systems, whose technology dictates very low weight resolutions (be they electronic or biological) could in principle implement the algorithms we study.
A Packing Lemma for Polar Codes
Venue: arXiv cs.IT 2015
Year: 2015

A packing lemma is proved using a setting where the channel is a binary-input discrete memoryless channel $(\mathcal{X},w(y|x),\mathcal{Y})$, the code is selected at random subject to parity-check constraints, and the decoder is a joint typicality decoder. The ensemble is characterized by (i) a pair of fixed parameters $(H,q)$ where $H$ is a parity-check matrix and $q$ is a channel input distribution and (ii) a random parameter $S$ representing the desired parity values. For a code of length $n$, the constraint is sampled from $p_S(s) = \sum_{x^n\in {\mathcal{X}}^n} ϕ(s,x^n)q^n(x^n)$ where $ϕ(s,x^n)$ is the indicator function of event $\{s = x^n H^T\}$ and $q^n(x^n) = \prod_{i=1}^nq(x_i)$. Given $S=s$, the codewords are chosen conditionally independently from $p_{X^n|S}(x^n|s) \propto ϕ(s,x^n) q^n(x^n)$. It is shown that the probability of error for this ensemble decreases exponentially in $n$ provided the rate $R$ is kept bounded away from $I(X;Y)-\frac{1}{n}I(S;Y^n)$ with $(X,Y)\sim q(x)w(y|x)$ and $(S,Y^n)\sim p_S(s)\sum_{x^n} p_{X^n|S}(x^n|s) \prod_{i=1}^{n} w(y_i|x_i)$. In the special case where $H$ is the parity-check matrix of a standard polar code, it is shown that the rate penalty $\frac{1}{n}I(S;Y^n)$ vanishes as $n$ increases. The paper also discusses the relation between ordinary polar codes and random codes based on polar parity-check matrices.