OpenRaiser/Intern-Atlas huggingface dataset:
Improving Link Prediction in Intermittently Connected Wireless Networks by Considering Link and Proximity Stabilities
Venue: arXiv cs.NI 2012
Year: 2012

Several works have outlined the fact that the mobility in intermittently connected wireless networks is strongly governed by human behaviors as they are basically human-centered. It has been shown that the users' moves can be correlated and that the social ties shared by the users highly impact their mobility patterns and hence the network structure. Tracking these correlations and measuring the strength of social ties have led us to propose an efficient distributed tensor-based link prediction technique. In fact, we are convinced that the feedback provided by such a prediction mechanism can enhance communication protocols such as opportunistic routing protocols. In this paper, we aim to bring out that measuring the stabilities of the link and the proximity at two hops can improve the efficiency of the proposed link prediction technique. To quantify these two parameters, we propose an entropy estimator in order to measure the two stability aspects over successive time periods. Then, we join these entropy estimations to the tensor-based link prediction framework by designing new prediction metrics. To assess the contribution of these entropy estimations in the enhancement of tensor-based link prediction efficiency, we perform prediction on two real traces. Our simulation results show that by exploiting the information corresponding to the link stability and/or to the proximity stability, the performance of the tensor-based link prediction technique is improved. Moreover, the results attest that our proposal's ability to outperform other well-known prediction metrics.
Distribution of the search of evolutionary product unit neural networks for classification
Venue: arXiv cs.NE 2012
Year: 2012

This paper deals with the distributed processing in the search for an optimum classification model using evolutionary product unit neural networks. For this distributed search we used a cluster of computers. Our objective is to obtain a more efficient design than those net architectures which do not use a distributed process and which thus result in simpler designs. In order to get the best classification models we use evolutionary algorithms to train and design neural networks, which require a very time consuming computation. The reasons behind the need for this distribution are various. It is complicated to train this type of nets because of the difficulty entailed in determining their architecture due to the complex error surface. On the other hand, the use of evolutionary algorithms involves running a great number of tests with different seeds and parameters, thus resulting in a high computational cost
Unfair items detection in educational measurement
Venue: arXiv cs.AI 2012
Year: 2012

Measurement professionals cannot come to an agreement on the definition of the term 'item fairness'. In this paper a continuous measure of item unfairness is proposed. The more the unfairness measure deviates from zero, the less fair the item is. If the measure exceeds the cutoff value, the item is identified as definitely unfair. The new approach can identify unfair items that would not be identified with conventional procedures. The results are in accord with experts' judgments on the item qualities. Since no assumptions about scores distributions and/or correlations are assumed, the method is applicable to any educational test. Its performance is illustrated through application to scores of a real test.
Power Series Solutions of Singular (q)-Differential Equations
Venue: arXiv cs.SC 2012
Year: 2012

We provide algorithms computing power series solutions of a large class of differential or $q$-differential equations or systems. Their number of arithmetic operations grows linearly with the precision, up to logarithmic terms.
Error-correcting pairs for a public-key cryptosystem
Venue: arXiv cs.IT 2012
Year: 2012

Code-based cryptography is an interesting alternative to classic number-theory PKC since it is conjectured to be secure against quantum computer attacks. Many families of codes have been proposed for these cryptosystems, one of the main requirements is having high performance t-bounded decoding algorithms which in the case of having high an error-correcting pair is achieved. In this article the class of codes with a t-ECP is proposed for the McEliece cryptosystem. The hardness of retrieving the t-ECP for a given code is considered. As a first step distinguishers of several subclasses are given.
Synthesis and Adaptation of Effective Motor Synergies for the Solution of Reaching Tasks
Venue: arXiv cs.RO 2012
Year: 2012

