OpenRaiser/Intern-Atlas huggingface dataset:
Evolutionary Computation Algorithms for Cryptanalysis: A Study
Venue: arXiv cs.CR 2010
Year: 2010

The cryptanalysis of various cipher problems can be formulated as NP-Hard combinatorial problem. Solving such problems requires time and/or memory requirement which increases with the size of the problem. Techniques for solving combinatorial problems fall into two broad groups - exact algorithms and Evolutionary Computation algorithms. An exact algorithms guarantees that the optimal solution to the problem will be found. The exact algorithms like branch and bound, simplex method, brute force etc methodology is very inefficient for solving combinatorial problem because of their prohibitive complexity (time and memory requirement). The Evolutionary Computation algorithms are employed in an attempt to find an adequate solution to the problem. A Evolutionary Computation algorithm - Genetic algorithm, simulated annealing and tabu search were developed to provide a robust and efficient methodology for cryptanalysis. The aim of these techniques to find sufficient "good" solution efficiently with the characteristics of the problem, instead of the global optimum solution, and thus it also provides attractive alternative for the large scale applications. This paper focuses on the methodology of Evolutionary Computation algorithms .
A Unified Formal Description of Arithmetic and Set Theoretical Data Types
Venue: arXiv cs.SC 2010
Year: 2010

We provide a "shared axiomatization" of natural numbers and hereditarily finite sets built around a polymorphic abstraction of bijective base-2 arithmetics. The "axiomatization" is described as a progressive refinement of Haskell type classes with examples of instances converging to an efficient implementation in terms of arbitrary length integers and bit operations. As an instance, we derive algorithms to perform arithmetic operations efficiently directly with hereditarily finite sets. The self-contained source code of the paper is available at http://logic.cse.unt.edu/tarau/research/2010/unified.hs .
Application of Statistical Features in Handwritten Devnagari Character Recognition
Venue: arXiv cs.CV 2010
Year: 2010

In this paper a scheme for offline Handwritten Devnagari Character Recognition is proposed, which uses different feature extraction methodologies and recognition algorithms. The proposed system assumes no constraints in writing style or size. First the character is preprocessed and features namely : Chain code histogram and moment invariant features are extracted and fed to Multilayer Perceptrons as a preliminary recognition step. Finally the results of both MLP's are combined using weighted majority scheme. The proposed system is tested on 1500 handwritten devnagari character database collected from different people. It is observed that the proposed system achieves recognition rates 98.03% for top 5 results and 89.46% for top 1 result.
A Two Stage Classification Approach for Handwritten Devanagari Characters
Venue: arXiv cs.CV 2010
Year: 2010

The paper presents a two stage classification approach for handwritten devanagari characters The first stage is using structural properties like shirorekha, spine in character and second stage exploits some intersection features of characters which are fed to a feedforward neural network. Simple histogram based method does not work for finding shirorekha, vertical bar (Spine) in handwritten devnagari characters. So we designed a differential distance based technique to find a near straight line for shirorekha and spine. This approach has been tested for 50000 samples and we got 89.12% success
Classification Of Gradient Change Features Using MLP For Handwritten Character Recognition
Venue: arXiv cs.CV 2010
Year: 2010

A novel, generic scheme for off-line handwritten English alphabets character images is proposed. The advantage of the technique is that it can be applied in a generic manner to different applications and is expected to perform better in uncertain and noisy environments. The recognition scheme is using a multilayer perceptron(MLP) neural networks. The system was trained and tested on a database of 300 samples of handwritten characters. For improved generalization and to avoid overtraining, the whole available dataset has been divided into two subsets: training set and test set. We achieved 99.10% and 94.15% correct recognition rates on training and test sets respectively. The purposed scheme is robust with respect to various writing styles and size as well as presence of considerable noise.
The Computational Complexity of Estimating Convergence Time
Venue: arXiv cs.DS 2010
Year: 2010

