OpenRaiser/Intern-Atlas huggingface dataset:
Using Repeating Decimals As An Alternative To Prime Numbers In Encryption
Venue: arXiv cs.CR 2010
Year: 2010

This article is meant to provide an additional point of view, applying known knowledge, to supply keys that have a series of non-repeating digits, in a manner that is not usually thought of. Traditionally, prime numbers are used in encryption as keys that have non-repeating sequences. Non-repetition of digits in a key is very sought after in encryption. Uniqueness in a digit sequence defeats decryption by method. In searching for methods of non-decryptable encryption as well as ways to provide unique sequences, other than using prime numbers, the idea of using repeating decimals came to me. Applied correctly, a repeating decimal series of sufficient length will stand in as well for a prime number. This is so, because only numbers prime to each other will produce repeating decimals and; within the repeating sequence there is uniqueness of digit sequence.
Cryptanalysis on Four Two-Party Authentication Protocols
Venue: arXiv cs.CR 2010
Year: 2010

In this paper, we analyze four authentication protocols of Bindu et al., Goriparthi et al., Wang et al. and Hölbl et al.. After investigation, we reveal several weaknesses of these schemes. First, Bindu et al.'s protocol suffers from an insider impersonation attack if a malicious user obtains a lost smart card. Second, both Goriparthi et al.'s and Wang et al.'s protocols cannot withstand a DoS attack in the password change phase, i.e. an attacker can involve the phase to make user's password never be used in subsequent authentications. Third, Hölbl et al.'s protocol is vulnerable to an insider attack since a legal but malevolent user can deduce KGC's secret key.
Acyclic Solos and Differential Interaction Nets
Venue: arXiv cs.LO 2010
Year: 2010

We present a restriction of the solos calculus which is stable under reduction and expressive enough to contain an encoding of the pi-calculus. As a consequence, it is shown that equalizing names that are already equal is not required by the encoding of the pi-calculus. In particular, the induced solo diagrams bear an acyclicity property that induces a faithful encoding into differential interaction nets. This gives a (new) proof that differential interaction nets are expressive enough to contain an encoding of the pi-calculus. All this is worked out in the case of finitary (replication free) systems without sum, match nor mismatch.
Toward Reliable Contention-aware Data Dissemination in Multi-hop Cognitive Radio Ad Hoc Networks
Venue: arXiv cs.NI 2010
Year: 2010

This paper introduces a new channel selection strategy for reliable contentionaware data dissemination in multi-hop cognitive radio network. The key challenge here is to select channels providing a good tradeoff between connectivity and contention. In other words, channels with good opportunities for communication due to (1) low primary radio nodes (PRs) activities, and (2) limited contention of cognitive ratio nodes (CRs) acceding that channel, have to be selected. Thus, by dynamically exploring residual resources on channels and by monitoring the number of CRs on a particular channel, SURF allows building a connected network with limited contention where reliable communication can take place. Through simulations, we study the performance of SURF when compared with three other related approaches. Simulation results confirm that our approach is effective in selecting the best channels for efficient and reliable multi-hop data dissemination.
Applying l-Diversity in anonymizing collaborative social network
Venue: arXiv cs.CY 2010
Year: 2010

To date publish of a giant social network jointly from different parties is an easier collaborative approach. Agencies and researchers who collect such social network data often have a compelling interest in allowing others to analyze the data. In many cases the data describes relationships that are private and sharing the data in full can result in unacceptable disclosures. Thus, preserving privacy without revealing sensitive information in the social network is a serious concern. Recent developments for preserving privacy using anonymization techniques are focused on relational data only. Preserving privacy in social networks against neighborhood attacks is an initiation which uses the definition of privacy called k-anonymity. k-anonymous social network still may leak privacy under the cases of homogeneity and background knowledge attacks. To overcome, we find a place to use a new practical and efficient definition of privacy called ldiversity. In this paper, we take a step further on preserving privacy in collaborative social network data with algorithms and analyze the effect on the utility of the data for social network analysis.
Pseudorandom generators and the BQP vs. PH problem
Venue: arXiv cs.CC 2010
Year: 2010

