OpenRaiser/Intern-Atlas huggingface dataset:
Errors in Improved Polynomial Algorithm For 3 Sat Proposed By Narendra Chaudhari
Venue: arXiv cs.CC 2011
Year: 2011

There are errors in the algorithm proposed by Narendra Chaudhari [2] purporting to solve the 3-sat problem in polynomial time. The present paper present instances for which the algorithm outputs erroneous results.
Simulation Performance of MMSE Iterative Equalization with Soft Boolean Value Propagation
Venue: arXiv cs.IT 2011
Year: 2011

The performance of MMSE Iterative Equalization based on MAP-SBVP and COD-MAP algorithms (for generating extrinsic information) are compared for fading and non-fading communication channels employing serial concatenated convolution codes. MAP-SBVP is a convolution decoder using a conventional soft-MAP decoder followed by a soft-convolution encoder using the soft-boolean value propagation (SBVP). From the simulations it is observed that for MMSE Iterative Equalization, MAP-SBVP performance is comparable to COD-MAP for fading and non-fading channels.
Location- and Time-Dependent VPD for Privacy-Preserving Wireless Accesses to Cloud Services
Venue: arXiv cs.CR 2011
Year: 2011

The advent of smartphones in recent years has changed the wireless landscape. Smartphones have become a platform for online user interface to cloud databases. Cloud databases may provide a large set of user-private and sensitive data (i.e., objects), while smartphone users (i.e., subjects) provide location-sensitive information. Secure and private services in wireless accessing to cloud databases have been discussed actively for the past recent years. However, the previous techniques are unsatisfactory for dynamism of moving subjects' wireless accesses. In this paper, we propose a novel technique to dynamically generate virtual private databases (VPD) for each access by taking subjects' location and time information into account. The contribution of this paper includes a privacy-preserving access control mechanism for dynamism of wireless access.
Correlation-aware Resource Allocation in Multi-Cell Networks
Venue: arXiv cs.IT 2011
Year: 2011

We propose a cross-layer strategy for resource allocation between spatially correlated sources in the uplink of multi-cell FDMA networks. Our objective is to find the optimum power and channel to sources, in order to minimize the maximum distortion achieved by any source in the network. Given that the network is multi-cell, the inter-cell interference must also be taken into consideration. This resource allocation problem is NP-hard and the optimal solution can only be found by exhaustive search over the entire solution space, which is not computationally feasible. We propose a three step method to be performed separately by the scheduler in each cell, which finds cross-layer resource allocation in simple steps. The three- step algorithm separates the problem into inter-cell resource management, grouping of sources for joint decoding, and intra- cell channel assignment. For each of the steps we propose allocation methods that satisfy different design constraints. In the simulations we compare methods for each step of the algorithm. We also demonstrate the overall gain of using correlation-aware resource allocation for a typical multi-cell network of Gaussian sources. We show that, while using correlation in compression and joint decoding can achieve 25% loss in distortion over independent decoding, this loss can be increased to 37% when correlation is also utilized in resource allocation method. This significant distortion loss motivates further work in correlation-aware resource allocation. Overall, we find that our method achieves a 60% decrease in 5 percentile distortion compared to independent methods.
Proposing Cluster_Similarity Method in Order to Find as Much Better Similarities in Databases
Venue: arXiv cs.DB 2011
Year: 2011

Different ways of entering data into databases result in duplicate records that cause increasing of databases' size. This is a fact that we cannot ignore it easily. There are several methods that are used for this purpose. In this paper, we have tried to increase the accuracy of operations by using cluster similarity instead of direct similarity of fields. So that clustering is done on fields of database and according to accomplished clustering on fields, similarity degree of records is obtained. In this method by using present information in database, more logical similarity is obtained for deficient information that in general, the method of cluster similarity could improve operations 24% compared with previous methods.
Partial order approach to compute shortest paths in multimodal networks
Venue: arXiv cs.OH 2011
Year: 2011

