OpenRaiser/Intern-Atlas huggingface dataset:
Monotone switching networks for directed connectivity are strictly more powerful than certain-knowledge switching networks
Venue: arXiv cs.CC 2011
Year: 2011

L (Logarithmic space) versus NL (Non-deterministic logarithmic space) is one of the great open problems in computational complexity theory. In the paper "Bounds on monotone switching networks for directed connectivity", we separated monotone analogues of L and NL using a model called the switching network model. In particular, by considering inputs consisting of just a path and isolated vertices, we proved that any monotone switching network solving directed connectivity on $N$ vertices must have size at least $N^{Ω(\lg(N))}$ and this bound is tight. If we could show a similar result for general switching networks solving directed connectivity, then this would prove that $L \neq NL$. However, proving lower bounds for general switching networks solving directed connectivity requires proving stronger lower bounds on monotone switching networks for directed connectivity. To work towards this goal, we investigated a different set of inputs which we believed to be hard for monotone switching networks to solve and attempted to prove similar lower size bounds. Instead, we found that this set of inputs is actually easy for monotone switching networks for directed connectivity to solve, yet if we restrict ourselves to certain-knowledge switching networks, which are a simple and intuitive subclass of monotone switching networks for directed connectivity, then these inputs are indeed hard to solve. In this paper, we give this set of inputs, demonstrate a "weird" polynomially-sized monotone switching network for directed connectivity which solves this set of inputs, and prove that no polynomially-sized certain-knowledge switching network can solve this set of inputs, thus proving that monotone switching networks for directed connectivity are strictly more powerful than certain-knowledge switching networks.
Space-Round Tradeoffs for MapReduce Computations
Venue: arXiv cs.DS 2011
Year: 2011

This work explores fundamental modeling and algorithmic issues arising in the well-established MapReduce framework. First, we formally specify a computational model for MapReduce which captures the functional flavor of the paradigm by allowing for a flexible use of parallelism. Indeed, the model diverges from a traditional processor-centric view by featuring parameters which embody only global and local memory constraints, thus favoring a more data-centric view. Second, we apply the model to the fundamental computation task of matrix multiplication presenting upper and lower bounds for both dense and sparse matrix multiplication, which highlight interesting tradeoffs between space and round complexity. Finally, building on the matrix multiplication results, we derive further space-round tradeoffs on matrix inversion and matching.
Design and Implementation of Prosthetic Arm using Gear Motor Control Technique with Appropriate Testing
Venue: arXiv cs.RO 2011
Year: 2011

Any part of the human body replication procedure commences the prosthetic control science. This paper highlights the hardware design technique of a prosthetic arm with implementation of gear motor control aspect. The prosthetic control arm movement has been demonstrated in this paper applying processor programming and with the successful testing of the designed prosthetic model. The architectural design of the prosthetic arm here has been replaced by lighter material instead of heavy metal, as well as the traditional EMG (electro myographic) signal has been replaced by the muscle strain.
Data Integrity and Dynamic Storage Way in Cloud Computing
Venue: arXiv cs.DC 2011
Year: 2011

It is not an easy task to securely maintain all essential data where it has the need in many applications for clients in cloud. To maintain our data in cloud, it may not be fully trustworthy because client doesn't have copy of all stored data. But any authors don't tell us data integrity through its user and CSP level by comparison before and after the data update in cloud. So we have to establish new proposed system for this using our data reading protocol algorithm to check the integrity of data before and after the data insertion in cloud. Here the security of data before and after is checked by client with the help of CSP using our "effective automatic data reading protocol from user as well as cloud level into the cloud" with truthfulness. Also we have proposed the multi-server data comparison algorithm with the calculation of overall data in each update before its outsourced level for server restore access point for future data recovery from cloud data server. Our proposed scheme efficiently checks integrity in efficient manner so that data integrity as well as security can be maintained in all cases by considering drawbacks of existing methods.
Three Tier Encryption Algorithm For Secure File Transfer
Venue: arXiv cs.CR 2011
Year: 2011

