OpenRaiser/Intern-Atlas huggingface dataset:
A Model for Adversarial Wiretap Channel
Venue: arXiv cs.CR 2014
Year: 2014

In wiretap model of secure communication the goal is to provide (asymptotic) perfect secrecy and reliable communication over a noisy channel that is eavesdropped by an adversary with unlimited computational power. This goal is achieved by taking advantage of the channel noise and without requiring a shared key. The model has attracted attention in recent years because it captures eavesdropping attack in wireless communication. The wiretap adversary is a passive eavesdropping adversary at the physical layer of communication. In this paper we propose a model for adversarial wiretap (AWTP) channel that models active adversaries at this layer. We consider a $(ρ_r, ρ_w)$ wiretap adversary who can see a fraction $ρ_r$, and modify a fraction $ρ_w$, of the sent codeword. The code components that are read and/or modified can be chosen adaptively, and the subsets of read and modified components in general, can be different. AWTP codes provide secrecy and reliability for communication over these channels. We give security and reliability definitions and measures for these codes, and define secrecy capacity of an AWTP channel that represents the secrecy potential of the channel. The paper has two main contributions. First, we prove a tight upper bound on the rate of AWTP codes with perfect secrecy for $(ρ_r, ρ_w)$-AWTP channels, and use the bound to derive the secrecy capacity of the channel. We prove a similar bound for $ε$-secure codes also, but in this case the bound is not tight. Second, we give an explicit construction for a capacity achieving AWTP code family, and prove its security and efficiency properties. We show that AWTP model is a natural generalization of Wyner's wiretap models and somewhat surprisingly, also provides a direct generalization for a seemingly unrelated cryptographic primitive, Secure Message Transmission (SMT).
Nonparametric Weight Initialization of Neural Networks via Integral Representation
Venue: arXiv cs.LG 2014
Year: 2014

A new initialization method for hidden parameters in a neural network is proposed. Derived from the integral representation of the neural network, a nonparametric probability distribution of hidden parameters is introduced. In this proposal, hidden parameters are initialized by samples drawn from this distribution, and output parameters are fitted by ordinary linear regression. Numerical experiments show that backpropagation with proposed initialization converges faster than uniformly random initialization. Also it is shown that the proposed method achieves enough accuracy by itself without backpropagation in some cases.
The Lasserre Hierarchy in Almost Diagonal Form
Venue: arXiv cs.DS 2014
Year: 2014

The Lasserre hierarchy is a systematic procedure for constructing a sequence of increasingly tight relaxations that capture the convex formulations used in the best available approximation algorithms for a wide variety of optimization problems. Despite the increasing interest, there are very few techniques for analyzing Lasserre integrality gaps. Satisfying the positive semi-definite requirement is one of the major hurdles to constructing Lasserre gap examples. We present a novel characterization of the Lasserre hierarchy based on moment matrices that differ from diagonal ones by matrices of rank one (almost diagonal form). We provide a modular recipe to obtain positive semi-definite feasibility conditions by iteratively diagonalizing rank one matrices. Using this, we prove strong lower bounds on integrality gaps of Lasserre hierarchy for two basic capacitated covering problems. For the min-knapsack problem, we show that the integrality gap remains arbitrarily large even at level $n-1$ of Lasserre hierarchy. For the min-sum of tardy jobs scheduling problem, we show that the integrality gap is unbounded at level $Ω(\sqrt{n})$ (even when the objective function is integrated as a constraint). These bounds are interesting on their own, since both problems admit FPTAS.
Distributed Policy Evaluation Under Multiple Behavior Strategies
Venue: arXiv cs.MA 2014
Year: 2014