It is a longstanding open problem to devise an oracle relative to which BQP does not lie in the Polynomial-Time Hierarchy (PH). We advance a natural conjecture about the capacity of the Nisan-Wigderson pseudorandom generator [NW94] to fool AC_0, with MAJORITY as its hard function. Our conjecture is essentially that the loss due to the hybrid argument (which is a component of the standard proof from [NW94]) can be avoided in this setting. This is a question that has been asked previously in the pseudorandomness literature [BSW03]. We then make three main contributions: (1) We show that our conjecture implies the existence of an oracle relative to which BQP is not in the PH. This entails giving an explicit construction of unitary matrices, realizable by small quantum circuits, whose row-supports are "nearly-disjoint." (2) We give a simple framework (generalizing the setting of Aaronson [A10]) in which any efficiently quantumly computable unitary gives rise to a distribution that can be distinguished from the uniform distribution by an efficient quantum algorithm. When applied to the unitaries we construct, this framework yields a problem that can be solved quantumly, and which forms the basis for the desired oracle. (3) We prove that Aaronson's "GLN conjecture" [A10] implies our conjecture; our conjecture is thus formally easier to prove. The GLN conjecture was recently proved false for depth greater than 2 [A10a], but it remains open for depth 2. If true, the depth-2 version of either conjecture would imply an oracle relative to which BQP is not in AM, which is itself an outstanding open problem. Taken together, our results have the following interesting interpretation: they give an instantiation of the Nisan-Wigderson generator that can be broken by quantum computers, but not by the relevant modes of classical computation, if our conjecture is true.
A Performance Comparison of Stability, Load-Balancing and Power-Aware Routing Protocols for Mobile Ad Hoc Networks
Venue: arXiv cs.NI 2010
Year: 2010

The high-level contribution of this paper is a simulation-based detailed performance comparison of three different classes of routing protocols for mobile ad hoc networks: stability-based routing, power-aware routing and load-balanced routing. We choose the Flow-Oriented Routing protocol (FORP), the traffic interference based Load Balancing Routing (LBR) protocol and Min-Max Battery Cost Routing (MMBCR) as representatives of the stability-based routing, load-balancing and power-aware routing protocols respectively. Among the three routing protocols, FORP incurs the least number of route transitions; while LBR incurs the smallest hop count and lowest end-to-end delay per data packet. Energy consumed per node is the least for MMBCR, closely followed by LBR. MMBCR is the most fair in terms of node usage and hence it incurs the largest time for first node failure. FORP tends to repeatedly use nodes lying on the stable path and hence is the most unfair of the three routing protocols and it incurs the smallest value for the time of first node failure. As we measure the failure times of up to the first five nodes in the network, we observe that LBR incurs the maximum improvement in the lifetime of the nodes and MMBCR incurs the least improvement beyond the time of first node failure.
Improving Iris Recognition Accuracy By Score Based Fusion Method
Venue: arXiv cs.AI 2010
Year: 2010