This encryption algorithm is mainly designed for having a secure file transfer in the low privilege servers and as well as in a secured environment too. This methodology will be implemented in the data center and other important data transaction sectors of the organisation where the encoding process of the software will be done by the database administrator or system administrators and his trusted clients will have decoding process of the software. This software will not be circulated to the unauthorised customers.
Towards Automated Verification of Web Services
Venue: arXiv cs.LO 2011
Year: 2011

This paper proposes the use of model-checking software technology for the verification of workflows and business processes behaviour based on web services, namely the use of the SPIN model checker. Since the specification of a business process behaviour based on web services can be decomposed into patterns, it is proposed a translation of a well known collection of workflow patterns into PROMELA, the input specification language of SPIN. The use of this translation is illustrated with one business process example, which demonstrates how its translation to a PROMELA model can be useful in the web service specification and verification.
Concurrent Development of Model and Implementation
Venue: arXiv cs.SE 2011
Year: 2011

This paper considers how a formal mathematically-based model can be used in support of evolutionary software development, and in particular how such a model can be kept consistent with the implementation as it changes to meet new requirements. A number of techniques are listed can make use of such a model to enhance the development process, and also ways to keep model and implementation consistent. The effectiveness of these techniques is investigated through two case studies concerning the development of small e-business applications, a travel agent and a mortgage broker. Some successes are reported, notably in the use of rapid throwaway modelling to investigate design alternatives, and also in the use of close team working and modelbased trace-checking to maintain synchronisation between model and implementation throughout the development. The main areas of weakness were seen to derive from deficiencies in tool support. Recommendations are therefore made for future improvements to tools supporting formal models which would, in principle, make this co-evolutionary approach attractive to industrial software developers. It is claimed that in fact tools already exist that provide the desired facilities, but these are not necessarily production-quality, and do not all support the same notations, and hence cannot be used together.
On Compress-Forward without Wyner-Ziv Binning for Relay Networks
Venue: arXiv cs.IT 2011
Year: 2011

Noisy network coding is recently proposed for the general multi-source network by Lim, Kim, El Gamal and Chung. This scheme builds on compress-forward (CF) relaying but involves three new ideas, namely no Wyner-Ziv binning, relaxed simultaneous decoding and message repetition. In this paper, using the two-way relay channel as the underlining example, we analyze the impact of each of these ideas on the achievable rate region of relay networks. First, CF without binning but with joint decoding of both the message and compression index can achieve a larger rate region than the original CF scheme for multi-destination relay networks. With binning and successive decoding, the compression rate at each relay is constrained by the weakest link from the relay to a destination; but without binning, this constraint is relaxed. Second, simultaneous decoding of all messages over all blocks without uniquely decoding the compression indices can remove the constraints on compression rate completely, but is still subject to the message block boundary effect. Third, message repetition is necessary to overcome this boundary effect and achieve the noisy network coding region for multi-source networks. The rate region is enlarged with increasing repetition times. We also apply CF without binning specifically to the one-way and two-way relay channels and analyze the rate regions in detail. For the one-way relay channel, it achieves the same rate as the original CF and noisy network coding but has only 1 block decoding delay. For the two-way relay channel, we derive the explicit channel conditions in the Gaussian and fading cases for CF without binning to achieve the same rate region or sum rate as noisy network coding. These analyses may be appealing to practical implementation because of the shorter encoding and decoding delay in CF without binning.
Principles of Distributed Data Management in 2020?
Venue: arXiv cs.DB 2011
Year: 2011

