OpenRaiser/Intern-Atlas huggingface dataset:
A Polynomial Time Algorithm for Deciding Branching Bisimilarity on Totally Normed BPA
Venue: arXiv cs.LO 2014
Year: 2014

Strong bisimilarity on normed BPA is polynomial-time decidable, while weak bisimilarity on totally normed BPA is NP-hard. It is natural to ask where the computational complexity of branching bisimilarity on totally normed BPA lies. This paper confirms that this problem is polynomial-time decidable. To our knowledge, in the presence of silent transitions, this is the first bisimilarity checking algorithm on infinite state systems which runs in polynomial time. This result spots an instance in which branching bisimilarity and weak bisimilarity are both decidable but lie in different complexity classes (unless NP=P), which is not known before. The algorithm takes the partition refinement approach and the final implementation can be thought of as a generalization of the previous algorithm of Czerwiński and Lasota. However, unexpectedly, the correctness of the algorithm cannot be directly generalized from previous works, and the correctness proof turns out to be subtle. The proof depends on the existence of a carefully defined refinement operation fitted for our algorithm and the proposal of elaborately developed techniques, which are quite different from previous works.
Revisiting Kernelized Locality-Sensitive Hashing for Improved Large-Scale Image Retrieval
Venue: arXiv cs.CV 2014
Year: 2014

We present a simple but powerful reinterpretation of kernelized locality-sensitive hashing (KLSH), a general and popular method developed in the vision community for performing approximate nearest-neighbor searches in an arbitrary reproducing kernel Hilbert space (RKHS). Our new perspective is based on viewing the steps of the KLSH algorithm in an appropriately projected space, and has several key theoretical and practical benefits. First, it eliminates the problematic conceptual difficulties that are present in the existing motivation of KLSH. Second, it yields the first formal retrieval performance bounds for KLSH. Third, our analysis reveals two techniques for boosting the empirical performance of KLSH. We evaluate these extensions on several large-scale benchmark image retrieval data sets, and show that our analysis leads to improved recall performance of at least 12%, and sometimes much higher, over the standard KLSH method.
Social Behavior in Bacterial Nanonetworks: Challenges and Opportunities
Venue: arXiv cs.ET 2014
Year: 2014

Molecular communication promises to enable communication between nanomachines with a view to increasing their functionalities and open up new possible applications. Due to some of the biological properties, bacteria have been proposed as a possible information carrier for molecular communication, and the corresponding communication networks are known as \textit{bacterial nanonetworks}. The biological properties include the ability for bacteria to mobilize between locations and carry the information encoded in Deoxyribonucleic Acid (DNA) molecules. However, similar to most organisms, bacteria have complex social properties that govern their colony. These social characteristics enable the bacteria to evolve through various fluctuating environmental conditions by utilizing cooperative and non-cooperative behaviors. This article provides an overview of the different types of cooperative and non-cooperative social behavior of bacteria. The challenges (due to non-cooperation) and the opportunities (due to cooperation) these behaviors can bring to the reliability of communication in bacterial nanonetworks are also discussed. Finally, simulation results on the impact of bacterial cooperative social behavior on the end-to-end reliability of a single-link bacterial nanonetwork are presented. The article concludes with highlighting the potential future research opportunities in this emerging field.
Efficient and Accurate Approximations of Nonlinear Convolutional Networks
Venue: arXiv cs.CV 2014
Year: 2014

This paper aims to accelerate the test-time computation of deep convolutional neural networks (CNNs). Unlike existing methods that are designed for approximating linear filters or linear responses, our method takes the nonlinear units into account. We minimize the reconstruction error of the nonlinear responses, subject to a low-rank constraint which helps to reduce the complexity of filters. We develop an effective solution to this constrained nonlinear optimization problem. An algorithm is also presented for reducing the accumulated error when multiple layers are approximated. A whole-model speedup ratio of 4x is demonstrated on a large network trained for ImageNet, while the top-5 error rate is only increased by 0.9%. Our accelerated model has a comparably fast speed as the "AlexNet", but is 4.7% more accurate.
Ten Years of Pedestrian Detection, What Have We Learned?
Venue: arXiv cs.CV 2014
Year: 2014

