OpenRaiser/Intern-Atlas huggingface dataset:
Gröbner Bases of Bihomogeneous Ideals generated by Polynomials of Bidegree (1,1): Algorithms and Complexity
Venue: arXiv cs.SC 2010
Year: 2010

Solving multihomogeneous systems, as a wide range of structured algebraic systems occurring frequently in practical problems, is of first importance. Experimentally, solving these systems with Gröbner bases algorithms seems to be easier than solving homogeneous systems of the same degree. Nevertheless, the reasons of this behaviour are not clear. In this paper, we focus on bilinear systems (i.e. bihomogeneous systems where all equations have bidegree (1,1)). Our goal is to provide a theoretical explanation of the aforementionned experimental behaviour and to propose new techniques to speed up the Gröbner basis computations by using the multihomogeneous structure of those systems. The contributions are theoretical and practical. First, we adapt the classical F5 criterion to avoid reductions to zero which occur when the input is a set of bilinear polynomials. We also prove an explicit form of the Hilbert series of bihomogeneous ideals generated by generic bilinear polynomials and give a new upper bound on the degree of regularity of generic affine bilinear systems. This leads to new complexity bounds for solving bilinear systems. We propose also a variant of the F5 Algorithm dedicated to multihomogeneous systems which exploits a structural property of the Macaulay matrix which occurs on such inputs. Experimental results show that this variant requires less time and memory than the classical homogeneous F5 Algorithm.
Ant Colony Algorithm for the Weighted Item Layout Optimization Problem
Venue: arXiv cs.NE 2010
Year: 2010

This paper discusses the problem of placing weighted items in a circular container in two-dimensional space. This problem is of great practical significance in various mechanical engineering domains, such as the design of communication satellites. Two constructive heuristics are proposed, one for packing circular items and the other for packing rectangular items. These work by first optimizing object placement order, and then optimizing object positioning. Based on these heuristics, an ant colony optimization (ACO) algorithm is described to search first for optimal positioning order, and then for the optimal layout. We describe the results of numerical experiments, in which we test two versions of our ACO algorithm alongside local search methods previously described in the literature. Our results show that the constructive heuristic-based ACO performs better than existing methods on larger problem instances.
The tropical double description method
Venue: arXiv cs.CG 2010
Year: 2010

We develop a tropical analogue of the classical double description method allowing one to compute an internal representation (in terms of vertices) of a polyhedron defined externally (by inequalities). The heart of the tropical algorithm is a characterization of the extreme points of a polyhedron in terms of a system of constraints which define it. We show that checking the extremality of a point reduces to checking whether there is only one minimal strongly connected component in an hypergraph. The latter problem can be solved in almost linear time, which allows us to eliminate quickly redundant generators. We report extensive tests (including benchmarks from an application to static analysis) showing that the method outperforms experimentally the previous ones by orders of magnitude. The present tools also lead to worst case bounds which improve the ones provided by previous methods.
Distributed Control of the Laplacian Spectral Moments of a Network
Venue: arXiv cs.MA 2010
Year: 2010

It is well-known that the eigenvalue spectrum of the Laplacian matrix of a network contains valuable information about the network structure and the behavior of many dynamical processes run on it. In this paper, we propose a fully decentralized algorithm that iteratively modifies the structure of a network of agents in order to control the moments of the Laplacian eigenvalue spectrum. Although the individual agents have knowledge of their local network structure only (i.e., myopic information), they are collectively able to aggregate this local information and decide on what links are most beneficial to be added or removed at each time step. Our approach relies on gossip algorithms to distributively compute the spectral moments of the Laplacian matrix, as well as ensure network connectivity in the presence of link deletions. We illustrate our approach in nontrivial computer simulations and show that a good final approximation of the spectral moments of the target Laplacian matrix is achieved for many cases of interest.
Detection and Demarcation of Tumor using Vector Quantization in MRI images
Venue: arXiv cs.CV 2010
Year: 2010