Taking inspiration from the hypothesis of muscle synergies, we propose a method to generate open loop controllers for an agent solving point-to-point reaching tasks. The controller output is defined as a linear combination of a small set of predefined actuations, termed synergies. The method can be interpreted from a developmental perspective, since it allows the agent to autonomously synthesize and adapt an effective set of synergies to new behavioral needs. This scheme greatly reduces the dimensionality of the control problem, while keeping a good performance level. The framework is evaluated in a planar kinematic chain, and the quality of the solutions is quantified in several scenarios.
Secrecy Is Cheap if the Adversary Must Reconstruct
Venue: arXiv cs.IT 2012
Year: 2012

A secret key can be used to conceal information from an eavesdropper during communication, as in Shannon's cipher system. Most theoretical guarantees of secrecy require the secret key space to grow exponentially with the length of communication. Here we show that when an eavesdropper attempts to reconstruct an information sequence, as posed in the literature by Yamamoto, very little secret key is required to effect unconditionally maximal distortion; specifically, we only need the secret key space to increase unboundedly, growing arbitrarily slowly with the blocklength. As a corollary, even with a secret key of constant size we can still cause the adversary arbitrarily close to maximal distortion, regardless of the length of the information sequence.
Three-Receiver Broadcast Channels with Side Information
Venue: arXiv cs.IT 2012
Year: 2012

Three-receiver broadcast channel (BC) is of interest due to its information theoretical differences with two receiver one. In this paper, we derive achievable rate regions for two classes of 3-receiver BC with side information available at the transmitter, Multilevel BC and 3-receiver less noisy BC, by using superposition coding, Gel'fand-Pinsker binning scheme and Nair-El Gamal indirect decoding. Our rate region for multilevel BC subsumes the Steinberg rate region for 2-receiver degraded BC with side information as its special case. We also find the capacity region of 3-receiver less noisy BC when side information is available both at the transmitter and at the receivers.
Optimal Weights Mixed Filter for Removing Mixture of Gaussian and Impulse Noises
Venue: arXiv cs.CV 2012
Year: 2012

According to the character of Gaussian, we modify the Rank-Ordered Absolute Differences (ROAD) to Rank-Ordered Absolute Differences of mixture of Gaussian and impulse noises (ROADG). It will be more effective to detect impulse noise when the impulse is mixed with Gaussian noise. Combining rightly the ROADG with Optimal Weights Filter (OWF), we obtain a new method to deal with the mixed noise, called Optimal Weights Mixed Filter (OWMF). The simulation results show that the method is effective to remove the mixed noise.
Fast Correlation Computation Method for Matching Pursuit Algorithms in Compressed Sensing
Venue: arXiv cs.IT 2012
Year: 2012

There have been many matching pursuit algorithms (MPAs) which handle the sparse signal recovery problem a.k.a. compressed sensing (CS). In the MPAs, the correlation computation step has a dominant computational complexity. In this letter, we propose a new fast correlation computation method when we use some classes of partial unitary matrices as the sensing matrix. Those partial unitary matrices include partial Fourier matrices and partial Hadamard matrices which are popular sensing matrices. The proposed correlation computation method can be applied to almost all MPAs without causing any degradation of their recovery performance. And, for most practical parameters, the proposed method can reduce the computational complexity of the MPAs substantially.
Approximate Feedback Capacity of the Gaussian Multicast Channel
Venue: arXiv cs.IT 2012
Year: 2012

We characterize the capacity region to within log{2(M-1)} bits/s/Hz for the M-transmitter K-receiver Gaussian multicast channel with feedback where each receiver wishes to decode every message from the M transmitters. Extending Cover-Leung's achievable scheme intended for (M,K)=(2,1), we show that this generalized scheme achieves the cutset-based outer bound within log{2(M-1)} bits per transmitter for all channel parameters. In contrast to the capacity in the non-feedback case, the feedback capacity improves upon the naive intersection of the feedback capacities of K individual multiple access channels. We find that feedback provides unbounded multiplicative gain at high signal-to-noise ratios as was shown in the Gaussian interference channel. To complement the results, we establish the exact feedback capacity of the Avestimehr-Diggavi-Tse (ADT) deterministic model, from which we make the observation that feedback can also be beneficial for function computation.
Frameless ALOHA Protocol for Wireless Networks
Venue: arXiv cs.IT 2012
Year: 2012

