OpenRaiser/Intern-Atlas huggingface dataset:
A Practical, Secure, and Verifiable Cloud Computing for Mobile Systems
Venue: arXiv cs.CR 2014
Year: 2014

Cloud computing systems, in which clients rent and share computing resources of third party platforms, have gained widespread use in recent years. Furthermore, cloud computing for mobile systems (i.e., systems in which the clients are mobile devices) have too been receiving considerable attention in technical literature. We propose a new method of delegating computations of resource-constrained mobile clients, in which multiple servers interact to construct an encrypted program known as garbled circuit. Next, using garbled inputs from a mobile client, another server executes this garbled circuit and returns the resulting garbled outputs. Our system assures privacy of the mobile client's data, even if the executing server chooses to collude with all but one of the other servers. We adapt the garbled circuit design of Beaver et al. and the secure multiparty computation protocol of Goldreich et al. for the purpose of building a secure cloud computing for mobile systems. Our method incorporates the novel use of the cryptographically secure pseudo random number generator of Blum et al. that enables the mobile client to efficiently retrieve the result of the computation, as well as to verify that the evaluator actually performed the computation. We analyze the server-side and client-side complexity of our system. Using real-world data, we evaluate our system for a privacy preserving search application that locates the nearest bank/ATM from the mobile client. We also measure the time taken to construct and evaluate the garbled circuit for varying number of servers, demonstrating the feasibility of our secure and verifiable cloud computing for mobile systems.
Approximation algorithms for the Transportation Problem with Market Choice and related models
Venue: arXiv cs.DS 2014
Year: 2014

Given facilities with capacities and clients with penalties and demands, the transportation problem with market choice consists in finding the minimum-cost way to partition the clients into unserved clients, paying the penalties, and into served clients, paying the transportation cost to serve them. We give polynomial-time reductions from this problem and variants to the (un)capacitated facility location problem, directly yielding approximation algorithms, two with constant factors in the metric case, one with a logarithmic factor in the general case.
Sampling and Galerkin reconstruction in reproducing kernel spaces
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we consider sampling in a reproducing kernel subspace of $L^p$. We introduce a pre-reconstruction operator associated with a sampling scheme and propose a Galerkin reconstruction in general Banach space setting. We show that the proposed Galerkin method provides a quasi-optimal approximation, and the corresponding Galerkin equations could be solved by an iterative approximation-projection algorithm. We also present detailed analysis and numerical simulations of the Galerkin method for reconstructing signals with finite rate of innovation.
On Optimizing Energy Efficiency in Multi-Radio Multi-Channel Wireless Networks
Venue: arXiv cs.NI 2014
Year: 2014

Multi-radio multi-channel (MR-MC) networks contribute significant enhancement in the network throughput by exploiting multiple radio interfaces and non-overlapping channels. While throughput optimization is one of the main targets in allocating resource in MR-MC networks, recently, the network energy efficiency is becoming a more and more important concern. Although turning on more radios and exploiting more channels for communication is always beneficial to network capacity, they may not be necessarily desirable from an energy efficiency perspective. The relationship between these two often conflicting objectives has not been well-studied in many existing works. In this paper, we investigate the problem of optimizing energy efficiency under full capacity operation in MR-MC networks and analyze the optimal choices of numbers of radios and channels. We provide detailed problem formulation and solution procedures. In particular, for homogeneous commodity networks, we derive a theoretical upper bound of the optimal energy efficiency and analyze the conditions under which such optimality can be achieved. Numerical results demonstrate that the achieved optimal energy efficiency is close to the theoretical upper bound.
Privacy Games
Venue: arXiv cs.GT 2014
Year: 2014

The problem of analyzing the effect of privacy concerns on the behavior of selfish utility-maximizing agents has received much attention lately. Privacy concerns are often modeled by altering the utility functions of agents to consider also their privacy loss. Such privacy aware agents prefer to take a randomized strategy even in very simple games in which non-privacy aware agents play pure strategies. In some cases, the behavior of privacy aware agents follows the framework of Randomized Response, a well-known mechanism that preserves differential privacy. Our work is aimed at better understanding the behavior of agents in settings where their privacy concerns are explicitly given. We consider a toy setting where agent A, in an attempt to discover the secret type of agent B, offers B a gift that one type of B agent likes and the other type dislikes. As opposed to previous works, B's incentive to keep her type a secret isn't the result of "hardwiring" B's utility function to consider privacy, but rather takes the form of a payment between B and A. We investigate three different types of payment functions and analyze B's behavior in each of the resulting games. As we show, under some payments, B's behavior is very different than the behavior of agents with hardwired privacy concerns and might even be deterministic. Under a different payment we show that B's BNE strategy does fall into the framework of Randomized Response.
On the Per-Sample Capacity of Nondispersive Optical Fibers
Venue: arXiv cs.IT 2014
Year: 2014