Segmenting a MRI images into homogeneous texture regions representing disparate tissue types is often a useful preprocessing step in the computer-assisted detection of breast cancer. That is why we proposed new algorithm to detect cancer in mammogram breast cancer images. In this paper we proposed segmentation using vector quantization technique. Here we used Linde Buzo-Gray algorithm (LBG) for segmentation of MRI images. Initially a codebook of size 128 was generated for MRI images. These code vectors were further clustered in 8 clusters using same LBG algorithm. These 8 images were displayed as a result. This approach does not leads to over segmentation or under segmentation. For the comparison purpose we displayed results of watershed segmentation and Entropy using Gray Level Co-occurrence Matrix along with this method.
Speech Recognition of the letter 'zha' in Tamil Language using HMM
Venue: arXiv cs.SD 2010
Year: 2010

Speech signals of the letter 'zha' in Tamil language of 3 males and 3 females were coded using an improved version of Linear Predictive Coding (LPC). The sampling frequency was at 16 kHz and the bit rate was at 15450 bits per second, where the original bit rate was at 128000 bits per second with the help of wave surfer audio tool. The output LPC cepstrum is implemented in first order three state Hidden Markov Model(HMM) chain.
Comparative Study of Protocols Used for Establishing VPN
Venue: arXiv cs.NI 2010
Year: 2010

This is an Internet era. Most of the organizations try to establish their development centers and branch offices across the World. Employees working from their homes are also becoming very popular and organizations benefit financially by utilizing less office space, and reducing total expenses incurred by having office workers on site. To meet such requirements organizations develop a need to communicate with these offices over highly secure, confidential and reliable connections regardless of the location of the office. Here the VPN plays a vital role in establishing a distributed business model.
Improved Approximation for Guarding Simple Galleries from the Perimeter
Venue: arXiv cs.CG 2010
Year: 2010

We provide an O(log log OPT)-approximation algorithm for the problem of guarding a simple polygon with guards on the perimeter. We first design a polynomial-time algorithm for building epsilon-nets of size O(1/epsilon log log 1/epsilon) for the instances of Hitting Set associated with our guarding problem. We then apply the technique of Bronnimann and Goodrich to build an approximation algorithm from this epsilon-net finder. Along with a simple polygon P, our algorithm takes as input a finite set of potential guard locations that must include the polygon's vertices. If a finite set of potential guard locations is not specified, e.g. when guards may be placed anywhere on the perimeter, we use a known discretization technique at the cost of making the algorithm's running time potentially linear in the ratio between the longest and shortest distances between vertices. Our algorithm is the first to improve upon O(log OPT)-approximation algorithms that use generic net finders for set systems of finite VC-dimension.
Multi-camera Realtime 3D Tracking of Multiple Flying Animals
Venue: arXiv cs.CV 2010
Year: 2010