Paper-by-paper results make it easy to miss the forest for the trees.We analyse the remarkable progress of the last decade by discussing the main ideas explored in the 40+ detectors currently present in the Caltech pedestrian detection benchmark. We observe that there exist three families of approaches, all currently reaching similar detection quality. Based on our analysis, we study the complementarity of the most promising ideas by combining multiple published strategies. This new decision forest detector achieves the current best known performance on the challenging Caltech-USA dataset.
PDD Crawler: A focused web crawler using link and content analysis for relevance prediction
Venue: arXiv cs.IR 2014
Year: 2014

Majority of the computer or mobile phone enthusiasts make use of the web for searching activity. Web search engines are used for the searching; The results that the search engines get are provided to it by a software module known as the Web Crawler. The size of this web is increasing round-the-clock. The principal problem is to search this huge database for specific information. To state whether a web page is relevant to a search topic is a dilemma. This paper proposes a crawler called as PDD crawler which will follow both a link based as well as a content based approach. This crawler follows a completely new crawling strategy to compute the relevance of the page. It analyses the content of the page based on the information contained in various tags within the HTML source code and then computes the total weight of the page. The page with the highest weight, thus has the maximum content and highest relevance.
Design of Spatially Coupled LDPC Codes over GF(q) for Windowed Decoding
Venue: arXiv cs.IT 2014
Year: 2014

In this paper we consider the generalization of binary spatially coupled low-density parity-check (SC-LDPC) codes to finite fields GF$(q)$, $q\geq 2$, and develop design rules for $q$-ary SC-LDPC code ensembles based on their iterative belief propagation (BP) decoding thresholds, with particular emphasis on low-latency windowed decoding (WD). We consider transmission over both the binary erasure channel (BEC) and the binary-input additive white Gaussian noise channel (BIAWGNC) and present results for a variety of $(J,K)$-regular SC-LDPC code ensembles constructed over GF$(q)$ using protographs. Thresholds are calculated using protograph versions of $q$-ary density evolution (for the BEC) and $q$-ary extrinsic information transfer analysis (for the BIAWGNC). We show that WD of $q$-ary SC-LDPC codes provides significant threshold gains compared to corresponding (uncoupled) $q$-ary LDPC block code (LDPC-BC) ensembles when the window size $W$ is large enough and that these gains increase as the finite field size $q=2^m$ increases. Moreover, we demonstrate that the new design rules provide WD thresholds that are close to capacity, even when both $m$ and $W$ are relatively small (thereby reducing decoding complexity and latency). The analysis further shows that, compared to standard flooding-schedule decoding, WD of $q$-ary SC-LDPC code ensembles results in significant reductions in both decoding complexity and decoding latency, and that these reductions increase as $m$ increases. For applications with a near-threshold performance requirement and a constraint on decoding latency, we show that using $q$-ary SC-LDPC code ensembles, with moderate $q>2$, instead of their binary counterparts results in reduced decoding complexity.
FGPGA: An Efficient Genetic Approach for Producing Feasible Graph Partitions
Venue: arXiv cs.NE 2014
Year: 2014

Graph partitioning, a well studied problem of parallel computing has many applications in diversified fields such as distributed computing, social network analysis, data mining and many other domains. In this paper, we introduce FGPGA, an efficient genetic approach for producing feasible graph partitions. Our method takes into account the heterogeneity and capacity constraints of the partitions to ensure balanced partitioning. Such approach has various applications in mobile cloud computing that include feasible deployment of software applications on the more resourceful infrastructure in the cloud instead of mobile hand set. Our proposed approach is light weight and hence suitable for use in cloud architecture. We ensure feasibility of the partitions generated by not allowing over-sized partitions to be generated during the initialization and search. Our proposed method tested on standard benchmark datasets significantly outperforms the state-of-the-art methods in terms of quality of partitions and feasibility of the solutions.
Stochastic HYPE: Flow-based modelling of stochastic hybrid systems
Venue: arXiv cs.SY 2014
Year: 2014