Many networked systems involve multiple modes of transport. Such systems are called multimodal, and examples include logistic networks, biomedical phenomena, manufacturing process and telecommunication networks. Existing techniques for determining optimal paths in multimodal networks have either required heuristics or else application-specific constraints to obtain tractable problems, removing the multimodal traits of the network during analysis. In this paper weighted coloured--edge graphs are introduced to model multimodal networks, where colours represent the modes of transportation. Optimal paths are selected using a partial order that compares the weights in each colour, resulting in a Pareto optimal set of shortest paths. This approach is shown to be tractable through experimental analyses for random and real multimodal networks without the need to apply heuristics or constraints.
Community structure and scale-free collections of Erdös-Rényi graphs
Venue: arXiv cs.SI 2011
Year: 2011

Community structure plays a significant role in the analysis of social networks and similar graphs, yet this structure is little understood and not well captured by most models. We formally define a community to be a subgraph that is internally highly connected and has no deeper substructure. We use tools of combinatorics to show that any such community must contain a dense Erdös-Rényi (ER) subgraph. Based on mathematical arguments, we hypothesize that any graph with a heavy-tailed degree distribution and community structure must contain a scale free collection of dense ER subgraphs. These theoretical observations corroborate well with empirical evidence. From this, we propose the Block Two-Level Erdös-Rényi (BTER) model, and demonstrate that it accurately captures the observable properties of many real-world social networks.
L-FLAT: Logtalk Toolkit for Formal Languages and Automata Theory
Venue: arXiv cs.PL 2011
Year: 2011

We describe L-FLAT, a Logtalk Toolkit for teaching Formal Languages and Automata Theory. L-FLAT supports the definition of \textsl{alphabets}, the definition of \textsl{orders} over alphabet symbols, the partial definition of \textsl{languages} using unit tests, and the definition of \textsl{mechanisms}, which implement language generators or language recognizers. Supported mechanisms include \textsl{predicates}, \textsl{regular expressions}, \textsl{finite automata}, \textsl{context-free grammars}, \textsl{Turing machines}, and \textsl{push-down automata}. L-FLAT entities are implemented using the object-oriented features of Logtalk, providing a highly portable and easily extendable framework. The use of L-FLAT in educational environments is enhanced by supporting Mooshak, a web application that features automatic grading of submitted programs.
Nesting Probabilistic Inference
Venue: arXiv cs.PL 2011
Year: 2011

When doing inference in ProbLog, a probabilistic extension of Prolog, we extend SLD resolution with some additional bookkeeping. This additional information is used to compute the probabilistic results for a probabilistic query. In Prolog's SLD, goals are nested very naturally. In ProbLog's SLD, nesting probabilistic queries interferes with the probabilistic bookkeeping. In order to support nested probabilistic inference we propose the notion of a parametrised ProbLog engine. Nesting becomes possible by suspending and resuming instances of ProbLog engines. With our approach we realise several extensions of ProbLog such as meta-calls, negation, and answers of probabilistic goals.
Bijective Term Encodings
Venue: arXiv cs.PL 2011
Year: 2011

