OpenRaiser/Intern-Atlas huggingface dataset:
List decoding Reed-Muller codes over small fields
Venue: arXiv cs.CC 2014
Year: 2014

The list decoding problem for a code asks for the maximal radius up to which any ball of that radius contains only a constant number of codewords. The list decoding radius is not well understood even for well studied codes, like Reed-Solomon or Reed-Muller codes. Fix a finite field $\mathbb{F}$. The Reed-Muller code $\mathrm{RM}_{\mathbb{F}}(n,d)$ is defined by $n$-variate degree-$d$ polynomials over $\mathbb{F}$. In this work, we study the list decoding radius of Reed-Muller codes over a constant prime field $\mathbb{F}=\mathbb{F}_p$, constant degree $d$ and large $n$. We show that the list decoding radius is equal to the minimal distance of the code. That is, if we denote by $δ(d)$ the normalized minimal distance of $\mathrm{RM}_{\mathbb{F}}(n,d)$, then the number of codewords in any ball of radius $δ(d)-\varepsilon$ is bounded by $c=c(p,d,\varepsilon)$ independent of $n$. This resolves a conjecture of Gopalan-Klivans-Zuckerman [STOC 2008], who among other results proved it in the special case of $\mathbb{F}=\mathbb{F}_2$; and extends the work of Gopalan [FOCS 2010] who proved the conjecture in the case of $d=2$. We also analyse the number of codewords in balls of radius exceeding the minimal distance of the code. For $e \leq d$, we show that the number of codewords of $\mathrm{RM}_{\mathbb{F}}(n,d)$ in a ball of radius $δ(e) - \varepsilon$ is bounded by $\exp(c \cdot n^{d-e})$, where $c=c(p,d,\varepsilon)$ is independent of $n$. The dependence on $n$ is tight. This extends the work of Kaufman-Lovett-Porat [IEEE Inf. Theory 2012] who proved similar bounds over $\mathbb{F}_2$. The proof relies on several new ingredients: an extension of the Frieze-Kannan weak regularity to general function spaces, higher-order Fourier analysis, and an extension of the Schwartz-Zippel lemma to compositions of polynomials.
Spanning Properties of Theta-Theta Graphs
Venue: arXiv cs.CG 2014
Year: 2014

We study the spanning properties of Theta-Theta graphs. Similar in spirit with the Yao-Yao graphs, Theta-Theta graphs partition the space around each vertex into a set of k cones, for some fixed integer k > 1, and select at most one edge per cone. The difference is in the way edges are selected. Yao-Yao graphs select an edge of minimum length, whereas Theta-Theta graphs select an edge of minimum orthogonal projection onto the cone bisector. It has been established that the Yao-Yao graphs with parameter k = 6k' have spanning ratio 11.67, for k' >= 6. In this paper we establish a first spanning ratio of $7.82$ for Theta-Theta graphs, for the same values of $k$. We also extend the class of Theta-Theta spanners with parameter 6k', and establish a spanning ratio of $16.76$ for k' >= 5. We surmise that these stronger results are mainly due to a tighter analysis in this paper, rather than Theta-Theta being superior to Yao-Yao as a spanner. We also show that the spanning ratio of Theta-Theta graphs decreases to 4.64 as k' increases to 8. These are the first results on the spanning properties of Theta-Theta graphs.
Generalized Secret Sharing using Permutation Ordered Binary System
Venue: arXiv cs.CR 2014
Year: 2014

Secret sharing is a method of dividing a secret among n par- ticipants and allows only qualified subset to reconstruct the secret and hence provides better reliability and availability of secret data.In the generalized secret sharing scheme, a monotone access structure of the set of participants is considered. The access structure specifies a qualified subset of participants who can reconstruct the secret from their shares.Generalized secret sharing schemes can be efficiently implemented by using (n; n) scheme.We have developed an efficient (n; n) scheme using Permutation Ordered Binary (POB) number system which is then combined with cumulative arrays to obtain a generalized secret sharing scheme.
Toward Network-based Keyword Extraction from Multitopic Web Documents
Venue: arXiv cs.CL 2014
Year: 2014