Stochastic HYPE is a novel process algebra that models stochastic, instantaneous and continuous behaviour. It develops the flow-based approach of the hybrid process algebra HYPE by replacing non-urgent events with events with exponentially-distributed durations and also introduces random resets. The random resets allow for general stochasticity, and in particular allow for the use of event durations drawn from distributions other than the exponential distribution. To account for stochasticity, the semantics of stochastic HYPE target piecewise deterministic Markov processes (PDMPs), via intermediate transition-driven stochastic hybrid automata (TDSHA) in contrast to the hybrid automata used as semantic target for HYPE. Stochastic HYPE models have a specific structure where the controller of a system is separate from the continuous aspect of this system providing separation of concerns and supporting reasoning. A novel equivalence is defined which captures when two models have the same stochastic behaviour (as in stochastic bisimulation), instantaneous behaviour (as in classical bisimulation) and continuous behaviour. These techniques are illustrated via an assembly line example.
Sunflowers and Testing Triangle-Freeness of Functions
Venue: arXiv cs.DS 2014
Year: 2014

A function $f: \mathbb{F}_2^n \rightarrow \{0,1\}$ is triangle-free if there are no $x_1,x_2,x_3 \in \mathbb{F}_2^n$ satisfying $x_1+x_2+x_3=0$ and $f(x_1)=f(x_2)=f(x_3)=1$. In testing triangle-freeness, the goal is to distinguish with high probability triangle-free functions from those that are $\varepsilon$-far from being triangle-free. It was shown by Green that the query complexity of the canonical tester for the problem is upper bounded by a function that depends only on $\varepsilon$ (GAFA, 2005), however the best known upper bound is a tower type function of $1/\varepsilon$. The best known lower bound on the query complexity of the canonical tester is $1/\varepsilon^{13.239}$ (Fu and Kleinberg, RANDOM, 2014). In this work we introduce a new approach to proving lower bounds on the query complexity of triangle-freeness. We relate the problem to combinatorial questions on collections of vectors in $\mathbb{Z}_D^n$ and to sunflower conjectures studied by Alon, Shpilka, and Umans (Comput. Complex., 2013). The relations yield that a refutation of the Weak Sunflower Conjecture over $\mathbb{Z}_4$ implies a super-polynomial lower bound on the query complexity of the canonical tester for triangle-freeness. Our results are extended to testing $k$-cycle-freeness of functions with domain $\mathbb{F}_p^n$ for every $k \geq 3$ and a prime $p$. In addition, we generalize the lower bound of Fu and Kleinberg to $k$-cycle-freeness for $k \geq 4$ by generalizing the construction of uniquely solvable puzzles due to Coppersmith and Winograd (J. Symbolic Comput., 1990).
Security Analysis of the Unrestricted Identity-Based Aggregate Signature Scheme
Venue: arXiv cs.CR 2014
Year: 2014

Aggregate signatures allow anyone to combine different signatures signed by different signers on different messages into a single short signature. An ideal aggregate signature scheme is an identity-based aggregate signature (IBAS) scheme that supports full aggregation since it can reduce the total transmitted data by using an identity string as a public key and anyone can freely aggregate different signatures. Constructing a secure IBAS scheme that supports full aggregation in bilinear maps is an important open problem. Recently, Yuan {\it et al.} proposed an IBAS scheme with full aggregation in bilinear maps and claimed its security in the random oracle model under the computational Diffie-Hellman assumption. In this paper, we show that there exists an efficient forgery attacker on their IBAS scheme and their security proof has a serious flaw.
Which Are You In A Photo?
Venue: arXiv cs.SD 2014
Year: 2014