The capacity of the channel defined by the stochastic nonlinear Schrödinger equation, which includes the effects of the Kerr nonlinearity and amplified spontaneous emission noise, is considered in the case of zero dispersion. In the absence of dispersion, this channel behaves as a collection of parallel per-sample channels. The conditional probability density function of the nonlinear per-sample channels is derived using both a sum-product and a Fokker-Planck differential equation approach. It is shown that, for a fixed noise power, the per-sample capacity grows unboundedly with input signal. The channel can be partitioned into amplitude and phase subchannels, and it is shown that the contribution to the total capacity of the phase channel declines for large input powers. It is found that a two-dimensional distribution with a half-Gaussian profile on the amplitude and uniform phase provides a lower bound for the zero-dispersion optical fiber channel, which is simple and asymptotically capacity-achieving at high signal-to-noise ratios (SNRs). A lower bound on the capacity is also derived in the medium-SNR region. The exact capacity subject to peak and average power constraints is numerically quantified using dense multiple ring modulation formats. The differential model underlying the zero-dispersion channel is reduced to an algebraic model, which is more tractable for digital communication studies, and in particular it provides a relation between the zero-dispersion optical channel and a $2 \times 2$ multiple-input multiple-output Rician fading channel. It appears that the structure of the capacity-achieving input distribution resembles that of the Rician fading channel, i.e., it is discrete in amplitude with a finite number of mass points, while continuous and uniform in phase.
Approximate Exponential Algorithms to Solve the Chemical Master Equation
Venue: arXiv cs.NA 2014
Year: 2014

This paper discusses new simulation algorithms for stochastic chemical kinetics that exploit the linearity of the chemical master equation and its matrix exponential exact solution. These algorithms make use of various approximations of the matrix exponential to evolve probability densities in time. A sampling of the approximate solutions of the chemical master equation is used to derive accelerated stochastic simulation algorithms. Numerical experiments compare the new methods with the established stochastic simulation algorithm and the tau-leaping method.
Higher order Voronoi based mobile coverage control
Venue: arXiv cs.SY 2014
Year: 2014

Most current results on coverage control using mobile sensors require that one partitioned cell is the sole responsibility of one sensor. In this paper, we consider a class of generalized Voronoi coverage control problems by using higher order Voronoi partitions, motivated by applications that more than one senor is required to monitor and cover onecell. We introduce a framework depending on a coverage performance function incorporating higher order Voronoi cells and then design a gradient-based controller which allows the multi-sensor system to achieve a local equilibrium in a distributed manner. In addition, we provide a number of real world scenarios where our framework can be applied. Simulation results are also provided to show the controller performance.
Supervised learning Methods for Bangla Web Document Categorization
Venue: arXiv cs.CL 2014
Year: 2014

This paper explores the use of machine learning approaches, or more specifically, four supervised learning Methods, namely Decision Tree(C 4.5), K-Nearest Neighbour (KNN), Naïve Bays (NB), and Support Vector Machine (SVM) for categorization of Bangla web documents. This is a task of automatically sorting a set of documents into categories from a predefined set. Whereas a wide range of methods have been applied to English text categorization, relatively few studies have been conducted on Bangla language text categorization. Hence, we attempt to analyze the efficiency of those four methods for categorization of Bangla documents. In order to validate, Bangla corpus from various websites has been developed and used as examples for the experiment. For Bangla, empirical results support that all four methods produce satisfactory performance with SVM attaining good result in terms of high dimensional and relatively noisy document feature vectors.
An improved multimodal PSO method based on electrostatic interaction using n- nearest-neighbor local search
Venue: arXiv cs.AI 2014
Year: 2014

In this paper, an improved multimodal optimization (MMO) algorithm,called LSEPSO,has been proposed. LSEPSO combined Electrostatic Particle Swarm Optimization (EPSO) algorithm and a local search method and then made some modification on them. It has been shown to improve global and local optima finding ability of the algorithm. This algorithm useda modified local search to improve particle's personal best, which used n-nearest-neighbour instead of nearest-neighbour. Then, by creating n new points among each particle and n nearest particles, it tried to find a point which could be the alternative of particle's personal best. This method prevented particle's attenuation and following a specific particle by its neighbours. The performed tests on a number of benchmark functions clearly demonstrated that the improved algorithm is able to solve MMO problems and outperform other tested algorithms in this article.
Improved steady-state stability of power grids with a communication infrastructure
Venue: arXiv cs.SY 2014
Year: 2014