In this paper we analyse the selectivity measure calculated from the complex network in the task of the automatic keyword extraction. Texts, collected from different web sources (portals, forums), are represented as directed and weighted co-occurrence complex networks of words. Words are nodes and links are established between two nodes if they are directly co-occurring within the sentence. We test different centrality measures for ranking nodes - keyword candidates. The promising results are achieved using the selectivity measure. Then we propose an approach which enables extracting word pairs according to the values of the in/out selectivity and weight measures combined with filtering.
Stability of routing strategies for the maximum lifetime problem in ad-hoc wireless networks
Venue: arXiv cs.NI 2014
Year: 2014

We solve the maximum lifetime problem for a one-dimensional, regular ad-hoc wireless network with one data collector $L_N$ for any data transmission cost energy matrix which elements $E_{i,j}$ are superadditive functions, i.e., satisfy the inequality $\forall_{i\leq j\leq k}\;E_{i,j}+E_{j,k}\leq E_{i,k}$. We analyze stability of the solution under modification of two sets of parameters, the amount of data $Q_i$, $i\in [1,N]$ generated by each node and location of the nodes $x_i$ in the network. We assume, that the data transmission cost energy matrix $E_{i,j}$ is a function of a distance between network nodes and thus the change of the node location causes change of $E_{i,j}$. We say, that a solution $q(t_0)$ of the maximum network lifetime problem is stable under modification of a given parameter $t_0$ in the stability region $U(t_0)$, if the data flow matrix $q(t)$ is a solution of the problem for any $t\in U(t_0)$. In the paper we estimate the size of the stability region $U(Q^0,d^0)$ for the solution of the maximum network lifetime problem for the $L_N$ network in the neighborhoods of the points $Q^0_i=1$, $d^0_i=0$, where $d_i\in (-1,1)$ describes the shift of the nodes from their initial location $x_i^0=i$, i.e., $x_i=i-d_i$.
Performance Guarantees for Schatten-$p$ Quasi-Norm Minimization in Recovery of Low-Rank Matrices
Venue: arXiv cs.IT 2014
Year: 2014

We address some theoretical guarantees for Schatten-$p$ quasi-norm minimization ($p \in (0,1]$) in recovering low-rank matrices from compressed linear measurements. Firstly, using null space properties of the measurement operator, we provide a sufficient condition for exact recovery of low-rank matrices. This condition guarantees unique recovery of matrices of ranks equal or larger than what is guaranteed by nuclear norm minimization. Secondly, this sufficient condition leads to a theorem proving that all restricted isometry property (RIP) based sufficient conditions for $\ell_p$ quasi-norm minimization generalize to Schatten-$p$ quasi-norm minimization. Based on this theorem, we provide a few RIP-based recovery conditions.
Array operators using multiple dispatch: a design methodology for array implementations in dynamic languages
Venue: arXiv cs.PL 2014
Year: 2014

Arrays are such a rich and fundamental data type that they tend to be built into a language, either in the compiler or in a large low-level library. Defining this functionality at the user level instead provides greater flexibility for application domains not envisioned by the language designer. Only a few languages, such as C++ and Haskell, provide the necessary power to define $n$-dimensional arrays, but these systems rely on compile-time abstraction, sacrificing some flexibility. In contrast, dynamic languages make it straightforward for the user to define any behavior they might want, but at the possible expense of performance. As part of the Julia language project, we have developed an approach that yields a novel trade-off between flexibility and compile-time analysis. The core abstraction we use is multiple dispatch. We have come to believe that while multiple dispatch has not been especially popular in most kinds of programming, technical computing is its killer application. By expressing key functions such as array indexing using multi-method signatures, a surprising range of behaviors can be obtained, in a way that is both relatively easy to write and amenable to compiler analysis. The compact factoring of concerns provided by these methods makes it easier for user-defined types to behave consistently with types in the standard library.
D4M 2.0 Schema: A General Purpose High Performance Schema for the Accumulo Database
Venue: arXiv cs.DB 2014
Year: 2014