We apply diffusion strategies to develop a fully-distributed cooperative reinforcement learning algorithm in which agents in a network communicate only with their immediate neighbors to improve predictions about their environment. The algorithm can also be applied to off-policy learning, meaning that the agents can predict the response to a behavior different from the actual policies they are following. The proposed distributed strategy is efficient, with linear complexity in both computation time and memory footprint. We provide a mean-square-error performance analysis and establish convergence under constant step-size updates, which endow the network with continuous learning capabilities. The results show a clear gain from cooperation: when the individual agents can estimate the solution, cooperation increases stability and reduces bias and variance of the prediction error; but, more importantly, the network is able to approach the optimal solution even when none of the individual agents can (e.g., when the individual behavior policies restrict each agent to sample a small portion of the state space).
Critical connectedness of thin arithmetical discrete planes
Venue: arXiv cs.DM 2014
Year: 2014

An arithmetical discrete plane is said to have critical connecting thickness if its thickness is equal to the infimum of the set of values that preserve its $2$-connectedness. This infimum thickness can be computed thanks to the fully subtractive algorithm. This multidimensional continued fraction algorithm consists, in its linear form, in subtracting the smallest entry to the other ones. We provide a characterization of the discrete planes with critical thickness that have zero intercept and that are $2$-connected. Our tools rely on the notion of dual substitution which is a geometric version of the usual notion of substitution acting on words. We associate with the fully subtractive algorithm a set of substitutions whose incidence matrix is provided by the matrices of the algorithm, and prove that their geometric counterparts generate arithmetic discrete planes.
Parallel Algorithms for Geometric Graph Problems
Venue: arXiv cs.DS 2014
Year: 2014

We give algorithms for geometric graph problems in the modern parallel models inspired by MapReduce. For example, for the Minimum Spanning Tree (MST) problem over a set of points in the two-dimensional space, our algorithm computes a $(1+ε)$-approximate MST. Our algorithms work in a constant number of rounds of communication, while using total space and communication proportional to the size of the data (linear space and near linear time algorithms). In contrast, for general graphs, achieving the same result for MST (or even connectivity) remains a challenging open problem, despite drawing significant attention in recent years. We develop a general algorithmic framework that, besides MST, also applies to Earth-Mover Distance (EMD) and the transportation cost problem. Our algorithmic framework has implications beyond the MapReduce model. For example it yields a new algorithm for computing EMD cost in the plane in near-linear time, $n^{1+o_ε(1)}$. We note that while recently Sharathkumar and Agarwal developed a near-linear time algorithm for $(1+ε)$-approximating EMD, our algorithm is fundamentally different, and, for example, also solves the transportation (cost) problem, raised as an open question in their work. Furthermore, our algorithm immediately gives a $(1+ε)$-approximation algorithm with $n^δ$ space in the streaming-with-sorting model with $1/δ^{O(1)}$ passes. As such, it is tempting to conjecture that the parallel models may also constitute a concrete playground in the quest for efficient algorithms for EMD (and other similar problems) in the vanilla streaming model, a well-known open problem.
Large Aperiodic Semigroups
Venue: arXiv cs.FL 2014
Year: 2014

The syntactic complexity of a regular language is the size of its syntactic semigroup. This semigroup is isomorphic to the transition semigroup of the minimal deterministic finite automaton accepting the language, that is, to the semigroup generated by transformations induced by non-empty words on the set of states of the automaton. In this paper we search for the largest syntactic semigroup of a star-free language having $n$ left quotients; equivalently, we look for the largest transition semigroup of an aperiodic finite automaton with $n$ states. We introduce two new aperiodic transition semigroups. The first is generated by transformations that change only one state; we call such transformations and resulting semigroups unitary. In particular, we study complete unitary semigroups which have a special structure, and we show that each maximal unitary semigroup is complete. For $n \ge 4$ there exists a complete unitary semigroup that is larger than any aperiodic semigroup known to date. We then present even larger aperiodic semigroups, generated by transformations that map a non-empty subset of states to a single state; we call such transformations and semigroups semiconstant. In particular, we examine semiconstant tree semigroups which have a structure based on full binary trees. The semiconstant tree semigroups are at present the best candidates for largest aperiodic semigroups. We also prove that $2^n-1$ is an upper bound on the state complexity of reversal of star-free languages, and resolve an open problem about a special case of state complexity of concatenation of star-free languages.
Sixsoid: A new paradigm for $k$-coverage in 3D Wireless Sensor Networks
Venue: arXiv cs.NI 2014
Year: 2014

