OpenRaiser/Intern-Atlas huggingface dataset:
Analysis And Improvement of Pairing-Free Certificate-Less Two-Party Authenticated Key Agreement Protocol For Grid Computing
Venue: arXiv cs.CR 2014
Year: 2014

The predominant grid authentication mechanisms use public key infrastructure (PKI). Nonetheless, certificate-less public key cryptography (CL-PKC) has several advantages that seem to well align with the demands of grid computing. Security and efficiency are the main objectives of grid authentication protocols. Unfortunately, certificate-less authenticated key agreement protocols rely on the bilinear pairing, that is extremely computational expensive. In this paper, we analyze the recently secure certificateless key agreement protocols without pairing. We then propose a novel grid pairing-free certificate-less two-party authenticated key agreement (GPC-AKA) protocol, providing a more lightweight key management approach for grid users. We also show, a GPC-AKA security protocol proof using formal automated security analysis Sycther tool.
Cancer Prognosis Prediction Using Balanced Stratified Sampling
Venue: arXiv cs.LG 2014
Year: 2014

High accuracy in cancer prediction is important to improve the quality of the treatment and to improve the rate of survivability of patients. As the data volume is increasing rapidly in the healthcare research, the analytical challenge exists in double. The use of effective sampling technique in classification algorithms always yields good prediction accuracy. The SEER public use cancer database provides various prominent class labels for prognosis prediction. The main objective of this paper is to find the effect of sampling techniques in classifying the prognosis variable and propose an ideal sampling method based on the outcome of the experimentation. In the first phase of this work the traditional random sampling and stratified sampling techniques have been used. At the next level the balanced stratified sampling with variations as per the choice of the prognosis class labels have been tested. Much of the initial time has been focused on performing the pre_processing of the SEER data set. The classification model for experimentation has been built using the breast cancer, respiratory cancer and mixed cancer data sets with three traditional classifiers namely Decision Tree, Naive Bayes and K-Nearest Neighbor. The three prognosis factors survival, stage and metastasis have been used as class labels for experimental comparisons. The results shows a steady increase in the prediction accuracy of balanced stratified model as the sample size increases, but the traditional approach fluctuates before the optimum results.
Complexity of the General Chromatic Art Gallery Problem
Venue: arXiv cs.CG 2014
Year: 2014

In the original Art Gallery Problem (AGP), one seeks the minimum number of guards required to cover a polygon $P$. We consider the Chromatic AGP (CAGP), where the guards are colored. As long as $P$ is completely covered, the number of guards does not matter, but guards with overlapping visibility regions must have different colors. This problem has applications in landmark-based mobile robot navigation: Guards are landmarks, which have to be distinguishable (hence the colors), and are used to encode motion primitives, \eg, "move towards the red landmark". Let $χ_G(P)$, the chromatic number of $P$, denote the minimum number of colors required to color any guard cover of $P$. We show that determining, whether $χ_G(P) \leq k$ is \NP-hard for all $k \geq 2$. Keeping the number of colors minimal is of great interest for robot navigation, because less types of landmarks lead to cheaper and more reliable recognition.
A Framework for Pricing Schemes for Networks under Complete Information
Venue: arXiv cs.NI 2014
Year: 2014

The revenue maximization problem of service provider is considered and different pricing schemes to solve the above problem are implemented. The service provider can choose an apt pricing scheme subjected to limited resources, if he knows the utility function and identity of the user. The complete price differentiation can achieve a large revenue gain but has high implementation complexity. The partial price differentiation scheme to overcome the high implementational complexity of complete price differentiation scheme is also studied. A polynomial- time algorithm is designed for partial price differentiation scheme that can compute the optimal partial differentiation prices. The willingness of the users to pay is also considered while designing price differentiation schemes.
Signaling in sensor networks for sequential detection
Venue: arXiv cs.SY 2014
Year: 2014

