OpenRaiser/Intern-Atlas huggingface dataset:
A Game Theoretical Approach to Modeling Full-Duplex Information Dissemination
Venue: arXiv cs.GT 2010
Year: 2010

One major function of social networks (e.g., massive online social networks) is the dissemination of information such as scientific knowledge, news, and rumors. Information can be propagated by the users of the network via natural connections in written, oral or electronic form. The information passing from a sender to a receiver intrinsically involves both of them considering their self-perceived knowledge, reputation, and popularity, which further determine their decisions of whether or not to forward the information and whether or not to provide feedback. To understand such human aspects of the information dissemination, we propose a game theoretical model of the two-way full duplex information forwarding and feedback mechanisms in a social network that take into account the personalities of the communicating actors (including their perceived knowledgeability, reputation, and desire for popularity) and the global characteristics of the network. The model demonstrates how the emergence of social networks can be explained in terms of maximizing game theoretical utility.
Probabilistic Frequent Pattern Growth for Itemset Mining in Uncertain Databases (Technical Report)
Venue: arXiv cs.DB 2010
Year: 2010

Frequent itemset mining in uncertain transaction databases semantically and computationally differs from traditional techniques applied on standard (certain) transaction databases. Uncertain transaction databases consist of sets of existentially uncertain items. The uncertainty of items in transactions makes traditional techniques inapplicable. In this paper, we tackle the problem of finding probabilistic frequent itemsets based on possible world semantics. In this context, an itemset X is called frequent if the probability that X occurs in at least minSup transactions is above a given threshold. We make the following contributions: We propose the first probabilistic FP-Growth algorithm (ProFP-Growth) and associated probabilistic FP-Tree (ProFP-Tree), which we use to mine all probabilistic frequent itemsets in uncertain transaction databases without candidate generation. In addition, we propose an efficient technique to compute the support probability distribution of an itemset in linear time using the concept of generating functions. An extensive experimental section evaluates the our proposed techniques and shows that our ProFP-Growth approach is significantly faster than the current state-of-the-art algorithm.
Removing the Barrier to Scalability in Parallel FMM
Venue: arXiv cs.CE 2010
Year: 2010

The Fast Multipole Method (FMM) is well known to possess a bottleneck arising from decreasing workload on higher levels of the FMM tree [Greengard and Gropp, Comp. Math. Appl., 20(7), 1990]. We show that this potential bottleneck can be eliminated by overlapping multipole and local expansion computations with direct kernel evaluations on the finest level grid.
Epistemic irrelevance in credal nets: the case of imprecise Markov trees
Venue: arXiv cs.AI 2010
Year: 2010

We focus on credal nets, which are graphical models that generalise Bayesian nets to imprecise probability. We replace the notion of strong independence commonly used in credal nets with the weaker notion of epistemic irrelevance, which is arguably more suited for a behavioural theory of probability. Focusing on directed trees, we show how to combine the given local uncertainty models in the nodes of the graph into a global model, and we use this to construct and justify an exact message-passing algorithm that computes updated beliefs for a variable in the tree. The algorithm, which is linear in the number of nodes, is formulated entirely in terms of coherent lower previsions, and is shown to satisfy a number of rationality requirements. We supply examples of the algorithm's operation, and report an application to on-line character recognition that illustrates the advantages of our approach for prediction. We comment on the perspectives, opened by the availability, for the first time, of a truly efficient algorithm based on epistemic irrelevance.
Homotopy Perturbation Method for Image Restoration and Denoising
Venue: arXiv cs.CV 2010
Year: 2010

The famous Perona-Malik (P-M) equation which was at first introduced for image restoration has been solved via various numerical methods. In this paper we will solve it for the first time via applying a new numerical method called Homotopy Perturbation Method (HMP) and the correspondent approximated solutions will be obtained for the P-M equation with regards to relevant error analysis. Through implementation of our algorithm we will access some effective results which are deserved to be considered as worthy as the other solutions issued by the other methods.
Joint maximum likelihood estimation of carrier and sampling frequency offsets for OFDM systems
Venue: arXiv cs.IT 2010
Year: 2010