Automatic image tagging has been a long standing problem, it mainly relies on image recognition techniques of which the accuracy is still not satisfying. This paper attempts to explore out-of-band sensing base on the mobile phone to sense the people in a picture while the picture is being taken and create name tags on-the-fly. The major challenges pertain to two aspects - "Who" and "Which". (1) "Who": discriminating people who are in the picture from those that are not; (2) "Which": correlating each name tag with its corresponding people in the picture. We propose an accurate acoustic scheme applying on the mobile phones, which leverages the Doppler effect of sound wave to address these two challenges. As a proof of concept, we implement the scheme on 7 android phones and take pictures in various real-life scenarios with people positioning in different ways. Extensive experiments show that the accuracy of tag correlation is above 85% within 3m for picturing.
Plurality Voting under Uncertainty
Venue: arXiv cs.MA 2014
Year: 2014

Understanding the nature of strategic voting is the holy grail of social choice theory, where game-theory, social science and recently computational approaches are all applied in order to model the incentives and behavior of voters. In a recent paper, Meir et al.[EC'14] made another step in this direction, by suggesting a behavioral game-theoretic model for voters under uncertainty. For a specific variation of best-response heuristics, they proved initial existence and convergence results in the Plurality voting system. In this paper, we extend the model in multiple directions, considering voters with different uncertainty levels, simultaneous strategic decisions, and a more permissive notion of best-response. We prove that a voting equilibrium exists even in the most general case. Further, any society voting in an iterative setting is guaranteed to converge. We also analyze an alternative behavior where voters try to minimize their worst-case regret. We show that the two behaviors coincide in the simple setting of Meir et al., but not in the general case.
Detection of Early-Stage Enterprise Infection by Mining Large-Scale Log Data
Venue: arXiv cs.CR 2014
Year: 2014

Recent years have seen the rise of more sophisticated attacks including advanced persistent threats (APTs) which pose severe risks to organizations and governments by targeting confidential proprietary information. Additionally, new malware strains are appearing at a higher rate than ever before. Since many of these malware are designed to evade existing security products, traditional defenses deployed by most enterprises today, e.g., anti-virus, firewalls, intrusion detection systems, often fail at detecting infections at an early stage. We address the problem of detecting early-stage infection in an enterprise setting by proposing a new framework based on belief propagation inspired from graph theory. Belief propagation can be used either with "seeds" of compromised hosts or malicious domains (provided by the enterprise security operation center -- SOC) or without any seeds. In the latter case we develop a detector of C&C communication particularly tailored to enterprises which can detect a stealthy compromise of only a single host communicating with the C&C server. We demonstrate that our techniques perform well on detecting enterprise infections. We achieve high accuracy with low false detection and false negative rates on two months of anonymized DNS logs released by Los Alamos National Lab (LANL), which include APT infection attacks simulated by LANL domain experts. We also apply our algorithms to 38TB of real-world web proxy logs collected at the border of a large enterprise. Through careful manual investigation in collaboration with the enterprise SOC, we show that our techniques identified hundreds of malicious domains overlooked by state-of-the-art security products.
A Unified View of Large-scale Zero-sum Equilibrium Computation
Venue: arXiv cs.AI 2014
Year: 2014

The task of computing approximate Nash equilibria in large zero-sum extensive-form games has received a tremendous amount of attention due mainly to the Annual Computer Poker Competition. Immediately after its inception, two competing and seemingly different approaches emerged---one an application of no-regret online learning, the other a sophisticated gradient method applied to a convex-concave saddle-point formulation. Since then, both approaches have grown in relative isolation with advancements on one side not effecting the other. In this paper, we rectify this by dissecting and, in a sense, unify the two views.
Consumption Factor Optimization for Multihop Relaying over Nakagami-m Fading channels
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, the energy efficiency of multihop relaying over Nakagami-$m$ fading channels is investigated. The "consumption factor" is used as a metric to evaluate the energy efficiency, and it is derived in closed-form for both amplify-and-forward and decode-and-forward relaying. Then, based on the obtained expressions, we propose a power allocation strategy maximizing the consumption factor. In addition, two sub-optimal, low complexity, power allocation algorithms are proposed and analyzed, and the obtained power allocation schemes are compared, in terms of energy efficiency as well as other common performance metrics, to other power allocation schemes from the literature. Analytical and simulation results confirm the accuracy of our derivations, and assess the performance gains of the proposed approach.
A Rewriting Logic Approach for Automatic Composition of Web Services
Venue: arXiv cs.SE 2014
Year: 2014

Nowadays, Web Services (WS) remain a main actor in the implementation of distributed applications. They represent a new promising paradigm for the development, deployment and integration of Internet applications. These services are in most cases unable to provide the required functionality; they must be composed to provide appropriate services, richer and more interesting for other applications as well as for human users. The composition of Web services is considered as a strong point, which allows answering complex queries by combining the functionality of multiple services within a same composition. In this work we showed how the formalism of graphs can be used to improve the composition of web services and make it automatic. We have proposed the rewriting logic and its language Maude as a support for a graph-based approach to automatic composition of web services. The proposed model has made possible the exploration of different composition schemas as well as the formal analysis of service compositions. The paper introduces a case study showing how to apply our formalization.
Design-theoretic encoding of deterministic hypotheses as constraints and correlations into U-relational databases
Venue: arXiv cs.DB 2014
Year: 2014

In view of the paradigm shift that makes science ever more data-driven, in this paper we consider deterministic scientific hypotheses as uncertain data. In the form of mathematical equations, hypotheses symmetrically relate aspects of the studied phenomena. For computing predictions, however, deterministic hypotheses are used asymmetrically as functions. We refer to Simon's notion of structural equations in order to extract the (so-called) causal ordering embedded in a hypothesis. Then we encode it into a set of functional dependencies (fd's) that is basic input to a design-theoretic method for the synthesis of U-relational databases (DB's). The causal ordering captured from a formally-specified system of mathematical equations into fd's determines not only the constraints (structure), but also the correlations (uncertainty chaining) hidden in the hypothesis predictive data. We show how to process it effectively through original algorithms for encoding and reasoning on the given hypotheses as constraints and correlations into U-relational DB's. The method is applicable to both quantitative and qualitative hypotheses and has underwent initial tests in a realistic use case from computational science.
Generalizing the Liveness Based Points-to Analysis
Venue: arXiv cs.PL 2014
Year: 2014

The original liveness based flow and context sensitive points-to analysis (LFCPA) is restricted to scalar pointer variables and scalar pointees on stack and static memory. In this paper, we extend it to support heap memory and pointer expressions involving structures, unions, arrays, and pointer arithmetic. The key idea behind these extensions involves constructing bounded names for locations in terms of compile time constants (names and fixed offsets), and introducing sound approximations when it is not possible to do so. We achieve this by defining a grammar for pointer expressions, suitable memory models and location naming conventions, and some key evaluations of pointer expressions that compute the named locations. These extensions preserve the spirit of the original LFCPA which is evidenced by the fact that although the lattices and flow functions change, the overall data flow equations remain unchanged.
Genetic Algorithms in Wireless Networking: Techniques, Applications, and Issues
Venue: arXiv cs.NI 2014
Year: 2014

In recent times, wireless access technology is becoming increasingly commonplace due to the ease of operation and installation of untethered wireless media. The design of wireless networking is challenging due to the highly dynamic environmental condition that makes parameter optimization a complex task. Due to the dynamic, and often unknown, operating conditions, modern wireless networking standards increasingly rely on machine learning and artificial intelligence algorithms. Genetic algorithms (GAs) provide a well-established framework for implementing artificial intelligence tasks such as classification, learning, and optimization. GAs are well-known for their remarkable generality and versatility, and have been applied in a wide variety of settings in wireless networks. In this paper, we provide a comprehensive survey of the applications of GAs in wireless networks. We provide both an exposition of common GA models and configuration and provide a broad ranging survey of GA techniques in wireless networks. We also point out open research issues and define potential future work. While various surveys on GAs exist in literature, our paper is the first paper, to the best of our knowledge, which focuses on their application in wireless networks.