An important problem in the implementation of Markov Chain Monte Carlo algorithms is to determine the convergence time, or the number of iterations before the chain is close to stationarity. For many Markov chains used in practice this time is not known. Even in cases where the convergence time is known to be polynomial, the theoretical bounds are often too crude to be practical. Thus, practitioners like to carry out some form of statistical analysis in order to assess convergence. This has led to the development of a number of methods known as convergence diagnostics which attempt to diagnose whether the Markov chain is far from stationarity. We study the problem of testing convergence in the following settings and prove that the problem is hard in a computational sense: Given a Markov chain that mixes rapidly, it is hard for Statistical Zero Knowledge (SZK-hard) to distinguish whether starting from a given state, the chain is close to stationarity by time t or far from stationarity at time ct for a constant c. We show the problem is in AM intersect coAM. Second, given a Markov chain that mixes rapidly it is coNP-hard to distinguish whether it is close to stationarity by time t or far from stationarity at time ct for a constant c. The problem is in coAM. Finally, it is PSPACE-complete to distinguish whether the Markov chain is close to stationarity by time t or far from being mixed at time ct for c at least 1.
A Bound on the Sum of Weighted Pairwise Distances of Points Constrained to Balls
Venue: arXiv cs.DS 2010
Year: 2010

We consider the problem of choosing Euclidean points to maximize the sum of their weighted pairwise distances, when each point is constrained to a ball centered at the origin. We derive a dual minimization problem and show strong duality holds (i.e., the resulting upper bound is tight) when some locally optimal configuration of points is affinely independent. We sketch a polynomial time algorithm for finding a near-optimal set of points.
Additive Non-negative Matrix Factorization for Missing Data
Venue: arXiv cs.NA 2010
Year: 2010

Non-negative matrix factorization (NMF) has previously been shown to be a useful decomposition for multivariate data. We interpret the factorization in a new way and use it to generate missing attributes from test data. We provide a joint optimization scheme for the missing attributes as well as the NMF factors. We prove the monotonic convergence of our algorithms. We present classification results for cases with missing attributes.
Privacy in geo-social networks: proximity notification with untrusted service providers and curious buddies
Venue: arXiv cs.DB 2010
Year: 2010

A major feature of the emerging geo-social networks is the ability to notify a user when one of his friends (also called buddies) happens to be geographically in proximity with the user. This proximity service is usually offered by the network itself or by a third party service provider (SP) using location data acquired from the users. This paper provides a rigorous theoretical and experimental analysis of the existing solutions for the location privacy problem in proximity services. This is a serious problem for users who do not trust the SP to handle their location data, and would only like to release their location information in a generalized form to participating buddies. The paper presents two new protocols providing complete privacy with respect to the SP, and controllable privacy with respect to the buddies. The analytical and experimental analysis of the protocols takes into account privacy, service precision, and computation and communication costs, showing the superiority of the new protocols compared to those appeared in the literature to date. The proposed protocols have also been tested in a full system implementation of the proximity service.
An Improved Neighbourhood for the Traveling Tournament Problem
Venue: arXiv cs.DS 2010
Year: 2010

The Traveling Tournament Problem (TTP) is a challenging combinatorial optimization problem that has attracted the interest of researchers around the world. This paper proposes an improved search neighbourhood for the TTP that has been tested in a simulated annealing context. The neighbourhood encompasses both feasible and infeasible schedules, and can be generated efficiently. For the largest TTP challenge problems with up to 40 teams, solutions found using this neighbourhood are the best currently known, and for smaller problems with 10 teams, three solutions found were subsequently proven optimal.
Binary Independent Component Analysis with OR Mixtures
Venue: arXiv cs.IT 2010
Year: 2010