Coverage in 3D wireless sensor network (WSN) is always a very critical issue to deal with. Coming up with good coverage models implies more energy efficient networks. $K$-coverage is one model that ensures that every point in a given 3D Field of Interest (FoI) is guaranteed to be covered by $k$ sensors. When it comes to 3D, coming up with a deployment of sensors that gurantees $k$-coverage becomes much more complicated than in 2D. The basic idea is to come up with a geometrical shape that is guaranteed to be $k$-covered by taking a specific arrangement of sensors, and then fill the FoI will non-overlapping copies of this shape. In this work, we propose a new shape for the 3D scenario which we call a \textbf{Devilsoid}. Prior to this work, the shape which was proposed for coverage in 3D was the so called \textbf{Reuleaux Tetrahedron}. Our construction is motivated from a construction that can be applied to the 2D version of the problem \cite{MS} in which it imples better guarantees over the \textbf{Reuleaux Triangle}. Our contribution in this paper is twofold, firstly we show how Devilsoid gurantees more coverage volume over Reuleaux Tetrahedron, secondly we show how Devilsoid also guarantees simpler and more pragmatic deployment strategy for 3D wireless sensor networks. In this paper, we show the constuction of Devilsoid, calculate its volume and discuss its effect on the $k$-coverage in WSN.
Twofold fast summation
Venue: arXiv cs.NA 2014
Year: 2014

Debugging accumulation of floating-point errors is hard; ideally, computer should track it automatically. Here we consider twofold approximation of an exact real with value + error pair of floating-point numbers. Normally, value + error sum is more accurate than value alone, so error can estimate deviation between value and its exact target. Fast summation algorithm, that provides twofold sum of x[1]+...+x[N] or dot product x[1]*y[1]+...+x[N]*y[N], can be same fast as direct summation sometimes if leveraging processor underused potential. This way, we can hit three goals: improve precision, track inaccuracy, and do this with little if any loss in performance.
Design of a GIS-based Assistant Software Agent for the Incident Commander to Coordinate Emergency Response Operations
Venue: arXiv cs.MA 2014
Year: 2014

Problem: This paper addresses the design of an intelligent software system for the IC (incident commander) of a team in order to coordinate actions of agents (field units or robots) in the domain of emergency/crisis response operations. Objective: This paper proposes GICoordinator. It is a GIS-based assistant software agent that assists and collaborates with the human planner in strategic planning and macro tasks assignment for centralized multi-agent coordination. Method: Our approach to design GICoordinator was to: analyze the problem, design a complete data model, design an architecture of GICoordinator, specify required capabilities of human and system in coordination problem solving, specify development tools, and deploy. Result: The result was an architecture/design of GICoordinator that contains system requirements. Findings: GICoordinator efficiently integrates geoinformatics with artifice intelligent techniques in order to provide a spatial intelligent coordinator system for an IC to efficiently coordinate and control agents by making macro/strategic decisions. Results define a framework for future works to develop this system.
Optimal Random Access and Random Spectrum Sensing for an Energy Harvesting Cognitive Radio with and without Primary Feedback Leveraging
Venue: arXiv cs.IT 2014
Year: 2014