In orthogonal-frequency division multiplexing (OFDM) systems, carrier and sampling frequency offsets (CFO and SFO, respectively) can destroy the orthogonality of the subcarriers and degrade system performance. In the literature, Nguyen-Le, Le-Ngoc, and Ko proposed a simple maximum-likelihood (ML) scheme using two long training symbols for estimating the initial CFO and SFO of a recursive least-squares (RLS) estimation scheme. However, the results of Nguyen-Le's ML estimation show poor performance relative to the Cramer-Rao bound (CRB). In this paper, we extend Moose's CFO estimation algorithm to joint ML estimation of CFO and SFO using two long training symbols. In particular, we derive CRBs for the mean square errors (MSEs) of CFO and SFO estimation. Simulation results show that the proposed ML scheme provides better performance than Nguyen-Le's ML scheme.
Mining tree-query associations in graphs
Venue: arXiv cs.DB 2010
Year: 2010

New applications of data mining, such as in biology, bioinformatics, or sociology, are faced with large datasetsstructured as graphs. We introduce a novel class of tree-shapedpatterns called tree queries, and present algorithms for miningtree queries and tree-query associations in a large data graph. Novel about our class of patterns is that they can containconstants, and can contain existential nodes which are not counted when determining the number of occurrences of the patternin the data graph. Our algorithms have a number of provableoptimality properties, which are based on the theory of conjunctive database queries. We propose a practical, database-oriented implementation in SQL, and show that the approach works in practice through experiments on data about food webs, protein interactions, and citation analysis.
Optimized Image Steganalysis through Feature Selection using MBEGA
Venue: arXiv cs.CR 2010
Year: 2010

Feature based steganalysis, an emerging branch in information forensics, aims at identifying the presence of a covert communication by employing the statistical features of the cover and stego image as clues/evidences. Due to the large volumes of security audit data as well as complex and dynamic properties of steganogram behaviours, optimizing the performance of steganalysers becomes an important open problem. This paper is focussed at fine tuning the performance of six promising steganalysers in this field, through feature selection. We propose to employ Markov Blanket-Embedded Genetic Algorithm (MBEGA) for stego sensitive feature selection process. In particular, the embedded Markov blanket based memetic operators add or delete features (or genes) from a genetic algorithm (GA) solution so as to quickly improve the solution and fine-tune the search. Empirical results suggest that MBEGA is effective and efficient in eliminating irrelevant and redundant features based on both Markov blanket and predictive power in classifier model. Observations show that the proposed method is superior in terms of number of selected features, classification accuracy and computational cost than their existing counterparts.
Benaloh's Dense Probabilistic Encryption Revisited
Venue: arXiv cs.CR 2010
Year: 2010

In 1994, Josh Benaloh proposed a probabilistic homomorphic encryption scheme, enhancing the poor expansion factor provided by Goldwasser and Micali's scheme. Since then, numerous papers have taken advantage of Benaloh's homomorphic encryption function, including voting schemes, computing multi-party trust privately, non-interactive verifiable secret sharing, online poker... In this paper we show that the original description of the scheme is incorrect, possibly resulting in ambiguous decryption of ciphertexts. We give a corrected description of the scheme and provide a complete proof of correctness. We also compute the probability of failure of the original scheme. Finally we analyze several applications using Benaloh's encryption scheme. We show in each case the impact of a bad choice in the key generation phase of Benaloh's scheme. For instance in the application of e-voting protocol, it can inverse the result of an election, which is a non negligible consequence.
The Two Quadrillionth Bit of Pi is 0! Distributed Computation of Pi with Apache Hadoop
Venue: arXiv cs.DC 2010
Year: 2010