Iris recognition technology, used to identify individuals by photographing the iris of their eye, has become popular in security applications because of its ease of use, accuracy, and safety in controlling access to high-security areas. Fusion of multiple algorithms for biometric verification performance improvement has received considerable attention. The proposed method combines the zero-crossing 1 D wavelet Euler number, and genetic algorithm based for feature extraction. The output from these three algorithms is normalized and their score are fused to decide whether the user is genuine or imposter. This new strategies is discussed in this paper, in order to compute a multimodal combined score.
Transmit Energy Focusing for DOA Estimation in MIMO Radar with Colocated Antennas
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we propose a transmit beamspace energy focusing technique for multiple-input multiple-output (MIMO) radar with application to direction finding for multiple targets. The general angular directions of the targets are assumed to be located within a certain spatial sector. We focus the energy of multiple (two or more) transmitted orthogonal waveforms within that spatial sector using transmit beamformers which are designed to improve the signal-to-noise ratio (SNR) gain at each receive antenna. The subspace decomposition-based techniques such as MUSIC can then be used for direction finding for multiple targets. Moreover, the transmit beamformers can be designed so that matched-filtering the received data to the waveforms yields multiple (two or more) data sets with rotational invariance property that allows applying search-free direction finding techniques such as ESPRIT for two data sets or parallel factor analysis (PARAFAC) for more than two data sets. Unlike previously reported MIMO radar ESPRIT/PARAFAC-based direction finding techniques, our method achieves the rotational invariance property in a different manner combined also with the transmit energy focusing. As a result, it achieves better estimation performance at lower computational cost. Particularly, the proposed technique leads to lower Cramer-Rao bound than the existing techniques due to the transmit energy focusing capability. Simulation results also show the superiority of the proposed technique over the existing techniques.
On the Solvability of 2-pair Unicast Networks --- A Cut-based Characterization
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we propose a subnetwork decomposition/combination approach to investigate the single rate $2$-pair unicast problem. It is shown that the solvability of a $2$-pair unicast problem is completely determined by four specific link subsets, namely, $\mathcal A_{1,1}$, $\mathcal A_{2,2}$, $\mathcal A_{1,2}$ and $\mathcal A_{2,1}$ of its underlying network. As a result, an efficient cut-based algorithm to determine the solvability of a $2$-pair unicast problem is presented.
IMP: A Message-Passing Algorithmfor Matrix Completion
Venue: arXiv cs.IT 2010
Year: 2010

A new message-passing (MP) method is considered for the matrix completion problem associated with recommender systems. We attack the problem using a (generative) factor graph model that is related to a probabilistic low-rank matrix factorization. Based on the model, we propose a new algorithm, termed IMP, for the recovery of a data matrix from incomplete observations. The algorithm is based on a clustering followed by inference via MP (IMP). The algorithm is compared with a number of other matrix completion algorithms on real collaborative filtering (e.g., Netflix) data matrices. Our results show that, while many methods perform similarly with a large number of revealed entries, the IMP algorithm outperforms all others when the fraction of observed entries is small. This is helpful because it reduces the well-known cold-start problem associated with collaborative filtering (CF) systems in practice.
Query Strategies for Evading Convex-Inducing Classifiers
Venue: arXiv cs.LG 2010
Year: 2010

Classifiers are often used to detect miscreant activities. We study how an adversary can systematically query a classifier to elicit information that allows the adversary to evade detection while incurring a near-minimal cost of modifying their intended malfeasance. We generalize the theory of Lowd and Meek (2005) to the family of convex-inducing classifiers that partition input space into two sets one of which is convex. We present query algorithms for this family that construct undetected instances of approximately minimal cost using only polynomially-many queries in the dimension of the space and in the level of approximation. Our results demonstrate that near-optimal evasion can be accomplished without reverse-engineering the classifier's decision boundary. We also consider general lp costs and show that near-optimal evasion on the family of convex-inducing classifiers is generally efficient for both positive and negative convexity for all levels of approximation if p=1.
Simulation-Checking of Real-Time Systems with Fairness Assumptions
Venue: arXiv cs.LO 2010
Year: 2010

We investigate the simulation problem in of dense-time system. A specification simulates a model if the specification can match every transition that the model can make at a time point. We also adapt the approach of Emerson and Lei and allow for multiple strong and weak fairness assumptions in checking the simulation relation. Furthermore, we allow for fairness assumptions specified as either state-predicates or event-predicates. We focus on a subclass of the problem with at most one fairness assumption for the specification. We then present a simulation-checking algorithm for this subclass. We propose simulation of a model by a specification against a common environment. We present efficient techniques for such simulations to take the common environment into consideration. Our experiment shows that such a consideration can dramatically improve the efficiency of checking simulation. We also report the performance of our algorithm in checking the liveness properties with fairness assumptions.
Face Synthesis (FASY) System for Determining the Characteristics of a Face Image
Venue: arXiv cs.CV 2010
Year: 2010