Independent component analysis (ICA) is a computational method for separating a multivariate signal into subcomponents assuming the mutual statistical independence of the non-Gaussian source signals. The classical Independent Components Analysis (ICA) framework usually assumes linear combinations of independent sources over the field of realvalued numbers R. In this paper, we investigate binary ICA for OR mixtures (bICA), which can find applications in many domains including medical diagnosis, multi-cluster assignment, Internet tomography and network resource management. We prove that bICA is uniquely identifiable under the disjunctive generation model, and propose a deterministic iterative algorithm to determine the distribution of the latent random variables and the mixing matrix. The inverse problem concerning inferring the values of latent variables are also considered along with noisy measurements. We conduct an extensive simulation study to verify the effectiveness of the propose algorithm and present examples of real-world applications where bICA can be applied.
A Fast Decision Technique for Hierarchical Hough Transform for Line Detection
Venue: arXiv cs.CV 2010
Year: 2010

Many techniques have been proposed to speedup the performance of classic Hough Transform. These techniques are primarily based on converting the voting procedure to a hierarchy based voting method. These methods use approximate decision-making process. In this paper, we propose a fast decision making process that enhances the speed and reduces the space requirements. Experimental results demonstrate that the proposed algorithm is much faster than a similar Fast Hough Transform.
On The Complexity and Completeness of Static Constraints for Breaking Row and Column Symmetry
Venue: arXiv cs.AI 2010
Year: 2010

We consider a common type of symmetry where we have a matrix of decision variables with interchangeable rows and columns. A simple and efficient method to deal with such row and column symmetry is to post symmetry breaking constraints like DOUBLELEX and SNAKELEX. We provide a number of positive and negative results on posting such symmetry breaking constraints. On the positive side, we prove that we can compute in polynomial time a unique representative of an equivalence class in a matrix model with row and column symmetry if the number of rows (or of columns) is bounded and in a number of other special cases. On the negative side, we show that whilst DOUBLELEX and SNAKELEX are often effective in practice, they can leave a large number of symmetric solutions in the worst case. In addition, we prove that propagating DOUBLELEX completely is NP-hard. Finally we consider how to break row, column and value symmetry, correcting a result in the literature about the safeness of combining different symmetry breaking constraints. We end with the first experimental study on how much symmetry is left by DOUBLELEX and SNAKELEX on some benchmark problems.
Fusion of Daubechies Wavelet Coefficients for Human Face Recognition
Venue: arXiv cs.CV 2010
Year: 2010

In this paper fusion of visual and thermal images in wavelet transformed domain has been presented. Here, Daubechies wavelet transform, called as D2, coefficients from visual and corresponding coefficients computed in the same manner from thermal images are combined to get fused coefficients. After decomposition up to fifth level (Level 5) fusion of coefficients is done. Inverse Daubechies wavelet transform of those coefficients gives us fused face images. The main advantage of using wavelet transform is that it is well-suited to manage different image resolution and allows the image decomposition in different kinds of coefficients, while preserving the image information. Fused images thus found are passed through Principal Component Analysis (PCA) for reduction of dimensions and then those reduced fused images are classified using a multi-layer perceptron. For experiments IRIS Thermal/Visual Face Database was used. Experimental results show that the performance of the approach presented here achieves maximum success rate of 100% in many cases.
A Parallel Framework for Multilayer Perceptron for Human Face Recognition
Venue: arXiv cs.CV 2010
Year: 2010

Artificial neural networks have already shown their success in face recognition and similar complex pattern recognition tasks. However, a major disadvantage of the technique is that it is extremely slow during training for larger classes and hence not suitable for real-time complex problems such as pattern recognition. This is an attempt to develop a parallel framework for the training algorithm of a perceptron. In this paper, two general architectures for a Multilayer Perceptron (MLP) have been demonstrated. The first architecture is All-Class-in-One-Network (ACON) where all the classes are placed in a single network and the second one is One-Class-in-One-Network (OCON) where an individual single network is responsible for each and every class. Capabilities of these two architectures were compared and verified in solving human face recognition, which is a complex pattern recognition task where several factors affect the recognition performance like pose variations, facial expression changes, occlusions, and most importantly illumination changes. Both the structures were implemented and tested for face recognition purpose and experimental results show that the OCON structure performs better than the generally used ACON ones in term of training convergence speed of the network. Unlike the conventional sequential approach of training the neural networks, the OCON technique may be implemented by training all the classes of the face images simultaneously.
Artificial Learning in Artificial Memories
Venue: arXiv cs.AI 2010
Year: 2010