With the advents of high-speed networks, fast commodity hardware, and the web, distributed data sources have become ubiquitous. The third edition of the Özsu-Valduriez textbook Principles of Distributed Database Systems [10] reflects the evolution of distributed data management and distributed database systems. In this new edition, the fundamental principles of distributed data management could be still presented based on the three dimensions of earlier editions: distribution, heterogeneity and autonomy of the data sources. In retrospect, the focus on fundamental principles and generic techniques has been useful not only to understand and teach the material, but also to enable an infinite number of variations. The primary application of these generic techniques has been obviously for distributed and parallel DBMS versions. Today, to support the requirements of important data-intensive applications (e.g. social networks, web data analytics, scientific applications, etc.), new distributed data management techniques and systems (e.g. MapReduce, Hadoop, SciDB, Peanut, Pig latin, etc.) are emerging and receiving much attention from the research community. Although they do well in terms of consistency/flexibility/performance trade-offs for specific applications, they seem to be ad-hoc and might hurt data interoperability. The key questions I discuss are: What are the fundamental principles behind the emerging solutions? Is there any generic architectural model, to explain those principles? Do we need new foundations to look at data distribution?
Spatio-Temporal Analysis of Topic Popularity in Twitter
Venue: arXiv cs.SI 2011
Year: 2011

We present the first comprehensive characterization of the diffusion of ideas on Twitter, studying more than 4000 topics that include both popular and less popular topics. On a data set containing approximately 10 million users and a comprehensive scraping of all the tweets posted by these users between June 2009 and August 2009 (approximately 200 million tweets), we perform a rigorous temporal and spatial analysis, investigating the time-evolving properties of the subgraphs formed by the users discussing each topic. We focus on two different notions of the spatial: the network topology formed by follower-following links on Twitter, and the geospatial location of the users. We investigate the effect of initiators on the popularity of topics and find that users with a high number of followers have a strong impact on popularity. We deduce that topics become popular when disjoint clusters of users discussing them begin to merge and form one giant component that grows to cover a significant fraction of the network. Our geospatial analysis shows that highly popular topics are those that cross regional boundaries aggressively.
Application of PSO, Artificial Bee Colony and Bacterial Foraging Optimization algorithms to economic load dispatch: An analysis
Venue: arXiv cs.NE 2011
Year: 2011

This paper illustrates successful implementation of three evolutionary algorithms, namely- Particle Swarm Optimization(PSO), Artificial Bee Colony (ABC) and Bacterial Foraging Optimization (BFO) algorithms to economic load dispatch problem (ELD). Power output of each generating unit and optimum fuel cost obtained using all three algorithms have been compared. The results obtained show that ABC and BFO algorithms converge to optimal fuel cost with reduced computational time when compared to PSO for the two example problems considered.
A Multi-Factor Security Protocol for Wireless Payment - Secure Web Authentication using Mobile Devices
Venue: arXiv cs.CR 2011
Year: 2011

Previous Web access authentication systems often use either the Web or the Mobile channel individually to confirm the claimed identity of the remote user. This paper proposes a new protocol using multifactor authentication system that is both secure and highly usable. It uses a novel approach based on Transaction Identification Code and SMS to enforce extra security level with the traditional Login/password system. The system provides a highly secure environment that is simple to use and deploy, that does not require any change in infrastructure or protocol of wireless networks. This Protocol for Wireless Payment is extended to provide two way authentications.
Design of a Sliding Window over Asynchronous Event Streams
Venue: arXiv cs.DC 2011
Year: 2011

The proliferation of sensing and monitoring applications motivates adoption of the event stream model of computation. Though sliding windows are widely used to facilitate effective event stream processing, it is greatly challenged when the event sources are distributed and asynchronous. To address this challenge, we first show that the snapshots of the asynchronous event streams within the sliding window form a convex distributive lattice (denoted by Lat-Win). Then we propose an algorithm to maintain Lat-Win at runtime. The Lat-Win maintenance algorithm is implemented and evaluated on the open-source context-aware middleware we developed. The evaluation results first show the necessity of adopting sliding windows over asynchronous event streams. Then they show the performance of detecting specified predicates within Lat-Win, even when faced with dynamic changes in the computing environment.
Maximizing System Throughput by Cooperative Sensing in Cognitive Radio Networks
Venue: arXiv cs.NI 2011
Year: 2011