We propose a novel distributed random access scheme for wireless networks based on slotted ALOHA, motivated by the analogies between successive interference cancellation and iterative belief-propagation decoding on erasure channels. The proposed scheme assumes that each user independently accesses the wireless link in each slot with a predefined probability, resulting in a distribution of user transmissions over slots. The operation bears analogy with rateless codes, both in terms of probability distributions as well as to the fact that the ALOHA frame becomes fluid and adapted to the current contention process. Our aim is to optimize the slot access probability in order to achieve rateless-like distributions, focusing both on the maximization of the resolution probability of user transmissions and the throughput of the scheme.
Three Schemes for Wireless Coded Broadcast to Heterogeneous Users
Venue: arXiv cs.NI 2012
Year: 2012

We study and compare three coded schemes for single-server wireless broadcast of multiple description coded content to heterogeneous users. The users (sink nodes) demand different number of descriptions over links with different packet loss rates. The three coded schemes are based on the LT codes, growth codes, and randomized chunked codes. The schemes are compared on the basis of the total number of transmissions required to deliver the demands of all users, which we refer to as the server (source) delivery time. We design the degree distributions of LT codes by solving suitably defined linear optimization problems, and numerically characterize the achievable delivery time for different coding schemes. We find that including a systematic phase (uncoded transmission) is significantly beneficial for scenarios with low demands, and that coding is necessary for efficiently delivering high demands. Different demand and error rate scenarios may require very different coding schemes. Growth codes and chunked codes do not perform as well as optimized LT codes in the heterogeneous communication scenario.
Transference & Retrieval of Pulse-code modulation Audio over Short Messaging Service
Venue: arXiv cs.NI 2012
Year: 2012

The paper presents the method of transferring PCM (Pulse-Code Modulation) based audio messages through SMS (Short Message Service) over GSM (Global System for Mobile Communications) network. As SMS is text based service, and could not send voice. Our method enables voice transferring through SMS, by converting PCM audio into characters. Than Huffman coding compression technique is applied in order to reduce numbers of characters which will latterly set as payload text of SMS. Testing the said method we develop an application using J2me platform
Combined Decode-Forward and Layered Noisy Network Coding Schemes for Relay Channels
Venue: arXiv cs.IT 2012
Year: 2012

We propose two coding schemes combining decode-forward (DF) and noisy network coding (NNC) with different flavors. The first is a combined DF-NNC scheme for the one-way relay channel which includes both DF and NNC as special cases by performing rate splitting, partial block Markov encoding and NNC. The second combines two different DF strategies and layered NNC for the two-way relay channel. One DF strategy performs coherent block Markov encoding at the source at the cost of power splitting at the relay, the other performs independent source and relay encoding but with full relay power, and layered NNC allows a different compression rate for each destination. Analysis and simulation show that both proposed schemes supersede each individual scheme and take full advantage of both DF and NNC.
Model Checking Vector Addition Systems with one zero-test
Venue: arXiv cs.DM 2012
Year: 2012

We design a variation of the Karp-Miller algorithm to compute, in a forward manner, a finite representation of the cover (i.e., the downward closure of the reachability set) of a vector addition system with one zero-test. This algorithm yields decision procedures for several problems for these systems, open until now, such as place-boundedness or LTL model-checking. The proof techniques to handle the zero-test are based on two new notions of cover: the refined and the filtered cover. The refined cover is a hybrid between the reachability set and the classical cover. It inherits properties of the reachability set: equality of two refined covers is undecidable, even for usual Vector Addition Systems (with no zero-test), but the refined cover of a Vector Addition System is a recursive set. The second notion of cover, called the filtered cover, is the central tool of our algorithms. It inherits properties of the classical cover, and in particular, one can effectively compute a finite representation of this set, even for Vector Addition Systems with one zero-test.
Pilgrims Face Recognition Dataset -- HUFRD
Venue: arXiv cs.CV 2012
Year: 2012

