OpenRaiser/Intern-Atlas huggingface dataset:
Additional Constructions to Solve the Generalized Russian Cards Problem using Combinatorial Designs
Venue: arXiv cs.CR 2014
Year: 2014

In the generalized Russian cards problem, we have a card deck $X$ of $n$ cards and three participants, Alice, Bob, and Cathy, dealt $a$, $b$, and $c$ cards, respectively. Once the cards are dealt, Alice and Bob wish to privately communicate their hands to each other via public announcements, without the advantage of a shared secret or public key infrastructure. Cathy should remain ignorant of all but her own cards after Alice and Bob have made their announcements. Notions for Cathy's ignorance in the literature range from Cathy not learning the fate of any individual card with certainty (weak $1$-security) to not gaining any probabilistic advantage in guessing the fate of some set of $δ$ cards (perfect $δ$-security). As we demonstrate, the generalized Russian cards problem has close ties to the field of combinatorial designs, on which we rely heavily, particularly for perfect security notions. Our main result establishes an equivalence between perfectly $δ$-secure strategies and $(c+δ)$-designs on $n$ points with block size $a$, when announcements are chosen uniformly at random from the set of possible announcements. We also provide construction methods and example solutions, including a construction that yields perfect $1$-security against Cathy when $c=2$. We leverage a known combinatorial design to construct a strategy with $a=8$, $b=13$, and $c=3$ that is perfectly $2$-secure. Finally, we consider a variant of the problem that yields solutions that are easy to construct and optimal with respect to both the number of announcements and level of security achieved. Moreover, this is the first method obtaining weak $δ$-security that allows Alice to hold an arbitrary number of cards and Cathy to hold a set of $c = \lfloor \frac{a-δ}{2} \rfloor$ cards. Alternatively, the construction yields solutions for arbitrary $δ$, $c$ and any $a \geq δ+ 2c$.
Equivalent relaxations of optimal power flow
Venue: arXiv cs.SY 2014
Year: 2014

Several convex relaxations of the optimal power flow (OPF) problem have recently been developed using both bus injection models and branch flow models. In this paper, we prove relations among three convex relaxations: a semidefinite relaxation that computes a full matrix, a chordal relaxation based on a chordal extension of the network graph, and a second-order cone relaxation that computes the smallest partial matrix. We prove a bijection between the feasible sets of the OPF in the bus injection model and the branch flow model, establishing the equivalence of these two models and their second-order cone relaxations. Our results imply that, for radial networks, all these relaxations are equivalent and one should always solve the second-order cone relaxation. For mesh networks, the semidefinite relaxation is tighter than the second-order cone relaxation but requires a heavier computational effort, and the chordal relaxation strikes a good balance. Simulations are used to illustrate these results.
On the Weight Distribution of Cyclic Codes with Niho Exponents
Venue: arXiv cs.IT 2014
Year: 2014

Recently, there has been intensive research on the weight distributions of cyclic codes. In this paper, we compute the weight distributions of three classes of cyclic codes with Niho exponents. More specifically, we obtain two classes of binary three-weight and four-weight cyclic codes and a class of nonbinary four-weight cyclic codes. The weight distributions follow from the determination of value distributions of certain exponential sums. Several examples are presented to show that some of our codes are optimal and some have the best known parameters.
Distributed Cloud Computing Environment Enhanced with Capabilities for Wide-Area Migration and Replication of Virtual Machines
Venue: arXiv cs.DC 2014
Year: 2014

When a network application is implmented as a virtual machine on a cloud and is used by a large number of users, the location of the virtual machine should be selected carefully so that the response time experienced by users is minimized. As the user population moves and/or increases, the virtual machine may need to be migrated to a new location or replicated on many locations over a wide-area network. Virtual machine migration and replication have been studied extensively but in most cases are limited within a subnetwork to be able to maintain service continuity. In this paper we introduce a distributed cloud computing environment which facilitates the migration and replication of a virtual machine over a wide area network. The mechanism is provided by an overlay network of smart routers, each of which connects a cooperating data center to the Internet. The proposed approach is analyzed and compared with related works
A logic for reasoning about ambiguity
Venue: arXiv cs.AI 2014
Year: 2014

Standard models of multi-agent modal logic do not capture the fact that information is often \emph{ambiguous}, and may be interpreted in different ways by different agents. We propose a framework that can model this, and consider different semantics that capture different assumptions about the agents' beliefs regarding whether or not there is ambiguity. We examine the expressive power of logics of ambiguity compared to logics that cannot model ambiguity, with respect to the different semantics that we propose.
Enhancement performance of road recognition system of autonomous robots in shadow scenario
Venue: arXiv cs.RO 2014
Year: 2014