We present a new record on computing specific bits of Pi, the mathematical constant, and discuss performing such computations on Apache Hadoop clusters. The specific bits represented in hexadecimal are 0E6C1294 AED40403 F56D2D76 4026265B CA98511D 0FCFFAA1 0F4D28B1 BB5392B8. These 256 bits end at the 2,000,000,000,000,252nd bit position, which doubles the position and quadruples the precision of the previous known record. The position of the first bit is 1,999,999,999,999,997 and the value of the two quadrillionth bit is 0. The computation is carried out by a MapReduce program called DistBbp. To effectively utilize available cluster resources without monopolizing the whole cluster, we develop an elastic computation framework that automatically schedules computation slices, each a DistBbp job, as either map-side or reduce-side computation based on changing cluster load condition. We have calculated Pi at varying bit positions and precisions, and one of the largest computations took 23 days of wall clock time and 503 years of CPU time on a 1000-node cluster.
On The Signed Edge Domination Number of Graphs
Venue: arXiv cs.DM 2010
Year: 2010

Let $γ'_s(G)$ be the signed edge domination number of G. In 2006, Xu conjectured that: for any $2$-connected graph G of order $ n (n \geq 2),$ $γ'_s(G)\geq 1$. In this article we show that this conjecture is not true. More precisely, we show that for any positive integer $m$, there exists an $m$-connected graph $G$ such that $ γ'_s(G)\leq -\frac{m}{6}|V(G)|.$ Also for every two natural numbers $m$ and $n$, we determine $γ'_s(K_{m,n})$, where $K_{m,n}$ is the complete bipartite graph with part sizes $m$ and $n$.
Secure Operations on Tree-Formed Verification Data
Venue: arXiv cs.CR 2010
Year: 2010

We define secure operations with tree-formed, protected verification data registers. Functionality is conceptually added to Trusted Platform Modules (TPMs) to handle Platform Configuration Registers (PCRs) which represent roots of hash trees protecting the integrity of tree-formed Stored Measurement Logs (SMLs). This enables verification and update of an inner node of an SML and even attestation to its value with the same security level as for ordinary PCRs. As an important application, it is shown how certification of SML subtrees enables attestation of platform properties.
Reversible Logic Synthesis of Fault Tolerant Carry Skip BCD Adder
Venue: arXiv cs.AR 2010
Year: 2010

Reversible logic is emerging as an important research area having its application in diverse fields such as low power CMOS design, digital signal processing, cryptography, quantum computing and optical information processing. This paper presents a new 4*4 parity preserving reversible logic gate, IG. The proposed parity preserving reversible gate can be used to synthesize any arbitrary Boolean function. It allows any fault that affects no more than a single signal readily detectable at the circuit's primary outputs. It is shown that a fault tolerant reversible full adder circuit can be realized using only two IGs. The proposed fault tolerant full adder (FTFA) is used to design other arithmetic logic circuits for which it is used as the fundamental building block. It has also been demonstrated that the proposed design offers less hardware complexity and is efficient in terms of gate count, garbage outputs and constant inputs than the existing counterparts.
An Individual-based Probabilistic Model for Fish Stock Simulation
Venue: arXiv cs.FL 2010
Year: 2010

We define an individual-based probabilistic model of a sole (Solea solea) behaviour. The individual model is given in terms of an Extended Probabilistic Discrete Timed Automaton (EPDTA), a new formalism that is introduced in the paper and that is shown to be interpretable as a Markov decision process. A given EPDTA model can be probabilistically model-checked by giving a suitable translation into syntax accepted by existing model-checkers. In order to simulate the dynamics of a given population of soles in different environmental scenarios, an agent-based simulation environment is defined in which each agent implements the behaviour of the given EPDTA model. By varying the probabilities and the characteristic functions embedded in the EPDTA model it is possible to represent different scenarios and to tune the model itself by comparing the results of the simulations with real data about the sole stock in the North Adriatic sea, available from the recent project SoleMon. The simulator is presented and made available for its adaptation to other species.
Fault tolerant reversible logic synthesis: Carry look-ahead and carry-skip adders
Venue: arXiv cs.AR 2010
Year: 2010