Efficient control of power systems is becoming increasingly difficult as they gain in complexity and size. We propose an automatic control strategy that regulates the mechanical power output of the generators in a power grid based on information obtained via a communication infrastructure. An algorithm that optimizes steady-state stability of a power grid by iteratively adding communication links is presented. The proposed control scheme is successfully applied to the IEEE New England and IEEE RTS 96 power systems, leading to a significant increase in the steady-state stability of the systems and an improvement in their overall robustness. The resulting communication network topology differs significantly from the transmission grid topology. This shows how complex the steady- state control for power systems is, influenced by the generators configuration, the transmission network topology, and the manner by which control is executed.
Towards EHR interoperability in Tanzania hospitals: Issues, Challenges and Opportunities
Venue: arXiv cs.CY 2014
Year: 2014

This study aimed at identifying the issue, challenges and opportunities from the health consumers in Tanzania towards interoperability of electronic health records. Recognizing that we conducted a study to identify the challenges, issues and opportunities towards health information exchange. The study was conducted in three major cities of Tanzania. This was in order to come up with a clear picture of how to implement some EHRs that will be trusted by health consumers. The participants (n=240) were surveyed on computer usage, EHRs knowledge, demographics, security and privacy issues. A total of 200 surveys were completed and returned (83.3% response rate). 67.5% were women, 62.6% had not heard of EHRs, 73% highly concerned about privacy and security of their information. 75% believed that introduction of various security mechanisms will make EHRs more secure. A number of chi-square tests (p<0.05) showed there was a strong relationship among the variable of age, computer use, EHRs knowledge and concerns for privacy and security. The study showed that there was a small difference of 8.5% between those who think EHRs are safer than paper records and those who think otherwise. The general observation of the study was that in order to make EHRs successful, then the issue of security, and health consumer involvement were two key towards the road of successful EHRs in our hospitals practices and that will make consumers more willing to allow their records to be shared.
Rise of the Rest: The Growing Impact of Non-Elite Journals
Venue: arXiv cs.DL 2014
Year: 2014

In this paper, we examine the evolution of the impact of non-elite journals. We attempt to answer two questions. First, what fraction of the top-cited articles are published in non-elite journals and how has this changed over time. Second, what fraction of the total citations are to non-elite journals and how has this changed over time. We studied citations to articles published in 1995-2013. We computed the 10 most-cited journals and the 1000 most-cited articles each year for all 261 subject categories in Scholar Metrics. We marked the 10 most-cited journals in a category as the elite journals for the category and the rest as non-elite. There are two conclusions from our study. First, the fraction of top-cited articles published in non-elite journals increased steadily over 1995-2013. While the elite journals still publish a substantial fraction of high-impact articles, many more authors of well-regarded papers in diverse research fields are choosing other venues. The number of top-1000 papers published in non-elite journals for the representative subject category went from 149 in 1995 to 245 in 2013, a growth of 64%. Looking at broad research areas, 4 out of 9 areas saw at least one-third of the top-cited articles published in non-elite journals in 2013. For 6 out of 9 areas, the fraction of top-cited papers published in non-elite journals for the representative subject category grew by 45% or more. Second, now that finding and reading relevant articles in non-elite journals is about as easy as finding and reading articles in elite journals, researchers are increasingly building on and citing work published everywhere. Considering citations to all articles, the percentage of citations to articles in non-elite journals went from 27% in 1995 to 47% in 2013. Six out of nine broad areas had at least 50% of citations going to articles published in non-elite journals in 2013.
Minimum Forcing Sets for Miura Folding Patterns
Venue: arXiv cs.DS 2014
Year: 2014

We introduce the study of forcing sets in mathematical origami. The origami material folds flat along straight line segments called creases, each of which is assigned a folding direction of mountain or valley. A subset $F$ of creases is forcing if the global folding mountain/valley assignment can be deduced from its restriction to $F$. In this paper we focus on one particular class of foldable patterns called Miura-ori, which divide the plane into congruent parallelograms using horizontal lines and zig-zag vertical lines. We develop efficient algorithms for constructing a minimum forcing set of a Miura-ori map, and for deciding whether a given set of creases is forcing or not. We also provide tight bounds on the size of a forcing set, establishing that the standard mountain-valley assignment for the Miura-ori is the one that requires the most creases in its forcing sets. Additionally, given a partial mountain/valley assignment to a subset of creases of a Miura-ori map, we determine whether the assignment domain can be extended to a locally flat-foldable pattern on all the creases. At the heart of our results is a novel correspondence between flat-foldable Miura-ori maps and $3$-colorings of grid graphs.
The single-crossing property on a tree
Venue: arXiv cs.GT 2014
Year: 2014

