OpenRaiser/Intern-Atlas huggingface dataset:
Self-Interference Cancellation in Multi-hop Full-Duplex Networks via Structured Signaling
Venue: arXiv cs.IT 2011
Year: 2011

This paper discusses transmission strategies for dealing with the problem of self-interference in multi-hop wireless networks in which the nodes communicate in a full- duplex mode. An information theoretic study of the simplest such multi-hop network: the two-hop source-relay-destination network, leads to a novel transmission strategy called structured self-interference cancellation (or just "structured cancellation" for short). In the structured cancellation strategy the source restrains from transmitting on certain signal levels, and the relay structures its transmit signal such that it can learn the residual self-interference channel, and undo the self-interference, by observing the portion of its own transmit signal that appears at the signal levels left empty by the source. It is shown that in certain nontrivial regimes, the structured cancellation strategy outperforms not only half-duplex but also full-duplex schemes in which time-orthogonal training is used for estimating the residual self-interference channel.
Generating Loop Invariants by Computing Vanishing Ideals of Sample Points
Venue: arXiv cs.SC 2011
Year: 2011

Loop invariants play a very important role in proving correctness of programs. In this paper, we address the problem of generating invariants of polynomial loop programs. We present a new approach, for generating polynomial equation invariants of polynomial loop programs through computing vanishing ideals of sample points. We apply rational function interpolation, based on early termination technique, to generate invariants of loop programs with symbolic initial values. Our approach avoids first-order quantifier elimination and cylindrical algebraic decomposition(CAD). An algorithm for generating polynomial invariants is proposed and some examples are given to illustrate the algorithm. Furthermore, we demonstrate on a set of loop programs with symbolic initial values that our algorithm can yield polynomial invariants with degrees high up to 15.
Multidimensional Balanced Allocation for Multiple Choice & (1 + Beta) Processes
Venue: arXiv cs.DS 2011
Year: 2011

Allocation of balls into bins is a well studied abstraction for load balancing problems.The literature hosts numerous results for sequential(single dimensional) allocation case when m balls are thrown into n bins. In this paper we study the symmetric multiple choice process for both unweighted and weighted balls as well as for both multidimensional and scalar models.Additionally,we present the results on bounds on gap for (1+beta) choice process with multidimensional balls and bins. We show that for the symmetric d choice process and with m=O(n), the upper bound on the gap is O(lnln(n)) w.h.p.This upper bound on the gap is within D=f factor of the lower bound. This is the first such tight result.For the general case of m>>n the expected gap is bounded by O(lnln(n)).For variable f and non-uniform distribution of the populated dimensions,we obtain the upper bound on the expected gap as O(log(n)). Further,for the multiple round parallel balls and bins,we show that the gap is also bounded by O(loglog(n)) for m=O(n).The same bound holds for the expected gap when m>>n. Our analysis also has strong implications in the sequential scalar case.For the weighted balls and bins and general case m>>n,we show that the upper bound on the expected gap is O(log(n)) which improves upon the best prior bound of n^c.Moreover,we show that for the (1 + beta) choice process and m=O(n) the upper bound(assuming uniform distribution of f populated dimensions over D total dimensions) on the gap is O(log(n)/beta),which is within D=f factor of the lower bound.For fixed f with non-uniform distribution and for random f with Binomial distribution the expected gap remains O(log(n)/beta) independent of the total number of balls thrown. This is the first such tight result for (1 +beta) paradigm with multidimensional balls and bins.
Perfectly Balanced Allocation With Estimated Average Using Expected Constant Retries
Venue: arXiv cs.DS 2011
Year: 2011

Balanced allocation of online balls-into-bins has long been an active area of research for efficient load balancing and hashing applications.There exists a large number of results in this domain for different settings, such as parallel allocations~\cite{parallel}, multi-dimensional allocations~\cite{multi}, weighted balls~\cite{weight} etc. For sequential multi-choice allocation, where $m$ balls are thrown into $n$ bins with each ball choosing $d$ (constant) bins independently uniformly at random, the maximum load of a bin is $O(\log \log n) + m/n$ with high probability~\cite{heavily_load}. This offers the current best known allocation scheme. However, for $d = Θ(\log n)$, the gap reduces to $O(1)$~\cite{soda08}.A similar constant gap bound has been established for parallel allocations with $O(\log ^*n)$ communication rounds~\cite{lenzen}. In this paper we propose a novel multi-choice allocation algorithm, \emph{Improved D-choice with Estimated Average} ($IDEA$) achieving a constant gap with a high probability for the sequential single-dimensional online allocation problem with constant $d$. We achieve a maximum load of $\lceil m/n \rceil$ with high probability for constant $d$ choice scheme with \emph{expected} constant number of retries or rounds per ball. We also show that the bound holds even for an arbitrary large number of balls, $m>>n$. Further, we generalize this result to (i)~the weighted case, where balls have weights drawn from an arbitrary weight distribution with finite variance, (ii)~multi-dimensional setting, where balls have $D$ dimensions with $f$ randomly and uniformly chosen filled dimension for $m=n$, and (iii)~the parallel case, where $n$ balls arrive and are placed parallely in the bins. We show that the gap in these case is also a constant w.h.p. (independent of $m$) for constant value of $d$ with expected constant number of retries per ball.
Collective Energy Foraging of Robot Swarms and Robot Organisms
Venue: arXiv cs.RO 2011
Year: 2011