Sequential detection problems in sensor networks are considered. The true state of nature/true hypothesis is modeled as a binary random variable $H$ with known prior distribution. There are $N$ sensors making noisy observations about the hypothesis; $\mathcal{N} =\{1,2,\ldots,N\}$ denotes the set of sensors. Sensor $i$ can receive messages from a subset $\mathcal{P}^i \subset \mathcal{N}$ of sensors and send a message to a subset $\mathcal{C}^i \subset \mathcal{N}$. Each sensor is faced with a stopping problem. At each time $t$, based on the observations it has taken so far and the messages it may have received, sensor $i$ can decide to stop and communicate a binary decision to the sensors in $\mathcal{C}^i$, or it can continue taking observations and receiving messages. After sensor $i$'s binary decision has been sent, it becomes inactive. Sensors incur operational costs (cost of taking observations, communication costs etc.) while they are active. In addition, the system incurs a terminal cost that depends on the true hypothesis $H$, the sensors' binary decisions and their stopping times. The objective is to determine decision strategies for all sensors to minimize the total expected cost.
Iterative Detection for Compressive Sensing:Turbo CS
Venue: arXiv cs.IT 2014
Year: 2014

We consider compressive sensing as a source coding method for signal transmission. We concatenate a convolutional coding system with 1-bit compressive sensing to obtain a serial concatenated system model for sparse signal transmission over an AWGN channel. The proposed source/channel decoder, which we refer to as turbo CS, is robust against channel noise and its signal reconstruction performance at the receiver increases considerably through iterations. We show 12 dB improvement with six turbo CS iterations compared to a non-iterative concatenated source/channel decoder.
Routing protocols for mobile sensor networks: a comparative study
Venue: arXiv cs.NI 2014
Year: 2014

This paper presents a comparison of cluster-based position and non position-based routing protocols for mobile wireless sensor networks to outline design considerations of protocols for mobile environments. The selected protocols are compared on the basis of multiple parameters, which include packet delivery ratio, packet loss, network lifetime, and control overhead using variable number of nodes and speeds. The extensive simulation and analysis of results show that position-based routing protocols incur less packet loss as compared to the non position based protocols. However, position-based protocols require localization mechanism or a GPS for the location information, which consumes energy and affects the network lifetime. Alternatively, non position-based protocols are more energy efficient and provide extended network lifetime.
Cloud Computing Simulation Using CloudSim
Venue: arXiv cs.DC 2014
Year: 2014

As we know that Cloud Computing is a new paradigm in IT. It has many advantages and disadvantages. But in future it will spread in the whole world. Many researches are going on for securing the cloud services. Simulation is the act of imitating or pretending. It is a situation in which a particular set of condition is created artificially in order to study that could exit in reality. We need only a simple Operating System with some memory to startup our Computer. All our resources will be available in the cloud.
Channel Capacity Analysis of MIMO System in Correlated Nakagami-m Fading Environment
Venue: arXiv cs.IT 2014
Year: 2014

We consider Vertical Bell Laboratories Layered Space-Time (V-BLAST) systems in correlated multiple-input multiple-output (MIMO) Nakagami-m fading channels with equal power allocated to each transmit antenna and also we consider that the channel state information (CSI) is available only at the receiver. Now for practical application, study of the VBLAST MIMO system in correlated environment is necessary. In this paper, we present a detailed study of the channel capacity in correlated and uncorrelated channel condition and also validated the result with appropriate mathematical relation.
Beyond Batch Processing: Towards Real-Time and Streaming Big Data
Venue: arXiv cs.DC 2014
Year: 2014

Today, big data is generated from many sources and there is a huge demand for storing, managing, processing, and querying on big data. The MapReduce model and its counterpart open source implementation Hadoop, has proven itself as the de facto solution to big data processing. Hadoop is inherently designed for batch and high throughput processing jobs. Although Hadoop is very suitable for batch jobs but there is an increasing demand for non-batch processes on big data like: interactive jobs, real-time queries, and big data streams. Since Hadoop is not proper for these non-batch workloads, new solutions are proposed to these new challenges. In this article, we discuss two categories of these solutions: real-time processing, and stream processing for big data. For each category, we discuss paradigms, strengths and differences to Hadoop. We also introduce some practical systems and frameworks for each category. Finally, some simple experiments are done to show effectiveness of some solutions compared to available Hadoop-based solutions.
Aspects of Favorable Propagation in Massive MIMO
Venue: arXiv cs.IT 2014
Year: 2014