Cognitive Radio Networks allow unlicensed users to opportunistically access the licensed spectrum without causing disruptive interference to the primary users (PUs). One of the main challenges in CRNs is the ability to detect PU transmissions. Recent works have suggested the use of secondary user (SU) cooperation over individual sensing to improve sensing accuracy. In this paper, we consider a CRN consisting of a single PU and multiple SUs to study the problem of maximizing the total expected system throughput. We propose a Bayesian decision rule based algorithm to solve the problem optimally with a constant time complexity. To prioritize PU transmissions, we re-formulate the throughput maximization problem by adding a constraint on the PU throughput. The constrained optimization problem is shown to be NP-hard and solved via a greedy algorithm with pseudo-polynomial time complexity that achieves strictly greater than 1/2 of the optimal solution. We also investigate the case for which a constraint is put on the sensing time overhead, which limits the number of SUs that can participate in cooperative sensing. We reveal that the system throughput is monotonic over the number of SUs chosen for sensing. We illustrate the efficacy of the performance of our algorithms via a numerical investigation.
On the Application of the Baum-Welch Algorithm for Modeling the Land Mobile Satellite Channel
Venue: arXiv cs.IT 2011
Year: 2011

Accurate channel models are of high importance for the design of upcoming mobile satellite systems. Nowadays most of the models for the LMSC are based on Markov chains and rely on measurement data, rather than on pure theoretical considerations. A key problem lies in the determination of the model parameters out of the observed data. In this work we face the issue of state identification of the underlying Markov model whose model parameters are a priori unknown. This can be seen as a HMM problem. For finding the ML estimates of such model parameters the BW algorithm is adapted to the context of channel modeling. Numerical results on test data sequences reveal the capabilities of the proposed algorithm. Results on real measurement data are finally presented.
A prototype system for handwritten sub-word recognition: Toward Arabic-manuscript transliteration
Venue: arXiv cs.CV 2011
Year: 2011

A prototype system for the transliteration of diacritics-less Arabic manuscripts at the sub-word or part of Arabic word (PAW) level is developed. The system is able to read sub-words of the input manuscript using a set of skeleton-based features. A variation of the system is also developed which reads archigraphemic Arabic manuscripts, which are dot-less, into archigraphemes transliteration. In order to reduce the complexity of the original highly multiclass problem of sub-word recognition, it is redefined into a set of binary descriptor classifiers. The outputs of trained binary classifiers are combined to generate the sequence of sub-word letters. SVMs are used to learn the binary classifiers. Two specific Arabic databases have been developed to train and test the system. One of them is a database of the Naskh style. The initial results are promising. The systems could be trained on other scripts found in Arabic manuscripts.
Lower bounds for finding the maximum and minimum elements with k lies
Venue: arXiv cs.DM 2011
Year: 2011

In this paper we deal with the problem of finding the smallest and the largest elements of a totally ordered set of size $n$ using pairwise comparisons if $k$ of the comparisons might be erroneous where $k$ is a fixed constant. We prove that at least $(k+1.5)n+Θ(k)$ comparisons are needed in the worst case thus disproving the conjecture that $(k+1+ε)n$ comparisons are enough.
Cache optimized linear sieve
Venue: arXiv cs.DS 2011
Year: 2011

Sieving is essential in different number theoretical algorithms. Sieving with large primes violates locality of memory access, thus degrading performance. Our suggestion on how to tackle this problem is to use cyclic data structures in combination with in-place bucket-sort. We present our results on the implementation of the sieve of Eratosthenes, using these ideas, which show that this approach is more robust and less affected by slow memory.
Fixing Data Anomalies with Prediction Based Algorithm in Wireless Sensor Networks
Venue: arXiv cs.DC 2011
Year: 2011