Cooperation and competition among stand-alone swarm agents increase collective fitness of the whole system. A principally new kind of collective systems is demonstrated by some bacteria and fungi, when they build symbiotic organisms. Symbiotic life forms emerge new functional and self-developmental capabilities, which allow better survival of swarm agents in different environments. In this paper we consider energy foraging scenario for two robotic species, swarm robots and symbiotic robot organism. It is indicated that aggregation of microrobots into a robot organism can provide better functional fitness for the whole group. A prototype of microrobots capable of autonomous aggregation and disaggregation are shown.
Using Neighborhood Beyond One Hop in Disruption-Tolerant Networks
Venue: arXiv cs.NI 2011
Year: 2011

Most disruption-tolerant networking (DTN) protocols available in the literature have focused on mere contact and intercontact characteristics to make forwarding decisions. Nevertheless, there is a world behind contacts: just because one node is not in contact with some potential destination, it does not mean that this node is alone. There may be interesting end-to-end transmission opportunities through other nearby nodes. Existing protocols miss such possibilities by maintaining a simple contact-based view of the network. In this paper, we investigate how the vicinity of a node evolves through time and whether such information can be useful when routing data. We observe a clear tradeoff between routing performance and the cost for monitoring the neighborhood. Our analyses suggest that limiting a node's neighborhood view to three or four hops is more than enough to significantly improve forwarding efficiency without incurring prohibitive overhead.
Context-Bounded Analysis For Concurrent Programs With Dynamic Creation of Threads
Venue: arXiv cs.LO 2011
Year: 2011

Context-bounded analysis has been shown to be both efficient and effective at finding bugs in concurrent programs. According to its original definition, context-bounded analysis explores all behaviors of a concurrent program up to some fixed number of context switches between threads. This definition is inadequate for programs that create threads dynamically because bounding the number of context switches in a computation also bounds the number of threads involved in the computation. In this paper, we propose a more general definition of context-bounded analysis useful for programs with dynamic thread creation. The idea is to bound the number of context switches for each thread instead of bounding the number of switches of all threads. We consider several variants based on this new definition, and we establish decidability and complexity results for the analysis induced by them.
Tight Bounds on Proper Equivalence Query Learning of DNF
Venue: arXiv cs.LG 2011
Year: 2011

We prove a new structural lemma for partial Boolean functions $f$, which we call the seed lemma for DNF. Using the lemma, we give the first subexponential algorithm for proper learning of DNF in Angluin's Equivalence Query (EQ) model. The algorithm has time and query complexity $2^{(\tilde{O}{\sqrt{n}})}$, which is optimal. We also give a new result on certificates for DNF-size, a simple algorithm for properly PAC-learning DNF, and new results on EQ-learning $\log n$-term DNF and decision trees.
Domain decomposition and locality optimization for large-scale lattice Boltzmann simulations
Venue: arXiv cs.DC 2011
Year: 2011

We present a simple, parallel and distributed algorithm for setting up and partitioning a sparse representation of a regular discretized simulation domain. This method is scalable for a large number of processes even for complex geometries and ensures load balance between the domains, reasonable communication interfaces, and good data locality within the domain. Applying this scheme to a list-based lattice Boltzmann flow solver can achieve similar or even higher flow solver performance than widely used standard graph partition based tools such as METIS and PT-SCOTCH.
A Casual Tour Around a Circuit Complexity Bound
Venue: arXiv cs.CC 2011
Year: 2011

I will discuss the recent proof that the complexity class NEXP (nondeterministic exponential time) lacks nonuniform ACC circuits of polynomial size. The proof will be described from the perspective of someone trying to discover it.
Improving the Thresholds of Sparse Recovery: An Analysis of a Two-Step Reweighted Basis Pursuit Algorithm
Venue: arXiv cs.IT 2011
Year: 2011