This paper aims at determining the characteristics of a face image by extracting its components. The FASY (FAce SYnthesis) System is a Face Database Retrieval and new Face generation System that is under development. One of its main features is the generation of the requested face when it is not found in the existing database, which allows a continuous growing of the database also. To generate the new face image, we need to store the face components in the database. So we have designed a new technique to extract the face components by a sophisticated method. After extraction of the facial feature points we have analyzed the components to determine their characteristics. After extraction and analysis we have stored the components along with their characteristics into the face database for later use during the face construction.
Scheduling Periodic Real-Time Tasks with Heterogeneous Reward Requirements
Venue: arXiv cs.OH 2010
Year: 2010

We study the problem of scheduling periodic real-time tasks so as to meet their individual minimum reward requirements. A task generates jobs that can be given arbitrary service times before their deadlines. A task then obtains rewards based on the service times received by its jobs. We show that this model is compatible to the imprecise computation models and the increasing reward with increasing service models. In contrast to previous work on these models, which mainly focus on maximize the total reward in the system, we aim to fulfill different reward requirements by different tasks, which offers better fairness and allows fine-grained tradeoff between tasks. We first derive a necessary and sufficient condition for a system, along with reward requirements of tasks, to be feasible. We also obtain an off-line feasibility optimal scheduling policy. We then studies a sufficient condition for a policy to be feasibility optimal or achieves some approximation bound. This condition can serve as a guideline for designing on-line scheduling policy and we obtains a greedy policy based on it. We prove that the on-line policy is feasibility optimal when all tasks have the same periods and also obtain an approximation bound for the policy under general cases.
Fountain Codes with Multiplicatively Repeated Non-Binary LDPC Codes
Venue: arXiv cs.IT 2010
Year: 2010

We study fountain codes transmitted over the binary-input symmetric-output channel. For channels with small capacity, receivers needs to collects many channel outputs to recover information bits. Since a collected channel output yields a check node in the decoding Tanner graph, the channel with small capacity leads to large decoding complexity. In this paper, we introduce a novel fountain coding scheme with non-binary LDPC codes. The decoding complexity of the proposed fountain code does not depend on the channel. Numerical experiments show that the proposed codes exhibit better performance than conventional fountain codes, especially for small number of information bits.
Filtrage vaste marge pour l'étiquetage séquentiel à noyaux de signaux
Venue: arXiv cs.LG 2010
Year: 2010

We address in this paper the problem of multi-channel signal sequence labeling. In particular, we consider the problem where the signals are contaminated by noise or may present some dephasing with respect to their labels. For that, we propose to jointly learn a SVM sample classifier with a temporal filtering of the channels. This will lead to a large margin filtering that is adapted to the specificity of each channel (noise and time-lag). We derive algorithms to solve the optimization problem and we discuss different filter regularizations for automated scaling or selection of channels. Our approach is tested on a non-linear toy example and on a BCI dataset. Results show that the classification performance on these problems can be improved by learning a large margin filtering.
Handling software upgradeability problems with MILP solvers
Venue: arXiv cs.LO 2010
Year: 2010

Upgradeability problems are a critical issue in modern operating systems. The problem consists in finding the "best" solution according to some criteria, to install, remove or upgrade packages in a given installation. This is a difficult problem: the complexity of the upgradeability problem is NP complete and modern OS contain a huge number of packages (often more than 20 000 packages in a Linux distribution). Moreover, several optimisation criteria have to be considered, e.g., stability, memory efficiency, network efficiency. In this paper we investigate the capabilities of MILP solvers to handle this problem. We show that MILP solvers are very efficient when the resolution is based on a linear combination of the criteria. Experiments done on real benchmarks show that the best MILP solvers outperform CP solvers and that they are significantly better than Pseudo Boolean solvers.
Narrow sieves for parameterized paths and packings
Venue: arXiv cs.DS 2010
Year: 2010