Irreversible logic circuits dissipate heat for every bit of information that is lost. Information is lost when the input vector cannot be recovered from its corresponding output vector. Reversible logic circuit naturally takes care of heating because it implements only the functions that have one-to-one mapping between its input and output vectors. Therefore reversible logic design becomes one of the promising research directions in low power dissipating circuit design in the past few years and has found its application in low power CMOS design, digital signal processing and nanotechnology. This paper presents the efficient approaches for designing reversible fast adders that implement carry look-ahead and carry-skip logic. The proposed 16-bit high speed reversible adder will include IG gates for the realization of its basic building block. The IG gate is universal in the sense that it can be used to synthesize any arbitrary Boolean-functions. The IG gate is parity preserving, that is, the parity of the inputs matches the parity of the outputs. It allows any fault that affects no more than a single signal readily detectable at the circuit's primary outputs. Therefore, the proposed high speed adders will have the inherent opportunity of detecting errors in its output side. It has also been demonstrated that the proposed design offers less hardware complexity and is efficient in terms of gate count, garbage outputs and constant inputs than the existing counterparts.
Homogeneous and Non Homogeneous Algorithms
Venue: arXiv cs.DS 2010
Year: 2010

Motivated by recent best case analyses for some sorting algorithms and based on the type of complexity we partition the algorithms into two classes: homogeneous and non homogeneous algorithms. Although both classes contain algorithms with worst and best cases, homogeneous algorithms behave uniformly on all instances. This partition clarifies in a completely mathematical way the previously mentioned terms and reveals that in classifying an algorithm as homogeneous or not best case analysis is equally important with worst case analysis.
Crystallized Rates Region of the Interference Channel via Correlated Equilibrium with Interference as Noise
Venue: arXiv cs.IT 2010
Year: 2010

Treating the interference as noise in the n-user interference channel, the paper describes a novel approach to the rates region, composed by the time-sharing convex hull of 2^n-1 corner points achieved through On/Off binary power control. The resulting rates region is denoted crystallized rates region. By treating the interference as noise, the n-user rates region frontiers has been found in the literature to be the convex hull of n hyper-surfaces. The rates region bounded by these hyper-surfaces is not necessarily convex, and thereby a convex hull operation is imposed through the strategy of time-sharing. This paper simplifies this rates region in the n-dimensional space by having only an On/Off binary power control. This consequently leads to 2^n-1 corner points situated within the rates region. A time-sharing convex hull is imposed onto those corner points, forming the crystallized rates region. The paper focuses on game theoretic concepts to achieve that crystallized convex hull via correlated equilibrium. In game theory, the correlated equilibrium set is convex, and it consists of the time-sharing mixed strategies of the Nash equilibriums. In addition, the paper considers a mechanism design approach to carefully design a utility function, particularly the Vickrey-Clarke-Groves auction utility, where the solution point is situated on the correlated equilibrium set. Finally, the paper proposes a self learning algorithm, namely the regret-matching algorithm, that converges to the solution point on the correlated equilibrium set in a distributed fashion.
Formal-language-theoretic Optimal Path Planning For Accommodation of Amortized Uncertainties and Dynamic Effects
Venue: arXiv cs.RO 2010
Year: 2010