Road region recognition is a main feature that is gaining increasing attention from intellectuals because it helps autonomous vehicle to achieve a successful navigation without accident. However, different techniques based on camera sensor have been used by various researchers and outstanding results have been achieved. Despite their success, environmental noise like shadow leads to inaccurate recognition of road region which eventually leads to accident for autonomous vehicle. In this research, we conducted an investigation on shadow and its effects, optimized the road region recognition system of autonomous vehicle by introducing an algorithm capable of detecting and eliminating the effects of shadow. The experimental performance of our system was tested and compared using the following schemes: Total Positive Rate (TPR), False Negative Rate (FNR), Total Negative Rate (TNR), Error Rate (ERR) and False Positive Rate (FPR). The performance result of the system improved on road recognition in shadow scenario and this advancement has added tremendously to successful navigation approaches for autonomous vehicle.
A Bi-Scheduler Algorithm for Frame Aggregation in IEEE 802.11n
Venue: arXiv cs.NI 2014
Year: 2014

IEEE 802.11n mainly aims to provide high throughput, reliability and good security over its other previous standards. The performance of 802.11n is very effective on the saturated traffic through the use of frame aggregation. But this frame aggregation will not effectively function in all scenarios. The main objective of this paper is to improve the throughput of the wireless LAN through effective frame aggregation using scheduler mechanism. The Bi-Scheduler algorithm proposed in this article aims to segregate frames based on their access categories. The outer scheduler separates delay sensitive applications from the incoming burst of multi-part data and also decides whether to apply Aggregated - MAC Service Data Unit (A-MSDU) aggregation technique or to send the data without any aggregation. The inner scheduler schedules the remaining (delay-insensitive, background and best-effort) packets using Aggregated-MAC Protocol Data unit (A-MPDU) aggregation technique
On the Nearest Neighbor Rule for the Metric Traveling Salesman Problem
Venue: arXiv cs.DS 2014
Year: 2014

We present a very simple family of traveling salesman instances with $n$ cities where the nearest neighbor rule may produce a tour that is $Θ(\log n)$ times longer than an optimum solution. Our family works for the graphic, the euclidean, and the rectilinear traveling salesman problem at the same time. It improves the so far best known lower bound in the euclidean case and proves for the first time a lower bound in the rectilinear case.
A Comparative Study of Reservoir Computing for Temporal Signal Processing
Venue: arXiv cs.NE 2014
Year: 2014

Reservoir computing (RC) is a novel approach to time series prediction using recurrent neural networks. In RC, an input signal perturbs the intrinsic dynamics of a medium called a reservoir. A readout layer is then trained to reconstruct a target output from the reservoir's state. The multitude of RC architectures and evaluation metrics poses a challenge to both practitioners and theorists who study the task-solving performance and computational power of RC. In addition, in contrast to traditional computation models, the reservoir is a dynamical system in which computation and memory are inseparable, and therefore hard to analyze. Here, we compare echo state networks (ESN), a popular RC architecture, with tapped-delay lines (DL) and nonlinear autoregressive exogenous (NARX) networks, which we use to model systems with limited computation and limited memory respectively. We compare the performance of the three systems while computing three common benchmark time series: H{é}non Map, NARMA10, and NARMA20. We find that the role of the reservoir in the reservoir computing paradigm goes beyond providing a memory of the past inputs. The DL and the NARX network have higher memorization capability, but fall short of the generalization power of the ESN.
A Survey on optimization approaches to text document clustering
Venue: arXiv cs.IR 2014
Year: 2014

Text Document Clustering is one of the fastest growing research areas because of availability of huge amount of information in an electronic form. There are several number of techniques launched for clustering documents in such a way that documents within a cluster have high intra-similarity and low inter-similarity to other clusters. Many document clustering algorithms provide localized search in effectively navigating, summarizing, and organizing information. A global optimal solution can be obtained by applying high-speed and high-quality optimization algorithms. The optimization technique performs a globalized search in the entire solution space. In this paper, a brief survey on optimization approaches to text document clustering is turned out.
Collaborative learning model with virtual team in ubiquitous learning environment using creative problem solving process
Venue: arXiv cs.CY 2014
Year: 2014

The purposes of this research study were: 1) to develop a Collaborative Learning Model with Virtual Team in u-Learning Environment using Creative Problem-solving Process(U-CCPS Model); 2) to evaluate a U-CCPS Model. The research procedures were divided into two phases. The first phase was to develop U-CCPS Model, and the second phase was to evaluate U-CCPS Model. The sample group in this study consisted of five experts using purposive sampling. Data were analyzed by arithmetic mean and standard deviation. The research findings were as follows: The U-CCPS learning Model consisted of five components as follows: 1) Input factors, 2) Process, 3) Control, 4) Output and 5) Feedback. The input factors consisted of four components as followed: 1) Objectives of U-CCPS Model, 2) Roles of Instructors, 3) Roles of learners and 4) Design of learning media. The process consisted of two components as followed: 1) Preparation before learning, and 2) Instructional management process. The experts agree that a U-CCPS Model was highest suitability.
General Impossibility of Group Homomorphic Encryption in the Quantum World
Venue: arXiv cs.CR 2014
Year: 2014