In this work, we define a new pilgrims face recognition dataset, called HUFRD dataset. The new developed dataset presents various pilgrims' images taken from outside the Holy Masjid El-Harram in Makkah during the 2011-2012 Hajj and Umrah seasons. Such dataset will be used to test our developed facial recognition and detection algorithms, as well as assess in the missing and found recognition system \cite{crowdsensing}.
Computational Complexity of Traffic Hijacking under BGP and S-BGP
Venue: arXiv cs.NI 2012
Year: 2012

Harmful Internet hijacking incidents put in evidence how fragile the Border Gateway Protocol (BGP) is, which is used to exchange routing information between Autonomous Systems (ASes). As proved by recent research contributions, even S-BGP, the secure variant of BGP that is being deployed, is not fully able to blunt traffic attraction attacks. Given a traffic flow between two ASes, we study how difficult it is for a malicious AS to devise a strategy for hijacking or intercepting that flow. We show that this problem marks a sharp difference between BGP and S-BGP. Namely, while it is solvable, under reasonable assumptions, in polynomial time for the type of attacks that are usually performed in BGP, it is NP-hard for S-BGP. Our study has several by-products. E.g., we solve a problem left open in the literature, stating when performing a hijacking in S-BGP is equivalent to performing an interception.
Constructing a Pseudorandom Generator Requires an Almost Linear Number of Calls
Venue: arXiv cs.CR 2012
Year: 2012

We show that a black-box construction of a pseudorandom generator from a one-way function needs to make Omega(n/log(n)) calls to the underlying one-way function. The bound even holds if the one-way function is guaranteed to be regular. In this case it matches the best known construction due to Goldreich, Krawczyk, and Luby (SIAM J. Comp. 22, 1993), which uses O(n/log(n)) calls.
No Sublogarithmic-time Approximation Scheme for Bipartite Vertex Cover
Venue: arXiv cs.DC 2012
Year: 2012

König's theorem states that on bipartite graphs the size of a maximum matching equals the size of a minimum vertex cover. It is known from prior work that for every ε> 0 there exists a constant-time distributed algorithm that finds a (1+ε)-approximation of a maximum matching on 2-coloured graphs of bounded degree. In this work, we show---somewhat surprisingly---that no sublogarithmic-time approximation scheme exists for the dual problem: there is a constant δ> 0 so that no randomised distributed algorithm with running time o(\log n) can find a (1+δ)-approximation of a minimum vertex cover on 2-coloured graphs of maximum degree 3. In fact, a simple application of the Linial--Saks (1993) decomposition demonstrates that this lower bound is tight. Our lower-bound construction is simple and, to some extent, independent of previous techniques. Along the way we prove that a certain cut minimisation problem, which might be of independent interest, is hard to approximate locally on expander graphs.
Iterative Approximate Byzantine Consensus under a Generalized Fault Model
Venue: arXiv cs.DC 2012
Year: 2012

In this work, we consider a generalized fault model that can be used to represent a wide range of failure scenarios, including correlated failures and non-uniform node reliabilities. This fault model is general in the sense that fault models studied in prior related work, such as f -total and f -local models, are special cases of the generalized fault model. Under the generalized fault model, we explore iterative approximate Byzantine consensus (IABC) algorithms in arbitrary directed networks. We prove a necessary and sufficient condition for the existence of IABC algorithms. The use of the generalized fault model helps to gain a better understanding of IABC algorithms.
SD-EQR: A New Technique To Use QR CodesTM in Cryptography
Venue: arXiv cs.CR 2012
Year: 2012