It is well known that $\ell_1$ minimization can be used to recover sufficiently sparse unknown signals from compressed linear measurements. In fact, exact thresholds on the sparsity, as a function of the ratio between the system dimensions, so that with high probability almost all sparse signals can be recovered from i.i.d. Gaussian measurements, have been computed and are referred to as "weak thresholds" \cite{D}. In this paper, we introduce a reweighted $\ell_1$ recovery algorithm composed of two steps: a standard $\ell_1$ minimization step to identify a set of entries where the signal is likely to reside, and a weighted $\ell_1$ minimization step where entries outside this set are penalized. For signals where the non-sparse component entries are independent and identically drawn from certain classes of distributions, (including most well known continuous distributions), we prove a \emph{strict} improvement in the weak recovery threshold. Our analysis suggests that the level of improvement in the weak threshold depends on the behavior of the distribution at the origin. Numerical simulations verify the distribution dependence of the threshold improvement very well, and suggest that in the case of i.i.d. Gaussian nonzero entries, the improvement can be quite impressive---over 20% in the example we consider.
Breaking a chaotic image encryption algorithm based on perceptron model
Venue: arXiv cs.CR 2011
Year: 2011

Recently, a chaotic image encryption algorithm based on perceptron model was proposed. The present paper analyzes security of the algorithm and finds that the equivalent secret key can be reconstructed with only one pair of known-plaintext/ciphertext, which is supported by both mathematical proof and experiment results. In addition, some other security defects are also reported.
Face Recognition Using Discrete Cosine Transform for Global and Local Features
Venue: arXiv cs.CV 2011
Year: 2011

Face Recognition using Discrete Cosine Transform (DCT) for Local and Global Features involves recognizing the corresponding face image from the database. The face image obtained from the user is cropped such that only the frontal face image is extracted, eliminating the background. The image is restricted to a size of 128 x 128 pixels. All images in the database are gray level images. DCT is applied to the entire image. This gives DCT coefficients, which are global features. Local features such as eyes, nose and mouth are also extracted and DCT is applied to these features. Depending upon the recognition rate obtained for each feature, they are given weightage and then combined. Both local and global features are used for comparison. By comparing the ranks for global and local features, the false acceptance rate for DCT can be minimized.
Multimodal diff-hash
Venue: arXiv cs.CV 2011
Year: 2011

Many applications require comparing multimodal data with different structure and dimensionality that cannot be compared directly. Recently, there has been increasing interest in methods for learning and efficiently representing such multimodal similarity. In this paper, we present a simple algorithm for multimodal similarity-preserving hashing, trying to map multimodal data into the Hamming space while preserving the intra- and inter-modal similarities. We show that our method significantly outperforms the state-of-the-art method in the field.
A Survey on Distance Vector Routing Protocols
Venue: arXiv cs.NI 2011
Year: 2011

In this paper we give a brief introduction to five different distance vector routing protocols (RIP, AODV, EIGRP, RIP-MTI and Babel) and give some of our thoughts on how to solve the count to infinity problem. Our focus is how distance vector routing protocols, based on limited information, can prevent routing loops and the count to infinity problem.
Iris Recognition Based on LBP and Combined LVQ Classifier
Venue: arXiv cs.CV 2011
Year: 2011

Iris recognition is considered as one of the best biometric methods used for human identification and verification, this is because of its unique features that differ from one person to another, and its importance in the security field. This paper proposes an algorithm for iris recognition and classification using a system based on Local Binary Pattern and histogram properties as a statistical approaches for feature extraction, and Combined Learning Vector Quantization Classifier as Neural Network approach for classification, in order to build a hybrid model depends on both features. The localization and segmentation techniques are presented using both Canny edge detection and Hough Circular Transform in order to isolate an iris from the whole eye image and for noise detection .Feature vectors results from LBP is applied to a Combined LVQ classifier with different classes to determine the minimum acceptable performance, and the result is based on majority voting among several LVQ classifier. Different iris datasets CASIA, MMU1, MMU2, and LEI with different extensions and size are presented. Since LBP is working on a grayscale level so colored iris images should be transformed into a grayscale level. The proposed system gives a high recognition rate 99.87 % on different iris datasets compared with other methods.
Efficient Hierarchical Markov Random Fields for Object Detection on a Mobile Robot
Venue: arXiv cs.CV 2011
Year: 2011

Object detection and classification using video is necessary for intelligent planning and navigation on a mobile robot. However, current methods can be too slow or not sufficient for distinguishing multiple classes. Techniques that rely on binary (foreground/background) labels incorrectly identify areas with multiple overlapping objects as single segment. We propose two Hierarchical Markov Random Field models in efforts to distinguish connected objects using tiered, binary label sets. Near-realtime performance has been achieved using efficient optimization methods which runs up to 11 frames per second on a dual core 2.2 Ghz processor. Evaluation of both models is done using footage taken from a robot obstacle course at the 2010 Intelligent Ground Vehicle Competition.
Solar Power Systems Web Monitoring
Venue: arXiv cs.OH 2011
Year: 2011