Memory refinements are designed below to detect those sequences of actions that have been repeated a given number n. Subsequently such sequences are permitted to run without CPU involvement. This mimics human learning. Actions are rehearsed and once learned, they are performed automatically without conscious involvement.
Large scale probabilistic available bandwidth estimation
Venue: arXiv cs.NI 2010
Year: 2010

The common utilization-based definition of available bandwidth and many of the existing tools to estimate it suffer from several important weaknesses: i) most tools report a point estimate of average available bandwidth over a measurement interval and do not provide a confidence interval; ii) the commonly adopted models used to relate the available bandwidth metric to the measured data are invalid in almost all practical scenarios; iii) existing tools do not scale well and are not suited to the task of multi-path estimation in large-scale networks; iv) almost all tools use ad-hoc techniques to address measurement noise; and v) tools do not provide enough flexibility in terms of accuracy, overhead, latency and reliability to adapt to the requirements of various applications. In this paper we propose a new definition for available bandwidth and a novel framework that addresses these issues. We define probabilistic available bandwidth (PAB) as the largest input rate at which we can send a traffic flow along a path while achieving, with specified probability, an output rate that is almost as large as the input rate. PAB is expressed directly in terms of the measurable output rate and includes adjustable parameters that allow the user to adapt to different application requirements. Our probabilistic framework to estimate network-wide probabilistic available bandwidth is based on packet trains, Bayesian inference, factor graphs and active sampling. We deploy our tool on the PlanetLab network and our results show that we can obtain accurate estimates with a much smaller measurement overhead compared to existing approaches.
A Platform for Implementing Secure Wireless Ad Hoc Networks
Venue: arXiv cs.CR 2010
Year: 2010

We propose a new platform for implementing secure wireless ad hoc networks. Our proposal is based on a modular architecture, with the software stack constructed directly on the Ethernet layer. Within our platform we use a new security protocol that we designed to ensure mutual authentication between nodes and a secure key exchange. The correctness of the proposed security protocol is ensured by Guttman's authentication tests.
On the instantaneous frequency of Gaussian stochastic processes
Venue: arXiv cs.IT 2010
Year: 2010

This paper concerns the instantaneous frequency (IF) of continuous-time, zero-mean, complex-valued, proper, mean-square differentiable nonstationary Gaussian stochastic processes. We compute the probability density function for the IF for fixed time, which extends a result known for wide-sense stationary processes to nonstationary processes. For a fixed time the IF has either zero or infinite variance. For harmonizable processes we obtain as a byproduct that the mean of the IF, for fixed time, is the normalized first order frequency moment of the Wigner spectrum.
Learning Read-Once Functions Using Subcube Identity Queries
Venue: arXiv cs.CC 2010
Year: 2010

We consider the problem of exact identification for read-once functions over arbitrary Boolean bases. We introduce a new type of queries (subcube identity ones), discuss its connection to previously known ones, and study the complexity of the problem in question. Besides these new queries, learning algorithms are allowed to use classic membership ones. We present a technique of modeling an equivalence query with a polynomial number of membership and subcube identity ones, thus establishing (under certain conditions) a polynomial upper bound on the complexity of the problem. We show that in some circumstances, though, equivalence queries cannot be modeled with a polynomial number of subcube identity and membership ones. We construct an example of an infinite Boolean basis with an exponential lower bound on the number of membership and subcube identity queries required for exact identification. We prove that for any finite subset of this basis, the problem remains polynomial.
Collision Codes: Decoding Superimposed BPSK Modulated Wireless Transmissions
Venue: arXiv cs.NI 2010
Year: 2010