We generalize the classical single-crossing property to single-crossing property on trees and obtain new ways to construct Condorcet domains which are sets of linear orders which possess the property that every profile composed from those orders have transitive majority relation. We prove that for any tree there exist profiles that are single-crossing on that tree; moreover, that tree is minimal in this respect for at least one such profile. Finally, we provide a polynomial-time algorithm to recognize whether or not a given profile is single-crossing with respect to some tree. We also show that finding winners for Chamberlin-Courant rule is polynomial for profiles that are single-crossing on trees.
Analysis and Design of Finite Alphabet Iterative Decoders Robust to Faulty Hardware
Venue: arXiv cs.IT 2014
Year: 2014

This paper addresses the problem of designing LDPC decoders robust to transient errors introduced by a faulty hardware. We assume that the faulty hardware introduces errors during the message passing updates and we propose a general framework for the definition of the message update faulty functions. Within this framework, we define symmetry conditions for the faulty functions, and derive two simple error models used in the analysis. With this analysis, we propose a new interpretation of the functional Density Evolution threshold previously introduced, and show its limitations in case of highly unreliable hardware. However, we show that under restricted decoder noise conditions, the functional threshold can be used to predict the convergence behavior of FAIDs under faulty hardware. In particular, we reveal the existence of robust and non-robust FAIDs and propose a framework for the design of robust decoders. We finally illustrate robust and non-robust decoders behaviors of finite length codes using Monte Carlo simulations.
Local Policies for Efficiently Patrolling a Triangulated Region by a Robot Swarm
Venue: arXiv cs.RO 2014
Year: 2014

We present and analyze methods for patrolling an environment with a distributed swarm of robots. Our approach uses a physical data structure - a distributed triangulation of the workspace. A large number of stationary "mapping" robots cover and triangulate the environment and a smaller number of mobile "patrolling" robots move amongst them. The focus of this work is to develop, analyze, implement and compare local patrolling policies. We desire strategies that achieve full coverage, but also produce good coverage frequency and visitation times. Policies that provide theoretical guarantees for these quantities have received some attention, but gaps have remained. We present: 1) A summary of how to achieve coverage by building a triangulation of the workspace, and the ensuing properties. 2) A description of simple local policies (LRV, for Least Recently Visited and LFV, for Least Frequently Visited) for achieving coverage by the patrolling robots. 3) New analytical arguments why different versions of LRV may require worst case exponential time between visits of triangles. 4) Analytical evidence that a local implementation of LFV on the edges of the dual graph is possible in our scenario, and immensely better in the worst case. 5) Experimental and simulation validation for the practical usefulness of these policies, showing that even a small number of weak robots with weak local information can greatly outperform a single, powerful robots with full information and computational capabilities.
Computing minimum area homologies
Venue: arXiv cs.CG 2014
Year: 2014

Calculating and categorizing the similarity of curves is a fundamental problem which has generated much recent interest. However, to date there are no implementations of these algorithms for curves on surfaces with provable guarantees on the quality of the measure. In this paper, we present a similarity measure for any two cycles that are homologous, where we calculate the minimum area of any homology (or connected bounding chain) between the two cycles. The minimum area homology exists for broader classes of cycles than previous measures which are based on homotopy. It is also much easier to compute than previously defined measures, yielding an efficient implementation that is based on linear algebra tools. We demonstrate our algorithm on a range of inputs, showing examples which highlight the feasibility of this similarity measure.
Recommendation Scheme Based on Converging Properties for Contents Broadcasting
Venue: arXiv cs.MM 2014
Year: 2014

Popular videos are often clicked by a mount of users in a short period. With content recommendation, the popular contents could be broadcast to the potential users in wireless network, to save huge transmitting resource. In this paper, the contents propagation model is analyzed due to users' historical behavior, location, and the converging properties in wireless data transmission, with the users' communication log in the Chinese commercial cellular network. And a recommendation scheme is proposed to achieve high energy efficiency.
Weighted finite automata with output
Venue: arXiv cs.FL 2014
Year: 2014

In this paper we prove the equivalence of sequential, Mealy-type and Moore-type weighted finite automata with output, with respect to various semantics which are defined here.
A unified approach for multi-object triangulation, tracking and camera calibration
Venue: arXiv cs.CV 2014
Year: 2014

Object triangulation, 3-D object tracking, feature correspondence, and camera calibration are key problems for estimation from camera networks. This paper addresses these problems within a unified Bayesian framework for joint multi-object tracking and sensor registration. Given that using standard filtering approaches for state estimation from cameras is problematic, an alternative parametrisation is exploited, called disparity space. The disparity space-based approach for triangulation and object tracking is shown to be more effective than non-linear versions of the Kalman filter and particle filtering for non-rectified cameras. The approach for feature correspondence is based on the Probability Hypothesis Density (PHD) filter, and hence inherits the ability to update without explicit measurement association, to initiate new targets, and to discriminate between target and clutter. The PHD filtering approach then forms the basis of a camera calibration method from static or moving objects. Results are shown on simulated data.