We report a globally-optimal approach to robotic path planning under uncertainty, based on the theory of quantitative measures of formal languages. A significant generalization to the language-measure-theoretic path planning algorithm $\nustar$ is presented that explicitly accounts for average dynamic uncertainties and estimation errors in plan execution. The notion of the navigation automaton is generalized to include probabilistic uncontrollable transitions, which account for uncertainties by modeling and planning for probabilistic deviations from the computed policy in the course of execution. The planning problem is solved by casting it in the form of a performance maximization problem for probabilistic finite state automata. In essence we solve the following optimization problem: Compute the navigation policy which maximizes the probability of reaching the goal, while simultaneously minimizing the probability of hitting an obstacle. Key novelties of the proposed approach include the modeling of uncertainties using the concept of uncontrollable transitions, and the solution of the ensuing optimization problem using a highly efficient search-free combinatorial approach to maximize quantitative measures of probabilistic regular languages. Applicability of the algorithm in various models of robot navigation has been shown with experimental validation on a two-wheeled mobile robotic platform (SEGWAY RMP 200) in a laboratory environment.
Fully Automatic Trunk Packing with Free Placements
Venue: arXiv cs.DS 2010
Year: 2010

We present a new algorithm to compute the volume of a trunk according to the SAE J1100 standard. Our new algorithm uses state-of-the-art methods from computational geometry and from combinatorial optimization. It finds better solutions than previous approaches for small trunks.
Malware Classification based on Call Graph Clustering
Venue: arXiv cs.CR 2010
Year: 2010

Each day, anti-virus companies receive tens of thousands samples of potentially harmful executables. Many of the malicious samples are variations of previously encountered malware, created by their authors to evade pattern-based detection. Dealing with these large amounts of data requires robust, automatic detection approaches. This paper studies malware classification based on call graph clustering. By representing malware samples as call graphs, it is possible to abstract certain variations away, and enable the detection of structural similarities between samples. The ability to cluster similar samples together will make more generic detection techniques possible, thereby targeting the commonalities of the samples within a cluster. To compare call graphs mutually, we compute pairwise graph similarity scores via graph matchings which approximately minimize the graph edit distance. Next, to facilitate the discovery of similar malware samples, we employ several clustering algorithms, including k-medoids and DBSCAN. Clustering experiments are conducted on a collection of real malware samples, and the results are evaluated against manual classifications provided by human malware analysts. Experiments show that it is indeed possible to accurately detect malware families via call graph clustering. We anticipate that in the future, call graphs can be used to analyse the emergence of new malware families, and ultimately to automate implementation of generic detection schemes.
Simulation Factory: Taming Application Configuration and Workflow on High-End Resources
Venue: arXiv cs.DC 2010
Year: 2010

Computational Science on large high performance computing resources is hampered by the complexity of these systems. Much of this complexity is due to low-level details on these resources that are exposed to the application and the end user. This includes (but is not limited to) mechanisms for remote access, configuring and building applications from source code, and managing simulations and their output files via batch queue systems. These challenges multiply in a modern research environment, where a research collaboration spans multiple groups, often in loosely defined international collaborations, where there is a constant influx of new students into multi-year projects, and where simulations are performed on several different resources. The Simulation Factory addresses these challenges by significantly simplifying remote access, building executables, and managing simulations. By abstracting out the low-level differences between different resources, it offers a uniform interface to these resources. At the same time, it can enforce certain standards for performing simulations that encapsulate best practices from experienced users. Furthermore, SimFactory's automation avoids many possible user errors that can in the worst case render month-long simulations worthless.
Freezing and Sleeping: Tracking Experts that Learn by Evolving Past Posteriors
Venue: arXiv cs.LG 2010
Year: 2010

A problem posed by Freund is how to efficiently track a small pool of experts out of a much larger set. This problem was solved when Bousquet and Warmuth introduced their mixing past posteriors (MPP) algorithm in 2001. In Freund's problem the experts would normally be considered black boxes. However, in this paper we re-examine Freund's problem in case the experts have internal structure that enables them to learn. In this case the problem has two possible interpretations: should the experts learn from all data or only from the subsequence on which they are being tracked? The MPP algorithm solves the first case. Our contribution is to generalise MPP to address the second option. The results we obtain apply to any expert structure that can be formalised using (expert) hidden Markov models. Curiously enough, for our interpretation there are \emph{two} natural reference schemes: freezing and sleeping. For each scheme, we provide an efficient prediction strategy and prove the relevant loss bound.