The introduction of physical layer network coding gives rise to the concept of turning a collision of transmissions on a wireless channel useful. In the idea of physical layer network coding, two synchronized simultaneous packet transmissions are carefully encoded such that the superimposed transmission can be decoded to produce a packet which is identical to the bitwise binary sum of the two transmitted packets. This paper explores the decoding of superimposed transmission resulted by multiple synchronized simultaneous transmissions. We devise a coding scheme that achieves the identification of individual transmission from the synchronized superimposed transmission. A mathematical proof for the existence of such a coding scheme is given.
Group Based Interference Alignment
Venue: arXiv cs.IT 2010
Year: 2010

In the $K$-user single-input single-output (SISO) frequency-selective fading interference channel, it is shown that the maximal achievable multiplexing gain is almost surely $K/2$ by using interference alignment (IA). However, when the signaling dimensions are limited, allocating all the resources to all users simultaneously is not optimal. So, a group based interference alignment (GIA) scheme is proposed, and it is formulated as an unbounded knapsack problem. Optimal and greedy search algorithms are proposed to obtain group patterns. Analysis and numerical results show that the GIA scheme can obtain a higher multiplexing gain when the resources are limited.
Prime Factor Cyclotomic Fourier Transforms with Reduced Complexity over Finite Fields
Venue: arXiv cs.IT 2010
Year: 2010

Discrete Fourier transforms~(DFTs) over finite fields have widespread applications in error correction coding. Hence, reducing the computational complexities of DFTs is of great significance, especially for long DFTs as increasingly longer error control codes are chosen for digital communication and storage systems. Since DFTs involve both multiplications and additions over finite fields and multiplications are much more complex than additions, recently proposed cyclotomic fast Fourier transforms (CFFTs) are promising due to their low multiplicative complexity. Unfortunately, they have very high additive complexity. Techniques such as common subexpression elimination (CSE) can be used to reduce the additive complexity of CFFTs, but their effectiveness for long DFTs is limited by their complexity. In this paper, we propose prime factor cyclotomic Fourier transforms (PFCFTs), which use CFFTs as sub-DFTs via the prime factor algorithm. When the length of DFTs is prime, our PFCFTs reduce to CFFTs. When the length has co-prime factors, since the sub-DFTs have much shorter lengths, this allows us to use CSE to significantly reduce their additive complexity. In comparison to previously proposed fast Fourier transforms, our PFCFTs achieve reduced overall complexity when the length of DFTs is at least 255, and the improvement significantly increases as the length grows. This approach also enables us to propose efficient DFTs with very long length (e.g., 4095-point), first efficient DFTs of such lengths in the literature. Finally, our PFCFTs are also advantageous for hardware implementation due to their regular structure.
Improved RANSAC performance using simple, iterative minimal-set solvers
Venue: arXiv cs.CV 2010
Year: 2010

RANSAC is a popular technique for estimating model parameters in the presence of outliers. The best speed is achieved when the minimum possible number of points is used to estimate hypotheses for the model. Many useful problems can be represented using polynomial constraints (for instance, the determinant of a fundamental matrix must be zero) and so have a number of solutions which are consistent with a minimal set. A considerable amount of effort has been expended on finding the constraints of such problems, and these often require the solution of systems of polynomial equations. We show that better performance can be achieved by using a simple optimization based approach on minimal sets. For a given minimal set, the optimization approach is not guaranteed to converge to the correct solution. However, when used within RANSAC the greater speed and numerical stability results in better performance overall, and much simpler algorithms. We also show that by selecting more than the minimal number of points and using robust optimization can yield better results for very noisy by reducing the number of trials required. The increased speed of our method demonstrated with experiments on essential matrix estimation.
Can Random Coin Flips Speed Up a Computer?
Venue: arXiv cs.CC 2010
Year: 2010

This expository essay introduces randomness and computation to a lay audience.