Group homomorphic encryption represents one of the most important building blocks in modern cryptography. It forms the basis of widely-used, more sophisticated primitives, such as CCA2-secure encryption or secure multiparty computation. Unfortunately, recent advances in quantum computation show that many of the existing schemes completely break down once quantum computers reach maturity (mainly due to Shor's algorithm). This leads to the challenge of constructing quantum-resistant group homomorphic cryptosystems. In this work, we prove the general impossibility of (abelian) group homomorphic encryption in the presence of quantum adversaries, when assuming the IND-CPA security notion as the minimal security requirement. To this end, we prove a new result on the probability of sampling generating sets of finite (sub-)groups if sampling is done with respect to an arbitrary, unknown distribution. Finally, we provide a sufficient condition on homomorphic encryption schemes for our quantum attack to work and discuss its satisfiability in non-group homomorphic cases. The impact of our results on recent fully homomorphic encryption schemes poses itself as an open question.
Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs
Venue: arXiv cs.CC 2014
Year: 2014

Building on work of Cai, Fürer, and Immerman \cite{CFI92}, we show two hardness results for the Graph Isomorphism problem. First, we show that there are pairs of nonisomorphic $n$-vertex graphs $G$ and $H$ such that any sum-of-squares (SOS) proof of nonisomorphism requires degree $Ω(n)$. In other words, we show an $Ω(n)$-round integrality gap for the Lasserre SDP relaxation. In fact, we show this for pairs $G$ and $H$ which are not even $(1-10^{-14})$-isomorphic. (Here we say that two $n$-vertex, $m$-edge graphs $G$ and $H$ are $α$-isomorphic if there is a bijection between their vertices which preserves at least $αm$ edges.) Our second result is that under the {\sc R3XOR} Hypothesis \cite{Fei02} (and also any of a class of hypotheses which generalize the {\sc R3XOR} Hypothesis), the \emph{robust} Graph Isomorphism problem is hard. I.e.\ for every $ε> 0$, there is no efficient algorithm which can distinguish graph pairs which are $(1-ε)$-isomorphic from pairs which are not even $(1-ε_0)$-isomorphic for some universal constant $ε_0$. Along the way we prove a robust asymmetry result for random graphs and hypergraphs which may be of independent interest.
A Prediction Model for the Probability of SLA Matching in Consumer Provider Contracting of Web Services
Venue: arXiv cs.DC 2014
Year: 2014

Future e-business models will rely on electronic contracts which are agreed dynamically and adaptively by web services. Thus, the automatic negotiation of Service Level Agreements (SLAs) between consumers and providers is key for enabling service-based value chains. The process of finding appropriate providers for web services seems to be simple. Consumers contact several providers and take the provider which offers the best matching SLA. However, currently consumers are not able forecasting the probability of finding a matching provider for their requested SLA. So consumers contact several providers and check if their offers are matching. In case of continuing faults, on the one hand consumers may adapt their Service Level Objects (SLOs) of the required SLA or on the other hand simply accept offered SLAs of the contacted providers. By forecasting the probability of finding a matching provider, consumers could assess their chances of finding a provider offering the requested SLA. If a low probability is predicted, consumers can immediately adapt their SLOs or increase the numbers of providers to be contacted. Thus, this paper proposes an analytical forecast model, which allows consumers to get a realistic assessment of the probability to find matching providers. Additionally, we present an optimization algorithm based on the forecast results, which allows adapting the SLO parameter ranges in order to find at least one matching provider. Not only consumers, but also providers can use this forecast model to predict the prospective demand. So providers are able to assess the number of potential consumers based on their offers too. Justification of our approach is done by simulation of practical examples checking our theoretical findings.
Dempster-Shafer Theory for Move Prediction in Start Kicking of The Bicycle Kick of Sepak Takraw Game
Venue: arXiv cs.AI 2014
Year: 2014

This paper presents Dempster-Shafer theory for move prediction in start kicking of the bicycle kick of sepak takraw game. Sepak takraw is a highly complex net-barrier kicking sport that involves dazzling displays of quick reflexes, acrobatic twists, turns and swerves of the agile human body movement. A Bicycle kick or Scissor kick is a physical move made by throwing the body up into the air, making a shearing movement with the legs to get one leg in front of the other without holding on to the ground. Specifically, this paper considers bicycle kick of sepak takraw game in start kicking of the ball with uncertainty where player has different awareness regarding the contingencies. We have chosen Dempster-Shafer theory because the advantages of the Dempster-Shafer theory which include the ability to model information in a flexible way without requiring a probability to be assigned to each element in a set, providing a convenient and simple mechanism for combining two or more pieces of evidence under certain conditions, it can model ignorance explicitly, rejection of the law of additivity for belief in disjoint propositions.
A General Construction of Binary Sequences with Optimal Autocorrelation
Venue: arXiv cs.IT 2014
Year: 2014

A general construction of binary sequences with low autocorrelation are considered in the paper. Based on recent progresses about this topic and this construction, several classes of binary sequences with optimal autocorrelation and other low autocorrelation are presented.
Reliability Analysis to overcome Black Hole Attack in Wireless Sensor Network
Venue: arXiv cs.NI 2014
Year: 2014

Wireless sensor networks are vulnerable to several attacks, one of them being the black hole attack. A black hole is a malicious node that attracts all the traffic in the network by advertising that it has the shortest path in the network. Once it receives the packet from other nodes, it drops all the packets causing loss of critical information. In this paper we propose a reliability analysis mechanism. The proposed reliability analysis scheme overcomes the shortcomings of existing cooperative black hole attack using AODV routing protocol. As soon as there is a path available for routing, its reliability is checked using the proposed scheme. The proposed reliability analysis scheme helps in achieving maximum reliability by minimizing the complexity of the system. The final path available after the reliability analysis using the proposed scheme will make the path secure enough to minimize the packet loss, end-to-end delay and the energy utilization of the network as well as maximize the network lifetime in return.
Performance Study of Mobile TV over Mobile WiMAX Considering Different Modulation and Coding Techniques
Venue: arXiv cs.NI 2014
Year: 2014

With the advent of the wide-spread use of smart phones, video streaming over mobile wireless networks has suddenly taken a huge surge in recent years. Considering its enormous potential, mobile WiMAX is emerging as a viable technology for mobile TV which is expected to become of key importance in the future of mobile indus- try. In this paper, a simulation performance study of Mobile TV over mobile WiMAX is conducted with different types of adaptive modulation and coding taking into account key system and environment parameters which include the variation in the speed of the mobile, path-loss, scheduling service classes with the fixed type of mod- ulations. Our simulation has been conducted using OPNET simulation. Simulation results show that dynamic adaptation of modulation and coding schemes based onchannel conditions can offer considerably more en- hanced QoS and at the same time reduce the overall bandwidthof the system.
Testing for Synchronization
Venue: arXiv cs.FL 2014
Year: 2014

We consider the first problem that appears in any application of synchronizing automata, namely, the problem of deciding whether or not a given $n$-state $k$-letter automaton is synchronizing. First we generalize results from \cite{RandSynch},\cite{On2Problems} for the case of strongly connected partial automata. Specifically, for $k>1$ we show that an automaton is synchronizing with probability $1-O(\frac{1}{n^{0.5k}})$ and present an algorithm with linear in $n$ expected time, while the best known algorithm is quadratic on each instance. This results are interesting due to their applications in synchronization of finite state information sources. After that we consider the synchronization of reachable partial automata that has application for splicing systems in computational biology. For this case we prove that the problem of testing a given automaton for synchronization is NP-complete.
A Proof of Kamp's theorem
Venue: arXiv cs.LO 2014
Year: 2014

We provide a simple proof of Kamp's theorem.
Differentially Private Distributed Optimization
Venue: arXiv cs.CR 2014
Year: 2014

In distributed optimization and iterative consensus literature, a standard problem is for $N$ agents to minimize a function $f$ over a subset of Euclidean space, where the cost function is expressed as a sum $\sum f_i$. In this paper, we study the private distributed optimization (PDOP) problem with the additional requirement that the cost function of the individual agents should remain differentially private. The adversary attempts to infer information about the private cost functions from the messages that the agents exchange. Achieving differential privacy requires that any change of an individual's cost function only results in unsubstantial changes in the statistics of the messages. We propose a class of iterative algorithms for solving PDOP, which achieves differential privacy and convergence to the optimal value. Our analysis reveals the dependence of the achieved accuracy and the privacy levels on the the parameters of the algorithm. We observe that to achieve $ε$-differential privacy the accuracy of the algorithm has the order of $O(\frac{1}{ε^2})$.
Computer model of teaching with the varied coefficient of forgetting
Venue: arXiv cs.CY 2014
Year: 2014

At computer modeling of process of training it is usually supposed that all elements of a training material are forgotten with an identical speed. But in practice that knowledge which are included in educational activity of the pupil are remembered much more strongly and forgotten more slowly then knowledge which he doesn't use. For the purpose of more exact research of didactic systems is offered the model of training, in which consider that in case increasing the number of applications of this element of a learning material: 1) duration of its use by the pupil decreases; 2) the coefficient of forgetting decreases. The computer model is considered, programs in the Pascal language are submitted, results of modeling are given and analyzed. Keywords: didactics, information and cybernetic approach, computer modeling of process of training.