Non-traditional, relaxed consistency, triple store databases are the backbone of many web companies (e.g., Google Big Table, Amazon Dynamo, and Facebook Cassandra). The Apache Accumulo database is a high performance open source relaxed consistency database that is widely used for government applications. Obtaining the full benefits of Accumulo requires using novel schemas. The Dynamic Distributed Dimensional Data Model (D4M)[http://d4m.mit.edu] provides a uniform mathematical framework based on associative arrays that encompasses both traditional (i.e., SQL) and non-traditional databases. For non-traditional databases D4M naturally leads to a general purpose schema that can be used to fully index and rapidly query every unique string in a dataset. The D4M 2.0 Schema has been applied with little or no customization to cyber, bioinformatics, scientific citation, free text, and social media data. The D4M 2.0 Schema is simple, requires minimal parsing, and achieves the highest published Accumulo ingest rates. The benefits of the D4M 2.0 Schema are independent of the D4M interface. Any interface to Accumulo can achieve these benefits by using the D4M 2.0 Schema
An Enhanced Leakage-Based Precoding Scheme for Multi-User Multi-Layer MIMO Systems
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we propose an enhanced leakage-based precoding scheme, i.e., layer signal to leakage plus noise ratio (layer SLNR) scheme, for multi-user multi-layer MIMO systems. Specifically, the layer SLNR scheme incorporates the MIMO receiver structure into the precoder design procedure, which makes the formulation of signal power and interference / leakage power more accurate. Besides, the layer SLNR scheme not only takes into account the inter-layer interference from different users, but also takes care of the inter-layer interference from the same user which is usually assumed to be zero in previous studies. As a result, the proposed layer SLNR scheme produces a good balance between the layer signal power and layer interference power in a multi-user multi-layer MIMO system, therefore achieves better system performance. The effectiveness and superiority of the proposed layer SLNR scheme are validated via simulations.
Globally Optimal Joint Image Segmentation and Shape Matching Based on Wasserstein Modes
Venue: arXiv cs.CV 2014
Year: 2014

A functional for joint variational object segmentation and shape matching is developed. The formulation is based on optimal transport w.r.t. geometric distance and local feature similarity. Geometric invariance and modelling of object-typical statistical variations is achieved by introducing degrees of freedom that describe transformations and deformations of the shape template. The shape model is mathematically equivalent to contour-based approaches but inference can be performed without conversion between the contour and region representations, allowing combination with other convex segmentation approaches and simplifying optimization. While the overall functional is non-convex, non-convexity is confined to a low-dimensional variable. We propose a locally optimal alternating optimization scheme and a globally optimal branch and bound scheme, based on adaptive convex relaxation. Combining both methods allows to eliminate the delicate initialization problem inherent to many contour based approaches while remaining computationally practical. The properties of the functional, its ability to adapt to a wide range of input data structures and the different optimization schemes are illustrated and compared by numerical experiments.
Routing Attacks in Wireless Sensor Networks: A Survey
Venue: arXiv cs.CR 2014
Year: 2014

Wireless Sensor Networks (WSN) is an emerging technology now-a-days and has a wide range of applications such as battlefield surveillance, traffic surveillance, forest fire detection, flood detection etc. But wireless sensor networks are susceptible to a variety of potential attacks which obstructs the normal operation of the network. The security of a wireless sensor network is compromised because of the random deployment of sensor nodes in open environment, memory limitations, power limitations and unattended nature. This paper focuses on various attacks that manifest in the network and provides a tabular representation of the attacks, their effects and severity. The paper depicts a comparison of attacks basis packet loss and packet corruption. Also, the paper discusses the known defence mechanisms and countermeasures against the attacks.
COEL: A Web-based Chemistry Simulation Framework
Venue: arXiv cs.CE 2014
Year: 2014

The chemical reaction network (CRN) is a widely used formalism to describe macroscopic behavior of chemical systems. Available tools for CRN modelling and simulation require local access, installation, and often involve local file storage, which is susceptible to loss, lacks searchable structure, and does not support concurrency. Furthermore, simulations are often single-threaded, and user interfaces are non-trivial to use. Therefore there are significant hurdles to conducting efficient and collaborative chemical research. In this paper, we introduce a new enterprise chemistry simulation framework, COEL, which addresses these issues. COEL is the first web-based framework of its kind. A visually pleasing and intuitive user interface, simulations that run on a large computational grid, reliable database storage, and transactional services make COEL ideal for collaborative research and education. COEL's most prominent features include ODE-based simulations of chemical reaction networks and multicompartment reaction networks, with rich options for user interactions with those networks. COEL provides DNA-strand displacement transformations and visualization (and is to our knowledge the first CRN framework to do so), GA optimization of rate constants, expression validation, an application-wide plotting engine, and SBML/Octave/Matlab export. We also present an overview of the underlying software and technologies employed and describe the main architectural decisions driving our development. COEL is available at http://coel-sim.org for selected research teams only. We plan to provide a part of COEL's functionality to the general public in the near future.
Scalable and Efficient Geographic Routing in Mobile Ad Hoc Wireless Networks
Venue: arXiv cs.NI 2014
Year: 2014

We propose and evaluate a scalable position-publish and an accompanying routing protocol which is efficient despite operating with imperfect information regarding the destination's location. The traffic generated by our position-publish protocol fits within the transport capacity of large mobile ad hoc networks (MANETs) with constant communication bandwidth allocated for routing overhead, even as the network size increases. The routing protocol guarantees, with high probability, routes whose lengths are within a constant "stretch" factor of the shortest path from source to destination. The key idea underlying the scalability of the publish protocol is for each potential destination node to send location updates (with frequency decaying with distance) to a subset of network nodes, structured as annular regions around it (the natural approach of updating circular regions in distance-dependent fashion does not scale). The routing protocol must therefore account for the fact that the source and/or relay nodes may not have estimates of the destination's location (or may have stale estimates). Spatial and temporal scaling of protocol parameters are chosen so as to guarantee scalability, route reliability and route stretch, and these analytical design prescriptions are verified using simulations.
Finding representative sets of optimizations for adaptive multiversioning applications
Venue: arXiv cs.PL 2014
Year: 2014

Iterative compilation is a widely adopted technique to optimize programs for different constraints such as performance, code size and power consumption in rapidly evolving hardware and software environments. However, in case of statically compiled programs, it is often restricted to optimizations for a specific dataset and may not be applicable to applications that exhibit different run-time behavior across program phases, multiple datasets or when executed in heterogeneous, reconfigurable and virtual environments. Several frameworks have been recently introduced to tackle these problems and enable run-time optimization and adaptation for statically compiled programs based on static function multiversioning and monitoring of online program behavior. In this article, we present a novel technique to select a minimal set of representative optimization variants (function versions) for such frameworks while avoiding performance loss across available datasets and code-size explosion. We developed a novel mapping mechanism using popular decision tree or rule induction based machine learning techniques to rapidly select best code versions at run-time based on dataset features and minimize selection overhead. These techniques enable creation of self-tuning static binaries or libraries adaptable to changing behavior and environments at run-time using staged compilation that do not require complex recompilation frameworks while effectively outperforming traditional single-version non-adaptable code.
A Coded Shared Atomic Memory Algorithm for Message Passing Architectures
Venue: arXiv cs.DC 2014
Year: 2014

This paper considers the communication and storage costs of emulating atomic (linearizable) multi-writer multi-reader shared memory in distributed message-passing systems. The paper contains three main contributions: (1) We present a atomic shared-memory emulation algorithm that we call Coded Atomic Storage (CAS). This algorithm uses erasure coding methods. In a storage system with $N$ servers that is resilient to $f$ server failures, we show that the communication cost of CAS is $\frac{N}{N-2f}$. The storage cost of CAS is unbounded. (2) We present a modification of the CAS algorithm known as CAS with Garbage Collection (CASGC). The CASGC algorithm is parametrized by an integer $δ$ and has a bounded storage cost. We show that in every execution where the number of write operations that are concurrent with a read operation is no bigger than $δ$, the CASGC algorithm with parameter $δ$ satisfies atomicity and liveness. We explicitly characterize the storage cost of CASGC, and show that it has the same communication cost as CAS. (3) We describe an algorithm known as the Communication Cost Optimal Atomic Storage (CCOAS) algorithm that achieves a smaller communication cost than CAS and CASGC. In particular, CCOAS incurs read and write communication costs of $\frac{N}{N-f}$ measured in terms of number of object values. We also discuss drawbacks of CCOAS as compared with CAS and CASGC.
A Typeful Characterization of Multiparty Structured Conversations Based on Binary Sessions
Venue: arXiv cs.LO 2014
Year: 2014

Relating the specification of the global communication behavior of a distributed system and the specifications of the local communication behavior of each of its nodes/peers (e.g., to check if the former is realizable by the latter under some safety and/or liveness conditions) is a challenging problem addressed in many relevant scenarios. In the context of networked software services, a widespread programming language-based approach relies on global specifications defined by session types or behavioral contracts. Static type checking can then be used to ensure that components follow the prescribed interaction protocols. In the case of session types, developments have been mostly framed within quite different type theories for either binary (two-party) or multiparty (n-party) protocols. Unfortunately, the precise relationship between analysis techniques for multiparty and binary protocols is yet to be understood. In this work, we bridge this previously open gap in a principled way: we show that the analysis of multiparty protocols can also be developed within a much simpler type theory for binary protocols, ensuring protocol fidelity and deadlock-freedom. We present characterization theorems which provide new insights on the relation between two existing, yet very differently motivated, session type systems---one based on linear logic, the other based on automata theory---and suggest useful type-based verification techniques for multiparty systems relying on reductions to the binary case.
Evolution and Innovation in 5G Cellular Communication System and Beyond: A Study
Venue: arXiv cs.NI 2014
Year: 2014

Since the last few years there has been a phenomenal growth in the wireless industry. Widespread wireless technologies, increasing variety of user-friendly and multimedia- enabled terminals and wider availability of open source tools for content generation has lead encouraged user-centric networks resulting in a need for efficient network design. The objective of this paper is comprehensive study related to 5G technology of mobile communication. Existing research work in mobile communication is related to 5G technology. The major contribution of this study is the key provisions of 5G (Fifth Generation) technology of mobile communication, which is seen as consumer oriented. In 5G technology, the mobile consumer has given utmost priority compared to others. In this context, the existing and highly demanded technologies for 5G technologies has beed studied extensively. Open challenges are highlighted for researcher for further study of the emerging 5G systems.
Pricing for local and global WiFi markets
Venue: arXiv cs.GT 2014
Year: 2014

This paper analyzes two pricing schemes commonly used in WiFi markets: the flat-rate and the usage-based pricing. The flat-rate pricing encourages the maximum usage, while the usage-based pricing can flexibly attract more users especially those with low valuations in mobile Internet access. First, we use theoretical analysis to compare the two schemes and show that for a single provider in a market, as long as the WiFi capacity is abundant, the flat-rate pricing leads to more revenue. Second, we study how a global provider (e.g., Skype) collaborates with this monopolist in each local market to provide a global WiFi service. We formulate {the interactions between the global and local providers as a dynamic game. In Stage I, the global provider bargains with the local provider in each market to determine the global WiFi service price and revenue sharing agreement. In Stage II, local users and travelers choose local or global WiFi services. We analytically show that the global provider prefers to use the usage-based pricing to avoid a severe competition with the local provider. At the equilibrium, the global provider always shares the majority of his revenue with the local provider to incentivize the cooperation. Finally, we analytically study how the interaction changes if the local market has more than one local provider. In this case, the global provider can integrate the coverages of multiple local providers and provide a better service. Compared to the local monopoly case, local market competition enables the global provider to share less revenue with each of the local providers. However, we numerically show that the global provider's revenue could decrease, as he shares his revenue with more providers and can only charge a lower price.