In this paper the author present a new technique of using QR Codes (commonly known as 'Quick Respond Codes') in the field of Cryptography. QR Codes are mainly used to convey or store messages because they have higher or large storage capacity than any other normal conventional 'barcodes'. In this paper the primary focus will be on storing messages in encrypted format with a password and send it to the required destination hiding in a QR Code, without being tracked or decrypted properly by any hacker or spyware. Since QR Codes have fast response time and have large storage capacity, QR Codes can be used perfectly to send encrypted data (messages) to the receiver. This method will be suitable in any business house, government sectors, communication network to send their encrypted messages faster to the destination. Or a person can even use this method to keep his important documents, like passport number, pan-card id, social security number, perfectly secured with him all the time, without the information getting leaked to outside world. The new method is achieved by entering the message along with a password. This password will generate a secret code, which will be added to each digit or alphabet in the numbers or text entered in the message (which is needed to be encrypted) and generate the first phase of encryption. That newly generated encrypted message will again be encrypted using various other methods to generate the final encrypted message.
Gray Level Co-Occurrence Matrices: Generalisation and Some New Features
Venue: arXiv cs.CV 2012
Year: 2012

Gray Level Co-occurrence Matrices (GLCM) are one of the earliest techniques used for image texture analysis. In this paper we defined a new feature called trace extracted from the GLCM and its implications in texture analysis are discussed in the context of Content Based Image Retrieval (CBIR). The theoretical extension of GLCM to n-dimensional gray scale images are also discussed. The results indicate that trace features outperform Haralick features when applied to CBIR.
On the practically interesting instances of MAXCUT
Venue: arXiv cs.CC 2012
Year: 2012

The complexity of a computational problem is traditionally quantified based on the hardness of its worst case. This approach has many advantages and has led to a deep and beautiful theory. However, from the practical perspective, this leaves much to be desired. In application areas, practically interesting instances very often occupy just a tiny part of an algorithm's space of instances, and the vast majority of instances are simply irrelevant. Addressing these issues is a major challenge for theoretical computer science which may make theory more relevant to the practice of computer science. Following Bilu and Linial, we apply this perspective to MAXCUT, viewed as a clustering problem. Using a variety of techniques, we investigate practically interesting instances of this problem. Specifically, we show how to solve in polynomial time distinguished, metric, expanding and dense instances of MAXCUT under mild stability assumptions. In particular, $(1+ε)$-stability (which is optimal) suffices for metric and dense MAXCUT. We also show how to solve in polynomial time $Ω(\sqrt{n})$-stable instances of MAXCUT, substantially improving the best previously known result.
A Multiple Access Protocol for Multimedia Transmission over Wireless Networks
Venue: arXiv cs.NI 2012
Year: 2012

This paper develops and evaluates the performance of an advanced multiple access protocol for transmission of full complement of multimedia signals consisting of various combinations of voice, video, data, text and images over wireless networks. The protocol is called Advanced Multiple Access Protocol for Multimedia Transmission (AMAPMT) and is to be used in the Data Link Layer of the protocol stack. The principle of operation of the protocol is presented in a number of logical flow charts. The protocol grants permission to transmit to a source on the basis of a priority scheme that takes into account a time-to-live (TTL) parameter of all the transactions, selectable priorities assigned to all the sources and relevant channel state information (CSI) in this order. Performance of the protocol is evaluated in terms of quality of service parameters like packet loss ratio (PLR), mean packet transfer delay (MPTD) and throughput. Using a simulation model based on an OPNET simulation software package does the evaluation. Under various traffic loads with constant distributions with various mean arrival rates and transaction sizes results obtained show that the performance is improved when this priority scheme is used than when it is not used. The results for AMAPMT are compared with that of the best currently available multiple access protocol called Adaptive Request Channel Multiple Access (ARCMA). AMAPMT protocol out performs ARCMA protocol.