Favorable propagation, defined as mutual orthogonality among the vector-valued channels to the terminals, is one of the key properties of the radio channel that is exploited in Massive MIMO. However, there has been little work that studies this topic in detail. In this paper, we first show that favorable propagation offers the most desirable scenario in terms of maximizing the sum-capacity. One useful proxy for whether propagation is favorable or not is the channel condition number. However, this proxy is not good for the case where the norms of the channel vectors may not be equal. For this case, to evaluate how favorable the propagation offered by the channel is, we propose a ``distance from favorable propagation'' measure, which is the gap between the sum-capacity and the maximum capacity obtained under favorable propagation. Secondly, we examine how favorable the channels can be for two extreme scenarios: i.i.d. Rayleigh fading and uniform random line-of-sight (UR-LoS). Both environments offer (nearly) favorable propagation. Furthermore, to analyze the UR-LoS model, we propose an urns-and-balls model. This model is simple and explains the singular value spread characteristic of the UR-LoS model well.
The Input/Output Complexity of Sparse Matrix Multiplication
Venue: arXiv cs.DS 2014
Year: 2014

We consider the problem of multiplying sparse matrices (over a semiring) where the number of non-zero entries is larger than main memory. In the classical paper of Hong and Kung (STOC '81) it was shown that to compute a product of dense $U \times U$ matrices, $Θ\left(U^3 / (B \sqrt{M}) \right)$ I/Os are necessary and sufficient in the I/O model with internal memory size $M$ and memory block size $B$. In this paper we generalize the upper and lower bounds of Hong and Kung to the sparse case. Our bounds depend of the number $N = \mathtt{nnz}(A)+\mathtt{nnz}(C)$ of nonzero entries in $A$ and $C$, as well as the number $Z = \mathtt{nnz}(AC)$ of nonzero entries in $AC$. We show that $AC$ can be computed using $\tilde{O} \left(\tfrac{N}{B} \min\left(\sqrt{\tfrac{Z}{M}},\tfrac{N}{M}\right) \right)$ I/Os, with high probability. This is tight (up to polylogarithmic factors) when only semiring operations are allowed, even for dense rectangular matrices: We show a lower bound of $Ω\left(\tfrac{N}{B} \min\left(\sqrt{\tfrac{Z}{M}},\tfrac{N}{M}\right) \right)$ I/Os. While our lower bound uses fairly standard techniques, the upper bound makes use of ``compressed matrix multiplication'' sketches, which is new in the context of I/O-efficient algorithms, and a new matrix product size estimation technique that avoids the ``no cancellation'' assumption.
Generalized prisoner's dilemma
Venue: arXiv cs.GT 2014
Year: 2014

Prisoner's dilemma has been heavily studied. In classical model, each player chooses to either "Cooperate" or "Defect". In this paper, we generalize the prisoner's dilemma with a new alternative which is neither defect or cooperation. The classical model is the special case under the condition that the third state is not taken into consideration.
Universal Decoding for Gaussian Intersymbol Interference Channels
Venue: arXiv cs.IT 2014
Year: 2014

A universal decoding procedure is proposed for the intersymbol interference (ISI) Gaussian channels. The universality of the proposed decoder is in the sense of being independent of the various channel parameters, and at the same time, attaining the same random coding error exponent as the optimal maximum-likelihood (ML) decoder, which utilizes full knowledge of these unknown parameters. The proposed decoding rule can be regarded as a frequency domain version of the universal maximum mutual information (MMI) decoder. Contrary to previously suggested universal decoders for ISI channels, our proposed decoding metric can easily be evaluated.
Sensing Subjective Well-being from Social Media
Venue: arXiv cs.AI 2014
Year: 2014

Subjective Well-being(SWB), which refers to how people experience the quality of their lives, is of great use to public policy-makers as well as economic, sociological research, etc. Traditionally, the measurement of SWB relies on time-consuming and costly self-report questionnaires. Nowadays, people are motivated to share their experiences and feelings on social media, so we propose to sense SWB from the vast user generated data on social media. By utilizing 1785 users' social media data with SWB labels, we train machine learning models that are able to "sense" individual SWB from users' social media. Our model, which attains the state-by-art prediction accuracy, can then be used to identify SWB of large population of social media users in time with very low cost.
A lower bound on opaque sets
Venue: arXiv cs.CG 2014
Year: 2014

It is proved that the total length of any set of countably many rectifiable curves, whose union meets all straight lines that intersect the unit square U, is at least 2.00002. This is the first improvement on the lower bound of 2 established by Jones in 1964. A similar bound is proved for all convex sets U other than a triangle.
Truthful Mechanisms for Combinatorial AC Electric Power Allocation
Venue: arXiv cs.GT 2014
Year: 2014

Traditional studies of combinatorial auctions often only consider linear constraints (by which the demands for certain goods are limited by the corresponding supplies). The rise of smart grid presents a new class of auctions, characterized by quadratic constraints. Yu and Chau [AAMAS 13'] introduced the complex-demand knapsack problem, in which the demands are complex-valued and the capacity of supplies is described by the magnitude of total complex-valued demand. This naturally captures the power constraints in AC electric systems. In this paper, we provide a more complete study and generalize the problem to the multi-minded version, beyond the previously known 1/2-approximation algorithm for only a subclass of the problem. More precisely, we give a truthful PTAS for the case phi in [0,pi/2-delta], and a truthful FPTAS, which fully optimizes the objective function but violates the capacity constraint by at most (1+epsilon), for the case phi in (pi/2,pi-delta], where phi is the maximum angle between any two complex-valued demands and epsilon,delta>0 are arbitrarily small constants.
An Improved Apriori Algorithm for Association Rules
Venue: arXiv cs.DB 2014
Year: 2014

There are several mining algorithms of association rules. One of the most popular algorithms is Apriori that is used to extract frequent itemsets from large database and getting the association rule for discovering the knowledge. Based on this algorithm, this paper indicates the limitation of the original Apriori algorithm of wasting time for scanning the whole database searching on the frequent itemsets, and presents an improvement on Apriori by reducing that wasted time depending on scanning only some transactions. The paper shows by experimental results with several groups of transactions, and with several values of minimum support that applied on the original Apriori and our implemented improved Apriori that our improved Apriori reduces the time consumed by 67.38% in comparison with the original Apriori, and makes the Apriori algorithm more efficient and less time consuming.
Feedback Generation for Performance Problems in Introductory Programming Assignments
Venue: arXiv cs.PL 2014
Year: 2014

Providing feedback on programming assignments manually is a tedious, error prone, and time-consuming task. In this paper, we motivate and address the problem of generating feedback on performance aspects in introductory programming assignments. We studied a large number of functionally correct student solutions to introductory programming assignments and observed: (1) There are different algorithmic strategies, with varying levels of efficiency, for solving a given problem. These different strategies merit different feedback. (2) The same algorithmic strategy can be implemented in countless different ways, which are not relevant for reporting feedback on the student program. We propose a light-weight programming language extension that allows a teacher to define an algorithmic strategy by specifying certain key values that should occur during the execution of an implementation. We describe a dynamic analysis based approach to test whether a student's program matches a teacher's specification. Our experimental results illustrate the effectiveness of both our specification language and our dynamic analysis. On one of our benchmarks consisting of 2316 functionally correct implementations to 3 programming problems, we identified 16 strategies that we were able to describe using our specification language (in 95 minutes after inspecting 66, i.e., around 3%, implementations). Our dynamic analysis correctly matched each implementation with its corresponding specification, thereby automatically producing the intended feedback.
Hypothesis Elimination in Kleene Semirings
Venue: arXiv cs.LO 2014
Year: 2014

A Kleene semiring is an algebraic structure satisfying the axioms of Kleene algebra, minus the annihilation axioms (x.0 = 0 = 0.x). We show that Kleene semirings (like Kleene algebras) admit the efficient elimination of various kinds of equational hypotheses, in particular Hoare formulas (t=0, where t is an arbitrary term). Our method is purely proof-theoretic, and can be used to eliminate Horn hypotheses in any suitable Horn-equational theory. Moreover, it gives a simple condition under which hypotheses eliminations can be combined.
Convergence Time for Unbiased Quantized Consensus Over Static and Dynamic Networks
Venue: arXiv cs.SY 2014
Year: 2014

In this paper, the question of expected time to convergence is addressed for unbiased quantized consensus on undirected connected graphs, and some strong results are obtained. The paper first provides a tight expression for the expected convergence time of the unbiased quantized consensus over general but fixed networks. It is shown that the maximum expected convergence time lies within a constant factor of the maximum hitting time of an appropriate lazy random walk, using the theory of harmonic functions for reversible Markov chains. Following this, and using electric resistance analogy of the reversible Markov chains, the paper provides a tight upper bound for the expected convergence time to consensus based on the parameters of the network. Moreover, the paper identifies a precise order of the maximum expected convergence time for some simple graphs such as line graph and cycle. Finally, the results are extended to bound the expected convergence time of the underlying dynamics in time-varying networks. Modeling such dynamics as the evolution of a time inhomogeneous Markov chain, the paper derives a tight upper bound for expected convergence time of the dynamics using the spectral representation of the networks. This upper bound is significantly better than earlier results for the quantized consensus problem over time-varying graphs.
Bayesian Design of Tandem Networks for Distributed Detection With Multi-bit Sensor Decisions
Venue: arXiv cs.IT 2014
Year: 2014

We consider the problem of decentralized hypothesis testing under communication constraints in a topology where several peripheral nodes are arranged in tandem. Each node receives an observation and transmits a message to its successor, and the last node then decides which hypothesis is true. We assume that the observations at different nodes are, conditioned on the true hypothesis, independent and the channel between any two successive nodes is considered error-free but rate-constrained. We propose a cyclic numerical design algorithm for the design of nodes using a person-by-person methodology with the minimum expected error probability as a design criterion, where the number of communicated messages is not necessarily equal to the number of hypotheses. The number of peripheral nodes in the proposed method is in principle arbitrary and the information rate constraints are satisfied by quantizing the input of each node. The performance of the proposed method for different information rate constraints, in a binary hypothesis test, is compared to the optimum rate-one solution due to Swaszek and a method proposed by Cover, and it is shown numerically that increasing the channel rate can significantly enhance the performance of the tandem network. Simulation results for $M$-ary hypothesis tests also show that by increasing the channel rates the performance of the tandem network significantly improves.
Heisenberg Groups as Platform for the AAG key-exchange protocol
Venue: arXiv cs.CR 2014
Year: 2014

Garber, Kahrobaei, and Lam studied polycyclic groups generated by number field as platform for the AAG key-exchange protocol. In this paper, we discuss the use of a different kind of polycyclic groups, Heisenberg groups, as a platform group for AAG by submitting Heisenberg groups to one of AAG's major attacks, the length-based attack.
Learning Negative Mixture Models by Tensor Decompositions
Venue: arXiv cs.LG 2014
Year: 2014

This work considers the problem of estimating the parameters of negative mixture models, i.e. mixture models that possibly involve negative weights. The contributions of this paper are as follows. (i) We show that every rational probability distributions on strings, a representation which occurs naturally in spectral learning, can be computed by a negative mixture of at most two probabilistic automata (or HMMs). (ii) We propose a method to estimate the parameters of negative mixture models having a specific tensor structure in their low order observable moments. Building upon a recent paper on tensor decompositions for learning latent variable models, we extend this work to the broader setting of tensors having a symmetric decomposition with positive and negative weights. We introduce a generalization of the tensor power method for complex valued tensors, and establish theoretical convergence guarantees. (iii) We show how our approach applies to negative Gaussian mixture models, for which we provide some experiments.