Automated tracking of animal movement allows analyses that would not otherwise be possible by providing great quantities of data. The additional capability of tracking in realtime - with minimal latency - opens up the experimental possibility of manipulating sensory feedback, thus allowing detailed explorations of the neural basis for control of behavior. Here we describe a new system capable of tracking the position and body orientation of animals such as flies and birds. The system operates with less than 40 msec latency and can track multiple animals simultaneously. To achieve these results, a multi target tracking algorithm was developed based on the Extended Kalman Filter and the Nearest Neighbor Standard Filter data association algorithm. In one implementation, an eleven camera system is capable of tracking three flies simultaneously at 60 frames per second using a gigabit network of nine standard Intel Pentium 4 and Core 2 Duo computers. This manuscript presents the rationale and details of the algorithms employed and shows three implementations of the system. An experiment was performed using the tracking system to measure the effect of visual contrast on the flight speed of Drosophila melanogaster. At low contrasts, speed is more variable and faster on average than at high contrasts. Thus, the system is already a useful tool to study the neurobiology and behavior of freely flying animals. If combined with other techniques, such as `virtual reality'-type computer graphics or genetic manipulation, the tracking system would offer a powerful new way to investigate the biology of flying animals.
Probabilistic Approach to Neural Networks Computation Based on Quantum Probability Model Probabilistic Principal Subspace Analysis Example
Venue: arXiv cs.NE 2010
Year: 2010

In this paper, we introduce elements of probabilistic model that is suitable for modeling of learning algorithms in biologically plausible artificial neural networks framework. Model is based on two of the main concepts in quantum physics - a density matrix and the Born rule. As an example, we will show that proposed probabilistic interpretation is suitable for modeling of on-line learning algorithms for PSA, which are preferably realized by a parallel hardware based on very simple computational units. Proposed concept (model) can be used in the context of improving algorithm convergence speed, learning factor choice, or input signal scale robustness. We are going to see how the Born rule and the Hebbian learning rule are connected
Connected searching of weighted trees
Venue: arXiv cs.DS 2010
Year: 2010

In this paper we consider the problem of connected edge searching of weighted trees. It is shown that there exists a polynomial-time algorithm for finding optimal connected search strategy for bounded degree trees with arbitrary weights on the edges and vertices of the tree. The problem is NP-complete for general node-weighted trees (the weight of each edge is 1).
A New Decoding Scheme for Errorless Codes for Overloaded CDMA with Active User Detection
Venue: arXiv cs.IT 2010
Year: 2010

Recently, a new class of binary codes for overloaded CDMA systems are proposed that not only has the ability of errorless communication but also suitable for detecting active users. These codes are called COWDA [1]. In [1], a Maximum Likelihood (ML) decoder is proposed for this class of codes. Although the proposed scheme of coding/decoding show impressive performance, the decoder can be improved. In this paper by assuming more practical conditions for the traffic in the system, we suggest an algorithm that increases the performance of the decoder several orders of magnitude (the Bit-Error-Rate (BER) is divided by a factor of 400 in some Eb/N0's The algorithm supposes the Poison distribution for the time of activation/deactivation of the users.
The Privacy Coach: Supporting customer privacy in the Internet of Things
Venue: arXiv cs.CY 2010
Year: 2010

The Privacy Coach is an application running on a mobile phone that supports customers in making privacy decisions when confronted with RFID tags. The approach we take to increase customer privacy is a radical departure from the mainstream research efforts that focus on implementing privacy enhancing technologies on the RFID tags themselves. Instead the Privacy Coach functions as a mediator between customer privacy preferences and corporate privacy policies, trying to find a match between the two, and informing the user of the outcome. In this paper we report on the architecture of the Privacy Coach, and show how it enables users to make informed privacy decisions in a user-friendly manner. We also spend considerable time to discuss lessons learnt and to describe future plans to further improve on the Privacy Coach concept.
Communication in a Poisson Field of Interferers -- Part II: Channel Capacity and Interference Spectrum
Venue: arXiv cs.IT 2010
Year: 2010

In Part I of this paper, we presented a mathematical model for communication subject to both network interference and noise, where the interferers are scattered according to a spatial Poisson process, and are operating asynchronously in a wireless environment subject to path loss, shadowing, and multipath fading. We determined the distribution of the aggregate interference and the error performance of the link. In this second part, we characterize the capacity of the link subject to both network interference and noise. Then, we put forth the concept of spectral outage probability (SOP), a new characterization of the aggregate radio-frequency emission generated by communicating nodes in a wireless network. We present some applications of the SOP, namely the establishment of spectral regulations and the design of covert military networks. The proposed framework captures all the essential physical parameters that affect the aggregate network emission, yet is simple enough to provide insights that may be of value in the design and deployment of wireless networks.
Is Space a Stronger Resource than Time? Positive Answer for the Nondeterministic at-Least-Quadratic Time Case
Venue: arXiv cs.CC 2010
Year: 2010

We show that all languages accepted in time f(n) >= n^2 can be accepted in space O(f(n)^{1/2})_and_ in time O(f(n)). The proof is carried out by simulation, based on the idea of guessing the sequences of internal states of the simulated TM when entering certain critical cells, whose location is also guessed. Our method cannot be generalised easily to many-tapes TMs, and in no case can it be relativised.
m-sophistication
Venue: arXiv cs.CC 2010
Year: 2010

The m-sophistication of a finite binary string x is introduced as a generalization of some parameter in the proof that complexity of complexity is rare. A probabilistic near sufficient statistic of x is given which length is upper bounded by the m-sophistication of x within small additive terms. This shows that m-sophistication is lower bounded by coarse sophistication and upper bounded by sophistication within small additive terms. It is also shown that m-sophistication and coarse sophistication can not be approximated by an upper or lower semicomputable function, not even within very large error.
An Optimal Family of Exponentially Accurate One-Bit Sigma-Delta Quantization Schemes
Venue: arXiv cs.IT 2010
Year: 2010

Sigma-Delta modulation is a popular method for analog-to-digital conversion of bandlimited signals that employs coarse quantization coupled with oversampling. The standard mathematical model for the error analysis of the method measures the performance of a given scheme by the rate at which the associated reconstruction error decays as a function of the oversampling ratio $λ$. It was recently shown that exponential accuracy of the form $O(2^{-rλ})$ can be achieved by appropriate one-bit Sigma-Delta modulation schemes. By general information-entropy arguments $r$ must be less than 1. The current best known value for $r$ is approximately 0.088. The schemes that were designed to achieve this accuracy employ the "greedy" quantization rule coupled with feedback filters that fall into a class we call "minimally supported". In this paper, we study the minimization problem that corresponds to optimizing the error decay rate for this class of feedback filters. We solve a relaxed version of this problem exactly and provide explicit asymptotics of the solutions. From these relaxed solutions, we find asymptotically optimal solutions of the original problem, which improve the best known exponential error decay rate to $r \approx 0.102$. Our method draws from the theory of orthogonal polynomials; in particular, it relates the optimal filters to the zero sets of Chebyshev polynomials of the second kind.
A Matroid Framework for Noncoherent Random Network Communications
Venue: arXiv cs.IT 2010
Year: 2010

Models for noncoherent error control in random linear network coding (RLNC) and store and forward (SAF) have been recently proposed. In this paper, we model different types of random network communications as the transmission of flats of matroids. This novel framework encompasses RLNC and SAF and allows us to introduce a novel protocol, referred to as random affine network coding (RANC), based on affine combinations of packets. Although the models previously proposed for RLNC and SAF only consider error control, using our framework, we first evaluate and compare the performance of different network protocols in the error-free case. We define and determine the rate, average delay, and throughput of such protocols, and we also investigate the possibilities of partial decoding before the entire message is received. We thus show that RANC outperforms RLNC in terms of data rate and throughput thanks to a more efficient encoding of messages into packets. Second, we model the possible alterations of a message by the network as an operator channel, which generalizes the channels proposed for RLNC and SAF. Error control is thus reduced to a coding-theoretic problem on flats of a matroid, where two distinct metrics can be used for error correction. We study the maximum cardinality of codes on flats in general, and codes for error correction in RANC in particular. We finally design a class of nearly optimal codes for RANC based on rank metric codes for which we propose a low-complexity decoding algorithm. The gain of RANC over RLNC is thus preserved with no additional cost in terms of complexity.
MIMO Detection for High-Order QAM Based on a Gaussian Tree Approximation
Venue: arXiv cs.IT 2010
Year: 2010

This paper proposes a new detection algorithm for MIMO communication systems employing high order QAM constellations. The factor graph that corresponds to this problem is very loopy; in fact, it is a complete graph. Hence, a straightforward application of the Belief Propagation (BP) algorithm yields very poor results. Our algorithm is based on an optimal tree approximation of the Gaussian density of the unconstrained linear system. The finite-set constraint is then applied to obtain a loop-free discrete distribution. It is shown that even though the approximation is not directly applied to the exact discrete distribution, applying the BP algorithm to the loop-free factor graph outperforms current methods in terms of both performance and complexity. The improved performance of the proposed algorithm is demonstrated on the problem of MIMO detection.
Perfect Z2Z4-linear codes in Steganography
Venue: arXiv cs.IT 2010
Year: 2010

Steganography is an information hiding application which aims to hide secret data imperceptibly into a commonly used media. Unfortunately, the theoretical hiding asymptotical capacity of steganographic systems is not attained by algorithms developed so far. In this paper, we describe a novel coding method based on Z2Z4-linear codes that conforms to +/-1-steganography, that is secret data is embedded into a cover message by distorting each symbol by one unit at most. This method solves some problems encountered by the most efficient methods known today, based on ternary Hamming codes. Finally, the performance of this new technique is compared with that of the mentioned methods and with the well-known theoretical upper bound.
Enumeration Order Reducibility
Venue: arXiv cs.FL 2010
Year: 2010

In this article we define a new reducibility based on the enumeration orders of r.e. sets.
Constraint solvers: An empirical evaluation of design decisions
Venue: arXiv cs.AI 2010
Year: 2010

This paper presents an evaluation of the design decisions made in four state-of-the-art constraint solvers; Choco, ECLiPSe, Gecode, and Minion. To assess the impact of design decisions, instances of the five problem classes n-Queens, Golomb Ruler, Magic Square, Social Golfers, and Balanced Incomplete Block Design are modelled and solved with each solver. The results of the experiments are not meant to give an indication of the performance of a solver, but rather investigate what influence the choice of algorithms and data structures has. The analysis of the impact of the design decisions focuses on the different ways of memory management, behaviour with increasing problem size, and specialised algorithms for specific types of variables. It also briefly considers other, less significant decisions.
Dendritic Cells for SYN Scan Detection
Venue: arXiv cs.AI 2010
Year: 2010

Artificial immune systems have previously been applied to the problem of intrusion detection. The aim of this research is to develop an intrusion detection system based on the function of Dendritic Cells (DCs). DCs are antigen presenting cells and key to activation of the human immune system, behaviour which has been abstracted to form the Dendritic Cell Algorithm (DCA). In algorithmic terms, individual DCs perform multi-sensor data fusion, asynchronously correlating the the fused data signals with a secondary data stream. Aggregate output of a population of cells, is analysed and forms the basis of an anomaly detection system. In this paper the DCA is applied to the detection of outgoing port scans using TCP SYN packets. Results show that detection can be achieved with the DCA, yet some false positives can be encountered when simultaneously scanning and using other network services. Suggestions are made for using adaptive signals to alleviate this uncovered problem.
A Grey-Box Approach to Automated Mechanism Design
Venue: arXiv cs.GT 2010
Year: 2010

Auctions play an important role in electronic commerce, and have been used to solve problems in distributed computing. Automated approaches to designing effective auction mechanisms are helpful in reducing the burden of traditional game theoretic, analytic approaches and in searching through the large space of possible auction mechanisms. This paper presents an approach to automated mechanism design (AMD) in the domain of double auctions. We describe a novel parametrized space of double auctions, and then introduce an evolutionary search method that searches this space of parameters. The approach evaluates auction mechanisms using the framework of the TAC Market Design Game and relates the performance of the markets in that game to their constituent parts using reinforcement learning. Experiments show that the strongest mechanisms we found using this approach not only win the Market Design Game against known, strong opponents, but also exhibit desirable economic properties when they run in isolation.
Fusion of Multiple Matchers using SVM for Offline Signature Identification
Venue: arXiv cs.CV 2010
Year: 2010

This paper uses Support Vector Machines (SVM) to fuse multiple classifiers for an offline signature system. From the signature images, global and local features are extracted and the signatures are verified with the help of Gaussian empirical rule, Euclidean and Mahalanobis distance based classifiers. SVM is used to fuse matching scores of these matchers. Finally, recognition of query signatures is done by comparing it with all signatures of the database. The proposed system is tested on a signature database contains 5400 offline signatures of 600 individuals and the results are found to be promising.