We consider a secondary user (SU) with energy harvesting capability. We design access schemes for the SU which incorporate random spectrum sensing and random access, and which make use of the primary automatic repeat request (ARQ) feedback. We study two problem-formulations. In the first problem-formulation, we characterize the stability region of the proposed schemes. The sensing and access probabilities are obtained such that the secondary throughput is maximized under the constraints that both the primary and secondary queues are stable. Whereas in the second problem-formulation, the sensing and access probabilities are obtained such that the secondary throughput is maximized under the stability of the primary queue and that the primary queueing delay is kept lower than a specified value needed to guarantee a certain quality of service (QoS) for the primary user (PU). We consider spectrum sensing errors and assume multipacket reception (MPR) capabilities. Numerical results show the enhanced performance of our proposed systems.
Selection Lemmas for various geometric objects
Venue: arXiv cs.CG 2014
Year: 2014

Selection lemmas are classical results in discrete geometry that have been well studied and have applications in many geometric problems like weak epsilon nets and slimming Delaunay triangulations. Selection lemma type results typically show that there exists a point that is contained in many objects that are induced (spanned) by an underlying point set. In the first selection lemma, we consider the set of all the objects induced (spanned) by a point set $P$. This question has been widely explored for simplices in $\mathbb{R}^d$, with tight bounds in $\mathbb{R}^2$. In our paper, we prove first selection lemma for other classes of geometric objects. We also consider the strong variant of this problem where we add the constraint that the piercing point comes from $P$. We prove an exact result on the strong and the weak variant of the first selection lemma for axis-parallel rectangles, special subclasses of axis-parallel rectangles like quadrants and slabs, disks (for centrally symmetric point sets). We also show non-trivial bounds on the first selection lemma for axis-parallel boxes and hyperspheres in $\mathbb{R}^d$. In the second selection lemma, we consider an arbitrary $m$ sized subset of the set of all objects induced by $P$. We study this problem for axis-parallel rectangles and show that there exists an point in the plane that is contained in $\frac{m^3}{24n^4}$ rectangles. This is an improvement over the previous bound by Smorodinsky and Sharir when $m$ is almost quadratic.
Sphere Packing with Limited Overlap
Venue: arXiv cs.CG 2014
Year: 2014

The classical sphere packing problem asks for the best (infinite) arrangement of non-overlapping unit balls which cover as much space as possible. We define a generalized version of the problem, where we allow each ball a limited amount of overlap with other balls. We study two natural choices of overlap measures and obtain the optimal lattice packings in a parameterized family of lattices which contains the FCC, BCC, and integer lattice.
Low-Complexity Particle Swarm Optimization for Time-Critical Applications
Venue: arXiv cs.NE 2014
Year: 2014

Particle swam optimization (PSO) is a popular stochastic optimization method that has found wide applications in diverse fields. However, PSO suffers from high computational complexity and slow convergence speed. High computational complexity hinders its use in applications that have limited power resources while slow convergence speed makes it unsuitable for time critical applications. In this paper, we propose two techniques to overcome these limitations. The first technique reduces the computational complexity of PSO while the second technique speeds up its convergence. These techniques can be applied, either separately or in conjunction, to any existing PSO variant. The proposed techniques are robust to the number of dimensions of the optimization problem. Simulation results are presented for the proposed techniques applied to the standard PSO as well as to several PSO variants. The results show that the use of both these techniques in conjunction results in a reduction in the number of computations required as well as faster convergence speed while maintaining an acceptable error performance for time-critical applications.
Natural Language Processing in Biomedicine: A Unified System Architecture Overview
Venue: arXiv cs.CL 2014
Year: 2014

In modern electronic medical records (EMR) much of the clinically important data - signs and symptoms, symptom severity, disease status, etc. - are not provided in structured data fields, but rather are encoded in clinician generated narrative text. Natural language processing (NLP) provides a means of "unlocking" this important data source for applications in clinical decision support, quality assurance, and public health. This chapter provides an overview of representative NLP systems in biomedicine based on a unified architectural view. A general architecture in an NLP system consists of two main components: background knowledge that includes biomedical knowledge resources and a framework that integrates NLP tools to process text. Systems differ in both components, which we will review briefly. Additionally, challenges facing current research efforts in biomedical NLP include the paucity of large, publicly available annotated corpora, although initiatives that facilitate data sharing, system evaluation, and collaborative work between researchers in clinical NLP are starting to emerge.
MRF denoising with compressed sensing and adaptive filtering
Venue: arXiv cs.IT 2014
Year: 2014