We present randomized algorithms for some well-studied, hard combinatorial problems: the k-path problem, the p-packing of q-sets problem, and the q-dimensional p-matching problem. Our algorithms solve these problems with high probability in time exponential only in the parameter (k, p, q) and using polynomial space; the constant bases of the exponentials are significantly smaller than in previous works. For example, for the k-path problem the improvement is from 2 to 1.66. We also show how to detect if a d-regular graph admits an edge coloring with $d$ colors in time within a polynomial factor of O(2^{(d-1)n/2}). Our techniques build upon and generalize some recently published ideas by I. Koutis (ICALP 2009), R. Williams (IPL 2009), and A. Björklund (STACS 2010, FOCS 2010).
Composite Cyclotomic Fourier Transforms with Reduced Complexities
Venue: arXiv cs.IT 2010
Year: 2010

Discrete Fourier transforms~(DFTs) over finite fields have widespread applications in digital communication and storage systems. Hence, reducing the computational complexities of DFTs is of great significance. Recently proposed cyclotomic fast Fourier transforms (CFFTs) are promising due to their low multiplicative complexities. Unfortunately, there are two issues with CFFTs: (1) they rely on efficient short cyclic convolution algorithms, which has not been investigated thoroughly yet, and (2) they have very high additive complexities when directly implemented. In this paper, we address both issues. One of the main contributions of this paper is efficient bilinear 11-point cyclic convolution algorithms, which allow us to construct CFFTs over GF$(2^{11})$. The other main contribution of this paper is that we propose composite cyclotomic Fourier transforms (CCFTs). In comparison to previously proposed fast Fourier transforms, our CCFTs achieve lower overall complexities for moderate to long lengths, and the improvement significantly increases as the length grows. Our 2047-point and 4095-point CCFTs are also first efficient DFTs of such lengths to the best of our knowledge. Finally, our CCFTs are also advantageous for hardware implementations due to their regular and modular structure.
MalStone: Towards A Benchmark for Analytics on Large Data Clouds
Venue: arXiv cs.DC 2010
Year: 2010

Developing data mining algorithms that are suitable for cloud computing platforms is currently an active area of research, as is developing cloud computing platforms appropriate for data mining. Currently, the most common benchmark for cloud computing is the Terasort (and related) benchmarks. Although the Terasort Benchmark is quite useful, it was not designed for data mining per se. In this paper, we introduce a benchmark called MalStone that is specifically designed to measure the performance of cloud computing middleware that supports the type of data intensive computing common when building data mining models. We also introduce MalGen, which is a utility for generating data on clouds that can be used with MalStone.
Development of a Context Aware Virtual Smart Home Simulator
Venue: arXiv cs.NI 2010
Year: 2010

Context awareness is the most important research area in ubiquitous computing. In particular, for smart home, context awareness attempts to bring the best services to the home habitants. However, the implementation in the real environment is not easy and takes a long time from building the scratch. Thus, to support the implementation in the real smart home, it is necessary to demonstrate that thing can be done in the simulator in which context information can be created by virtual sensors instead of physical sensors. In this paper, we propose ISS, an Interactive Smart home Simulator system aiming at controlling and simulating the behavior of an intelligent house. The developed system aims to provide architects, designers a simulation and useful tool for understanding the interaction between environment, people and the impact of embedded and pervasive technology on in daily life. In this research, the smart house is considered as an environment made up of independent and distributed devices interacting to support user's goals and tasks. Therefore, by using ISS, the developer can realize the relationship among virtual home space, surrounded environment, use and home appliances.