All over the world the peak demand load is increasing and the load factor is decreasing year-by-year. The fossil fuel is considered insufficient thus solar energy systems are becoming more and more useful, not only in terms of installation but monitoring of these systems is very crucial. Monitoring becomes very important when there are a large number of solar panels. Monitoring would allow early detection if the output falls below required level or one of the solar panel out of 1000 goes down. In this study the target is to monitor and control a developed solar panel by using available internet foundation. This web-enabled software will provide more flexibility over the system such as transmitting data from panel to the host computer and disseminating information to relevant stake holders barring any geographical barrier. The software would be built around web server with dynamic HTML and JAVA, this paper presents the preliminary design of the proposed system.
Sentiment Analysis of Document Based on Annotation
Venue: arXiv cs.IR 2011
Year: 2011

I present a tool which tells the quality of document or its usefulness based on annotations. Annotation may include comments, notes, observation, highlights, underline, explanation, question or help etc. comments are used for evaluative purpose while others are used for summarization or for expansion also. Further these comments may be on another annotation. Such annotations are referred as meta-annotation. All annotation may not get equal weightage. My tool considered highlights, underline as well as comments to infer the collective sentiment of annotators. Collective sentiments of annotators are classified as positive, negative, objectivity. My tool computes collective sentiment of annotations in two manners. It counts all the annotation present on the documents as well as it also computes sentiment scores of all annotation which includes comments to obtain the collective sentiments about the document or to judge the quality of document. I demonstrate the use of tool on research paper.
IT Security Plan for Flight Simulation Program
Venue: arXiv cs.CR 2011
Year: 2011

Information security is one of the most important aspects of technology, we cannot protect the best interests of our organizations' assets (be that personnel, data, or other resources), without ensuring that these assetsare protected to the best of their ability. Within the Defense Department, this is vital to the security of not just those assets but also the national security of the United States. Compromise insecurity could lead severe consequences. However, technology changes so rapidly that change has to be made to reflect these changes with security in mind. This article outlines a growing technological change (virtualization and cloud computing), and how to properly address IT security concerns within an operating environment. By leveraging a series of encrypted physical and virtual systems, andnetwork isolation measures, this paper delivered a secured high performance computing environment that efficiently utilized computing resources, reduced overall computer processing costs, and ensures confidentiality, integrity, and availability of systems within the operating environment.
Reliability of Mobile Agents for Reliable Service Discovery Protocol in MANET
Venue: arXiv cs.NI 2011
Year: 2011

Recently mobile agents are used to discover services in mobile ad-hoc network (MANET) where agents travel through the network, collecting and sometimes spreading the dynamically changing service information. But it is important to investigate how reliable the agents are for this application as the dependability issues(reliability and availability) of MANET are highly affected by its dynamic nature.The complexity of underlying MANET makes it hard to obtain the route reliability of the mobile agent systems (MAS); instead we estimate it using Monte Carlo simulation. Thus an algorithm for estimating the task route reliability of MAS (deployed for discovering services) is proposed, that takes into account the effect of node mobility in MANET. That mobility pattern of the nodes affects the MAS performance is also shown by considering different mobility models. Multipath propagation effect of radio signal is considered to decide link existence. Transient link errors are also considered. Finally we propose a metric to calculate the reliability of service discovery protocol and see how MAS performance affects the protocol reliability. The experimental results show the robustness of the proposed algorithm. Here the optimum value of network bandwidth (needed to support the agents) is calculated for our application. However the reliability of MAS is highly dependent on link failure probability.
A criterion of simultaneously symmetrization and spectral finiteness for a finite set of real 2-by-2 matrices
Venue: arXiv cs.SY 2011
Year: 2011

In this paper, we consider the simultaneously symmetrization and spectral finiteness for a finite set of real 2-by-2 matrices.
Generic Multiplicative Methods for Implementing Machine Learning Algorithms on MapReduce
Venue: arXiv cs.DS 2011
Year: 2011

In this paper we introduce a generic model for multiplicative algorithms which is suitable for the MapReduce parallel programming paradigm. We implement three typical machine learning algorithms to demonstrate how similarity comparison, gradient descent, power method and other classic learning techniques fit this model well. Two versions of large-scale matrix multiplication are discussed in this paper, and different methods are developed for both cases with regard to their unique computational characteristics and problem settings. In contrast to earlier research, we focus on fundamental linear algebra techniques that establish a generic approach for a range of algorithms, rather than specific ways of scaling up algorithms one at a time. Experiments show promising results when evaluated on both speedup and accuracy. Compared with a standard implementation with computational complexity $O(m^3)$ in the worst case, the large-scale matrix multiplication experiments prove our design is considerably more efficient and maintains a good speedup as the number of cores increases. Algorithm-specific experiments also produce encouraging results on runtime performance.