The recently proposed Magnetic Resonance Fingerprinting (MRF) technique can simultaneously estimate multiple parameters through dictionary matching. It has promising potentials in a wide range of applications. However, MRF introduces errors due to undersampling during the data acquisition process and the limit of dictionary resolution. In this paper, we investigate the error source of MRF and propose the technologies of improving the quality of MRF with compressed sensing, error prediction by decision trees, and adaptive filtering. Experimental results support our observations and show significant improvement of the proposed technologies.
Two-Page Book Embeddings of 4-Planar Graphs
Venue: arXiv cs.DM 2014
Year: 2014

Back in the Eighties, Heath showed that every 3-planar graph is subhamiltonian and asked whether this result can be extended to a class of graphs of degree greater than three. In this paper we affirmatively answer this question for the class of 4-planar graphs. Our contribution consists of two algorithms: The first one is limited to triconnected graphs, but runs in linear time and uses existing methods for computing hamiltonian cycles in planar graphs. The second one, which solves the general case of the problem, is a quadratic-time algorithm based on the book-embedding viewpoint of the problem.
ConceptVision: A Flexible Scene Classification Framework
Venue: arXiv cs.CV 2014
Year: 2014

We introduce ConceptVision, a method that aims for high accuracy in categorizing large number of scenes, while keeping the model relatively simpler and efficient for scalability. The proposed method combines the advantages of both low-level representations and high-level semantic categories, and eliminates the distinctions between different levels through the definition of concepts. The proposed framework encodes the perspectives brought through different concepts by considering them in concept groups. Different perspectives are ensembled for the final decision. Extensive experiments are carried out on benchmark datasets to test the effects of different concepts, and methods used to ensemble. Comparisons with state-of-the-art studies show that we can achieve better results with incorporation of concepts in different levels with different perspectives.
Repairable Fountain Codes
Venue: arXiv cs.IT 2014
Year: 2014

We introduce a new family of Fountain codes that are systematic and also have sparse parities. Given an input of $k$ symbols, our codes produce an unbounded number of output symbols, generating each parity independently by linearly combining a logarithmic number of randomly selected input symbols. The construction guarantees that for any $ε>0$ accessing a random subset of $(1+ε)k$ encoded symbols, asymptotically suffices to recover the $k$ input symbols with high probability. Our codes have the additional benefit of logarithmic locality: a single lost symbol can be repaired by accessing a subset of $O(\log k)$ of the remaining encoded symbols. This is a desired property for distributed storage systems where symbols are spread over a network of storage nodes. Beyond recovery upon loss, local reconstruction provides an efficient alternative for reading symbols that cannot be accessed directly. In our code, a logarithmic number of disjoint local groups is associated with each systematic symbol, allowing multiple parallel reads. Our main mathematical contribution involves analyzing the rank of sparse random matrices with specific structure over finite fields. We rely on establishing that a new family of sparse random bipartite graphs have perfect matchings with high probability.
A Survey of Techniques For Improving Energy Efficiency in Embedded Computing Systems
Venue: arXiv cs.AR 2014
Year: 2014

Recent technological advances have greatly improved the performance and features of embedded systems. With the number of just mobile devices now reaching nearly equal to the population of earth, embedded systems have truly become ubiquitous. These trends, however, have also made the task of managing their power consumption extremely challenging. In recent years, several techniques have been proposed to address this issue. In this paper, we survey the techniques for managing power consumption of embedded systems. We discuss the need of power management and provide a classification of the techniques on several important parameters to highlight their similarities and differences. This paper is intended to help the researchers and application-developers in gaining insights into the working of power management techniques and designing even more efficient high-performance embedded systems of tomorrow.