Data inconsistencies are present in the data collected over a large wireless sensor network (WSN), usually deployed for any kind of monitoring applications. Before passing this data to some WSN applications for decision making, it is necessary to ensure that the data received are clean and accurate. In this paper, we have used a statistical tool to examine the past data to fit in a highly sophisticated prediction model i.e., ARIMA for a given sensor node and with this, the model corrects the data using forecast value if any data anomaly exists there. Another scheme is also proposed for detecting data anomaly at sink among the aggregated data in the data are received from a particular sensor node. The effectiveness of our methods are validated by data collected over a real WSN application consisting of Crossbow IRIS Motes \cite{Crossbow:2009}.
Outage probability of selective decode and forward relaying with secrecy constraints
Venue: arXiv cs.IT 2011
Year: 2011

We study the outage probability of opportunistic relay selection in decode-and-forward relaying with secrecy constraints. We derive the closed-form expression for the outage probability. Based on the analytical result, the asymptotic performance is then investigated. The accuracy of our performance analysis is verified by the simulation results.
On context-free languages of scattered words
Venue: arXiv cs.FL 2011
Year: 2011

It is known that if a Büchi context-free language (BCFL) consists of scattered words, then there is an integer $n$, depending only on the language, such that the Hausdorff rank of each word in the language is bounded by $n$. Every BCFL is a Müller context-free language (MCFL). In the first part of the paper, we prove that an MCFL of scattered words is a BCFL iff the rank of every word in the language is bounded by an integer depending only on the language. Then we establish operational characterizations of the BCFLs of well-ordered and scattered words. We prove that a language is a BCFL consisting of well-ordered words iff it can be generated from the singleton languages containing the letters of the alphabet by substitution into ordinary context-free languages and the $ω$-power operation. We also establish a corresponding result for BCFLs of scattered words and define expressions denoting BCFLs of well-ordered and scattered words. In the final part of the paper we give some applications.
Large primes in generalized Pascal triangles
Venue: arXiv cs.DS 2011
Year: 2011

In this paper, after presenting the results of the generalization of Pascal triangle (using powers of base numbers), we examine some properties of the 112-based triangle, most of all regarding to prime numbers. Additionally, an effective implementation of ECPP method is presented which enables Magma computer algebra system to prove the primality of numbers with more than 1000 decimal digits.
New Candidates Welcome! Possible Winners with respect to the Addition of New Candidates
Venue: arXiv cs.AI 2011
Year: 2011

In voting contexts, some new candidates may show up in the course of the process. In this case, we may want to determine which of the initial candidates are possible winners, given that a fixed number $k$ of new candidates will be added. We give a computational study of this problem, focusing on scoring rules, and we provide a formal comparison with related problems such as control via adding candidates or cloning.
Achieving AWGN Channel Capacity with Sparse Graph Modulation and "In the Air" Coupling
Venue: arXiv cs.IT 2011
Year: 2011

Communication over a multiple access channel is considered. Each user modulates his signal as a superposition of redundant data streams where interconnection of data bits can be represented by means of a sparse graph. The receiver observes a signal resulting from the coupling of the sparse modulation graphs. Iterative interference cancellation decoding is analyzed. It is proved that spatial graph coupling allows to achieve the AWGN channel capacity with equal power transmissions.
No Free Lunch versus Occam's Razor in Supervised Learning
Venue: arXiv cs.LG 2011
Year: 2011

The No Free Lunch theorems are often used to argue that domain specific knowledge is required to design successful algorithms. We use algorithmic information theory to argue the case for a universal bias allowing an algorithm to succeed in all interesting problem domains. Additionally, we give a new algorithm for off-line classification, inspired by Solomonoff induction, with good performance on all structured problems under reasonable assumptions. This includes a proof of the efficacy of the well-known heuristic of randomly selecting training data in the hope of reducing misclassification rates.