We encode/decode Prolog terms as unique natural numbers. Our encodings have the following properties: a) are bijective b) natural numbers always decode to syntactically valid terms c) they work in low polynomial time in the bitsize of the representations d) the bitsize of our encodings is within constant factor of the syntactic representation of the input. We describe encodings of term algebras with finite signature as well as algorithms that separate the "structure" of a term, a natural number encoding of a list of balanced parenthesis, from its "content", a list of atomic terms and Prolog variables. The paper is organized as a literate Prolog program available from \url{http://logic.cse.unt.edu/tarau/research/2011/bijenc.pl}.
Chaotic iterations versus Spread-spectrum: topological-security and stego-security
Venue: arXiv cs.CR 2011
Year: 2011

A new framework for information hiding security, called topological-security, has been proposed in a previous study. It is based on the evaluation of unpredictability of the scheme, whereas existing notions of security, as stego-security, are more linked to information leaks. It has been proven that spread-spectrum techniques, a well-known stego-secure scheme, are topologically-secure too. In this paper, the links between the two notions of security is deepened and the usability of topological-security is clarified, by presenting a novel data hiding scheme that is twice stego and topological-secure. This last scheme has better scores than spread-spectrum when evaluating qualitative and quantitative topological-security properties. Incidentally, this result shows that the new framework for security tends to improve the ability to compare data hiding scheme.
Clustering and Latent Semantic Indexing Aspects of the Nonnegative Matrix Factorization
Venue: arXiv cs.LG 2011
Year: 2011

This paper provides a theoretical support for clustering aspect of the nonnegative matrix factorization (NMF). By utilizing the Karush-Kuhn-Tucker optimality conditions, we show that NMF objective is equivalent to graph clustering objective, so clustering aspect of the NMF has a solid justification. Different from previous approaches which usually discard the nonnegativity constraints, our approach guarantees the stationary point being used in deriving the equivalence is located on the feasible region in the nonnegative orthant. Additionally, since clustering capability of a matrix decomposition technique can sometimes imply its latent semantic indexing (LSI) aspect, we will also evaluate LSI aspect of the NMF by showing its capability in solving the synonymy and polysemy problems in synthetic datasets. And more extensive evaluation will be conducted by comparing LSI performances of the NMF and the singular value decomposition (SVD), the standard LSI method, using some standard datasets.
An Empirical Study on End-users Productivity Using Model-based Spreadsheets
Venue: arXiv cs.HC 2011
Year: 2011

Spreadsheets are widely used, and studies have shown that most end-user spreadsheets contain nontrivial errors. To improve end-users productivity, recent research proposes the use of a model-driven engineering approach to spreadsheets. In this paper we conduct the first systematic empirical study to assess the effectiveness and efficiency of this approach. A set of spreadsheet end users worked with two different model-based spreadsheets, and we present and analyze here the results achieved.
Approximate Decoding Approaches for Network Coded Correlated Data
Venue: arXiv cs.NI 2011
Year: 2011

This paper considers a framework where data from correlated sources are transmitted with help of network coding in ad-hoc network topologies. The correlated data are encoded independently at sensors and network coding is employed in the intermediate nodes in order to improve the data delivery performance. In such settings, we focus on the problem of reconstructing the sources at decoder when perfect decoding is not possible due to losses or bandwidth bottlenecks. We first show that the source data similarity can be used at decoder to permit decoding based on a novel and simple approximate decoding scheme. We analyze the influence of the network coding parameters and in particular the size of finite coding fields on the decoding performance. We further determine the optimal field size that maximizes the expected decoding performance as a trade-off between information loss incurred by limiting the resolution of the source data and the error probability in the reconstructed data. Moreover, we show that the performance of the approximate decoding improves when the accuracy of the source model increases even with simple approximate decoding techniques. We provide illustrative examples about the possible of our algorithms that can be deployed in sensor networks and distributed imaging applications. In both cases, the experimental results confirm the validity of our analysis and demonstrate the benefits of our low complexity solution for delivery of correlated data sources.
Alignment Based Kernel Learning with a Continuous Set of Base Kernels
Venue: arXiv cs.LG 2011
Year: 2011

The success of kernel-based learning methods depend on the choice of kernel. Recently, kernel learning methods have been proposed that use data to select the most appropriate kernel, usually by combining a set of base kernels. We introduce a new algorithm for kernel learning that combines a {\em continuous set of base kernels}, without the common step of discretizing the space of base kernels. We demonstrate that our new method achieves state-of-the-art performance across a variety of real-world datasets. Furthermore, we explicitly demonstrate the importance of combining the right dictionary of kernels, which is problematic for methods based on a finite set of base kernels chosen a priori. Our method is not the first approach to work with continuously parameterized kernels. However, we show that our method requires substantially less computation than previous such approaches, and so is more amenable to multiple dimensional parameterizations of base kernels, which we demonstrate.
Observability of Strapdown INS Alignment: A Global Perspective
Venue: arXiv cs.RO 2011
Year: 2011

Alignment of the strapdown inertial navigation system (INS) has strong nonlinearity, even worse when maneuvers, e.g., tumbling techniques, are employed to improve the alignment. There is no general rule to attack the observability of a nonlinear system, so most previous works addressed the observability of the corresponding linearized system by implicitly assuming that the original nonlinear system and the linearized one have identical observability characteristics. Strapdown INS alignment is a nonlinear system that has its own characteristics. Using the inherent properties of strapdown INS, e.g., the attitude evolution on the SO(3) manifold, we start from the basic definition and develop a global and constructive approach to investigate the observability of strapdown INS static and tumbling alignment, highlighting the effects of the attitude maneuver on observability. We prove that strapdown INS alignment, considering the unknown constant sensor biases, will be completely observable if the strapdown INS is rotated successively about two different axes and will be nearly observable for finite known unobservable states (no more than two) if it is rotated about a single axis. Observability from a global perspective provides us with insights into and a clearer picture of the problem, shedding light on previous theoretical results on strapdown INS alignment that were not comprehensive or consistent.. The reporting of inconsistencies calls for a review of all linearization-based observability studies in the vast literature. Extensive simulations with constructed ideal observers and an extended Kalman filter are carried out, and the numerical results accord with the analysis. The conclusions can also assist in designing the optimal tumbling strategy and the appropriate state observer in practice to maximize the alignment performance.
Zero-Temperature Limit of a Convergent Algorithm to Minimize the Bethe Free Energy
Venue: arXiv cs.CV 2011
Year: 2011

After the discovery that fixed points of loopy belief propagation coincide with stationary points of the Bethe free energy, several researchers proposed provably convergent algorithms to directly minimize the Bethe free energy. These algorithms were formulated only for non-zero temperature (thus finding fixed points of the sum-product algorithm) and their possible extension to zero temperature is not obvious. We present the zero-temperature limit of the double-loop algorithm by Heskes, which converges a max-product fixed point. The inner loop of this algorithm is max-sum diffusion. Under certain conditions, the algorithm combines the complementary advantages of the max-product belief propagation and max-sum diffusion (LP relaxation): it yields good approximation of both ground states and max-marginals.
2P-Med: Building a Personalization Platform for Mediation Systems
Venue: arXiv cs.IR 2011
Year: 2011

Nowadays, with the increasing number of integrated data sources, there is a real trend to personalize mediation systems to improve user satisfaction. To make these systems user sensitive, we propose a personalization platform called 2P-Med. 2P-Med allows personalizing any mediation system used in any domain following a cyclic process. The process includes building and managing adequate user profiles and sources profiles, content and quality matching, source selection, adapting the mediator responses to user preferences and handling user feedbacks. In this paper, we describe 2P-Med architecture and highlight its main functionalities. We also illustrate the operation of the platform through personalizing source selection in a travel planning assistant.
SPAM -- Technological and Legal Aspects
Venue: arXiv cs.CR 2011
Year: 2011

In this paper an attempt is made to review technological, economical and legal aspects of the spam in detail. The technical details will include different techniques of spam control e.g., filtering techniques, Genetic Algorithm, Memory Based Classifier, Support Vector Machine Method, etc. The economic aspect includes Shaping/Rate Throttling Approach/Economic Filtering and Pricing/Payment based spam control. Finally, the paper discusses the legal provisions for the control of spam. The scope of the legal options is limited to USA, European Union, New Zealand, Canada, Britain and Australia.
Relay-Assisted Interference Channel: Degrees of Freedom
Venue: arXiv cs.IT 2011
Year: 2011

This paper investigates the degrees of freedom of the interference channel in the presence of a dedicated MIMO relay. The relay is used to manage the interference at the receivers. It is assumed that all nodes including the relay have channel state information only for their own links and that the relay has M (greater than or equal to K) antennas in a K-user network. We pose the question: What is the benefit of exploiting the direct links from the source to destinations compared to a simpler two-hop strategy. To answer this question, we first establish the degrees of freedom of the interference channel with a MIMO relay, showing that a K-pair network with a MIMO relay has K/2 degrees of freedom. Thus, appropriate signaling in a two-hop scenario captures the degrees of freedom without the need for the direct links. We then consider more sophisticated encoding strategies in search of other ways to exploit the direct links. Using a number of hybrid encoding strategies, we obtain non-asymptotic achievable sum-rates. We investigate the case where the relay (unlike other nodes) has access to abundant power, showing that when sources have power P and the relay is allowed power proportional to O(P^2), the full degrees of freedom K are available to the network.
Online Adaptive Statistical Compressed Sensing of Gaussian Mixture Models
Venue: arXiv cs.CV 2011
Year: 2011

A framework of online adaptive statistical compressed sensing is introduced for signals following a mixture model. The scheme first uses non-adaptive measurements, from which an online decoding scheme estimates the model selection. As soon as a candidate model has been selected, an optimal sensing scheme for the selected model continues to apply. The final signal reconstruction is calculated from the ensemble of both the non-adaptive and the adaptive measurements. For signals generated from a Gaussian mixture model, the online adaptive sensing algorithm is given and its performance is analyzed. On both synthetic and real image data, the proposed adaptive scheme considerably reduces the average reconstruction error with respect to standard statistical compressed sensing that uses fully random measurements, at a marginally increased computational complexity.
Management of Data Replication for PC Cluster-based Cloud Storage System
Venue: arXiv cs.DC 2011
Year: 2011

Storage systems are essential building blocks for cloud computing infrastructures. Although high performance storage servers are the ultimate solution for cloud storage, the implementation of inexpensive storage system remains an open issue. To address this problem, the efficient cloud storage system is implemented with inexpensive and commodity computer nodes that are organized into PC cluster based datacenter. Hadoop Distributed File System (HDFS) is an open source cloud based storage platform and designed to be deployed in low-cost hardware. PC Cluster based Cloud Storage System is implemented with HDFS by enhancing replication management scheme. Data objects are distributed and replicated in a cluster of commodity nodes located in the cloud. This system provides optimum replica number as well as weighting and balancing among the storage server nodes. The experimental results show that storage can be balanced depending on the available disk space, expected availability and failure probability of each node in PC cluster.
Disseny d'un prototipus de xarxa MESH sense fils multirádio i multicanal sobre OLSR modificat amb canal de senyalització dedicat
Venue: arXiv cs.NI 2011
Year: 2011

Wireless mesh cubes are used to improve the channel signaling.
Characterization of $2^n$-periodic binary sequences with fixed 3-error or 4-error linear complexity
Venue: arXiv cs.CR 2011
Year: 2011

The linear complexity and the $k$-error linear complexity of a sequence have been used as important security measures for key stream sequence strength in linear feedback shift register design. By using the sieve method of combinatorics, the $k$-error linear complexity distribution of $2^n$-periodic binary sequences is investigated based on Games-Chan algorithm. First, for $k=2,3$, the complete counting functions on the $k$-error linear complexity of $2^n$-periodic binary sequences with linear complexity less than $2^n$ are characterized. Second, for $k=3,4$, the complete counting functions on the $k$-error linear complexity of $2^n$-periodic binary sequences with linear complexity $2^n$ are presented. Third, for $k=4,5$, the complete counting functions on the $k$-error linear complexity of $2^n$-periodic binary sequences with linear complexity less than $2^n$ are derived. As a consequence of these results, the counting functions for the number of $2^n$-periodic binary sequences with the 3-error linear complexity are obtained, and the complete counting functions on the 4-error linear complexity of $2^n$-periodic binary sequences are obvious.