OpenRaiser/Intern-Atlas huggingface dataset:
Achieving Small World Properties using Bio-Inspired Techniques in Wireless Networks
Venue: arXiv cs.NI 2012
Year: 2012

It is highly desirable and challenging for a wireless ad hoc network to have self-organization properties in order to achieve network wide characteristics. Studies have shown that Small World properties, primarily low average path length and high clustering coefficient, are desired properties for networks in general. However, due to the spatial nature of the wireless networks, achieving small world properties remains highly challenging. Studies also show that, wireless ad hoc networks with small world properties show a degree distribution that lies between geometric and power law. In this paper, we show that in a wireless ad hoc network with non-uniform node density with only local information, we can significantly reduce the average path length and retain the clustering coefficient. To achieve our goal, our algorithm first identifies logical regions using Lateral Inhibition technique, then identifies the nodes that beamform and finally the beam properties using Flocking. We use Lateral Inhibition and Flocking because they enable us to use local state information as opposed to other techniques. We support our work with simulation results and analysis, which show that a reduction of up to 40% can be achieved for a high-density network. We also show the effect of hopcount used to create regions on average path length, clustering coefficient and connectivity.
Improved Lower Bounds for the Shortest Superstring and Related Problems
Venue: arXiv cs.CC 2012
Year: 2012

We study the approximation hardness of the Shortest Superstring, the Maximal Compression and the Maximum Asymmetric Traveling Salesperson (MAX-ATSP) problem. We introduce a new reduction method that produces strongly restricted instances of the Shortest Superstring problem, in which the maximal orbit size is eight (with no character appearing more than eight times) and all given strings having length four. Based on this reduction method, we are able to improve the best up to now known approximation lower bound for the Shortest Superstring problem and the Maximal Compression problem by an order of magnitude. The results imply also an improved approximation lower bound for the MAX-ATSP problem.
Truthful Mechanisms for Agents that Value Privacy
Venue: arXiv cs.GT 2012
Year: 2012

Recent work has constructed economic mechanisms that are both truthful and differentially private. In these mechanisms, privacy is treated separately from the truthfulness; it is not incorporated in players' utility functions (and doing so has been shown to lead to non-truthfulness in some cases). In this work, we propose a new, general way of modelling privacy in players' utility functions. Specifically, we only assume that if an outcome $o$ has the property that any report of player $i$ would have led to $o$ with approximately the same probability, then $o$ has small privacy cost to player $i$. We give three mechanisms that are truthful with respect to our modelling of privacy: for an election between two candidates, for a discrete version of the facility location problem, and for a general social choice problem with discrete utilities (via a VCG-like mechanism). As the number $n$ of players increases, the social welfare achieved by our mechanisms approaches optimal (as a fraction of $n$).
A Formalization of Social Requirements for Human Interactions with Service Protocols
Venue: arXiv cs.SI 2012
Year: 2012

Collaboration models and tools aim at improving the efficiency and effectiveness of human interactions. Although social relations among collaborators have been identified as having a strong influence on collaboration, they are still insufficiently taken into account in current collaboration models and tools. In this paper, the concept of service protocols is proposed as a model for human interactions supporting social requirements, i.e., sets of constraints on the relations among interacting humans. Service protocols have been proposed as an answer to the need for models for human interactions in which not only the potential sequences of activities are specified-as in process models-but also the constraints on the relations among collaborators. Service protocols are based on two main ideas: first, service protocols are rooted in the service-oriented architecture (SOA): each service protocol contains a service-oriented summary which provides a representation of the activities of an associated process model in SOA terms. Second, a class-based graph-referred to as a service network schema-restricts the set of potential service elements that may participate in the service protocol by defining constraints on nodes and constraints on arcs, i.e., social requirements. Another major contribution to the modelling of human interactions is a unified approach organized around the concept of service, understood in a broad sense with services being not only Web services, but also provided by humans.
Type inference in mathematics
Venue: arXiv cs.LO 2012
Year: 2012

In the theory of programming languages, type inference is the process of inferring the type of an expression automatically, often making use of information from the context in which the expression appears. Such mechanisms turn out to be extremely useful in the practice of interactive theorem proving, whereby users interact with a computational proof assistant to construct formal axiomatic derivations of mathematical theorems. This article explains some of the mechanisms for type inference used by the Mathematical Components project, which is working towards a verification of the Feit-Thompson theorem.
List Decoding Barnes-Wall Lattices
Venue: arXiv cs.IT 2012
Year: 2012

The question of list decoding error-correcting codes over finite fields (under the Hamming metric) has been widely studied in recent years. Motivated by the similar discrete structure of linear codes and point lattices in R^N, and their many shared applications across complexity theory, cryptography, and coding theory, we initiate the study of list decoding for lattices. Namely: for a lattice L in R^N, given a target vector r in R^N and a distance parameter d, output the set of all lattice points w in L that are within distance d of r. In this work we focus on combinatorial and algorithmic questions related to list decoding for the well-studied family of Barnes-Wall lattices. Our main contributions are twofold: 1) We give tight (up to polynomials) combinatorial bounds on the worst-case list size, showing it to be polynomial in the lattice dimension for any error radius bounded away from the lattice's minimum distance (in the Euclidean norm). 2) Building on the unique decoding algorithm of Micciancio and Nicolosi (ISIT '08), we give a list-decoding algorithm that runs in time polynomial in the lattice dimension and worst-case list size, for any error radius. Moreover, our algorithm is highly parallelizable, and with sufficiently many processors can run in parallel time only poly-logarithmic in the lattice dimension. In particular, our results imply a polynomial-time list-decoding algorithm for any error radius bounded away from the minimum distance, thus beating a typical barrier for error-correcting codes posed by the Johnson radius.
A discrepancy lower bound for information complexity
Venue: arXiv cs.CC 2012
Year: 2012

This paper provides the first general technique for proving information lower bounds on two-party unbounded-rounds communication problems. We show that the discrepancy lower bound, which applies to randomized communication complexity, also applies to information complexity. More precisely, if the discrepancy of a two-party function $f$ with respect to a distribution $μ$ is $Disc_μf$, then any two party randomized protocol computing $f$ must reveal at least $Ω(\log (1/Disc_μf))$ bits of information to the participants. As a corollary, we obtain that any two-party protocol for computing a random function on $\{0,1\}^n\times\{0,1\}^n$ must reveal $Ω(n)$ bits of information to the participants. In addition, we prove that the discrepancy of the Greater-Than function is $Ω(1/\sqrt{n})$, which provides an alternative proof to the recent proof of Viola \cite{Viola11} of the $Ω(\log n)$ lower bound on the communication complexity of this well-studied function and, combined with our main result, proves the tight $Ω(\log n)$ lower bound on its information complexity. The proof of our main result develops a new simulation procedure that may be of an independent interest. In a very recent breakthrough work of Kerenidis et al. \cite{kerenidis2012lower}, this simulation procedure was the main building block for proving that almost all known lower bound techniques for communication complexity (and not just discrepancy) apply to information complexity.
ANDaNA: Anonymous Named Data Networking Application
Venue: arXiv cs.CR 2012
Year: 2012

Content-centric networking -- also known as information-centric networking (ICN) -- shifts emphasis from hosts and interfaces (as in today's Internet) to data. Named data becomes addressable and routable, while locations that currently store that data become irrelevant to applications. Named Data Networking (NDN) is a large collaborative research effort that exemplifies the content-centric approach to networking. NDN has some innate privacy-friendly features, such as lack of source and destination addresses on packets. However, as discussed in this paper, NDN architecture prompts some privacy concerns mainly stemming from the semantic richness of names. We examine privacy-relevant characteristics of NDN and present an initial attempt to achieve communication privacy. Specifically, we design an NDN add-on tool, called ANDaNA, that borrows a number of features from Tor. As we demonstrate via experiments, it provides comparable anonymity with lower relative overhead.
Being, space and time in the Web
Venue: arXiv cs.OH 2012
Year: 2012

The Web initially emerged as an "antidote" to accumulated scientific knowledge since it enables global representation and communication with minimum costs. Its gigantic scale and interdependence incommode our ability to find relevant information and develop trustworthy contexts. It is time for science to compensate by providing an epistemological "antidote" to Web issues. Philosophy should be in the front line by forming the salient questions and analysis. The scope of our research is to provide a theory about the Web being that will bridge philosophical thinking and engineering. We analyze existence and spatiotemporality in the Web and how it transforms the traditional actualities. The Web space is specified by incoming and outgoing links. The primordial role of visiting durations in Web's existence is approximated by Bergsonian time. The physical space becomes more discoverable. The human activity can be asynchronous, synchronous and continuous. Networked individuals operate in a flexible and spatially dispersed environment. The resulting issues concern the self-determination of a being and the way in which the Web could be a free and open platform for innovation and participation.
Decorated proofs for computational effects: States
Venue: arXiv cs.PL 2012
Year: 2012

The syntax of an imperative language does not mention explicitly the state, while its denotational semantics has to mention it. In this paper we show that the equational proofs about an imperative language may hide the state, in the same way as the syntax does.
Distributed Particle Filter Implementation with Intermittent/Irregular Consensus Convergence
Venue: arXiv cs.DC 2012
Year: 2012

Motivated by non-linear, non-Gaussian, distributed multi-sensor/agent navigation and tracking applications, we propose a multi-rate consensus/fusion based framework for distributed implementation of the particle filter (CF/DPF). The CF/DPF framework is based on running localized particle filters to estimate the overall state vector at each observation node. Separate fusion filters are designed to consistently assimilate the local filtering distributions into the global posterior by compensating for the common past information between neighbouring nodes. The CF/DPF offers two distinct advantages over its counterparts. First, the CF/DPF framework is suitable for scenarios where network connectivity is intermittent and consensus can not be reached between two consecutive observations. Second, the CF/DPF is not limited to the Gaussian approximation for the global posterior density. A third contribution of the paper is the derivation of the exact expression for computing the posterior Cramer-Rao lower bound (PCRLB) for the distributed architecture based on a recursive procedure involving the local Fisher information matrices (FIM) of the distributed estimators. The performance of the CF/DPF algorithm closely follows the centralized particle filter approaching the PCRLB at the signal to noise ratios that we tested.
Practical Methods for Wireless Network Coding with Multiple Unicast Transmissions
Venue: arXiv cs.IT 2012
Year: 2012

We propose a simple yet effective wireless network coding and decoding technique for a multiple unicast network. It utilizes spatial diversity through cooperation between nodes which carry out distributed encoding operations dictated by generator matrices of linear block codes. In order to exemplify the technique, we make use of greedy codes over the binary field and show that the arbitrary diversity orders can be flexibly assigned to nodes. Furthermore, we present the optimal detection rule for the given model that accounts for intermediate node errors and suggest a low-complexity network decoder using the sum-product (SP) algorithm. The proposed SP detector exhibits near optimal performance. We also show asymptotic superiority of network coding over a method that utilizes the wireless channel in a repetitive manner without network coding (NC) and give related rate-diversity trade-off curves. Finally, we extend the given encoding method through selective encoding in order to obtain extra coding gains.
A Sufficient Condition for Hanna Neumann Property of Submonoids of a Free Monoid
Venue: arXiv cs.FL 2012
Year: 2012

Using automata-theoretic approach, Giambruno and Restivo have investigated on the intersection of two finitely generated submonoids of the free monoid over a finite alphabet. In particular, they have obtained Hanna Neumann property for a special class of submonoids generated by finite prefix sets. This work continues their work and provides a sufficient condition for Hanna Neumann property for the entire class of submonoids generated by finite prefix sets. In this connection, a general rank formula for the submonoids which are accepted by semi-flower automata is also obtained.
Cooperative Algorithms for MIMO Amplify-and-Forward Relay Networks
Venue: arXiv cs.IT 2012
Year: 2012

Interference alignment is a signaling technique that provides high multiplexing gain in the interference channel. It can be extended to multi-hop interference channels, where relays aid transmission between sources and destinations. In addition to coverage extension and capacity enhancement, relays increase the multiplexing gain in the interference channel. In this paper, three cooperative algorithms are proposed for a multiple-antenna amplify-and-forward (AF) relay interference channel. The algorithms design the transmitters and relays so that interference at the receivers can be aligned and canceled. The first algorithm minimizes the sum power of enhanced noise from the relays and interference at the receivers. The second and third algorithms rely on a connection between mean square error and mutual information to solve the end-to-end sum-rate maximization problem with either equality or inequality power constraints via matrix-weighted sum mean square error minimization. The resulting iterative algorithms converge to stationary points of the corresponding optimization problems. Simulations show that the proposed algorithms achieve higher end-to-end sum-rates and multiplexing gains that existing strategies for AF relays, decode-and-forward relays, and direct transmission. The first algorithm outperforms the other algorithms at high signal-to-noise ratio (SNR) but performs worse than them at low SNR. Thanks to power control, the third algorithm outperforms the second algorithm at the cost of overhead.
Entropic Inequalities and Marginal Problems
Venue: arXiv cs.IT 2012
Year: 2012

A marginal problem asks whether a given family of marginal distributions for some set of random variables arises from some joint distribution of these variables. Here we point out that the existence of such a joint distribution imposes non-trivial conditions already on the level of Shannon entropies of the given marginals. These entropic inequalities are necessary (but not sufficient) criteria for the existence of a joint distribution. For every marginal problem, a list of such Shannon-type entropic inequalities can be calculated by Fourier-Motzkin elimination, and we offer a software interface to a Fourier-Motzkin solver for doing so. For the case that the hypergraph of given marginals is a cycle graph, we provide a complete analytic solution to the problem of classifying all relevant entropic inequalities, and use this result to bound the decay of correlations in stochastic processes. Furthermore, we show that Shannon-type inequalities for differential entropies are not relevant for continuous-variable marginal problems; non-Shannon-type inequalities are, both in the discrete and in the continuous case. In contrast to other approaches, our general framework easily adapts to situations where one has additional (conditional) independence requirements on the joint distribution, as in the case of graphical models. We end with a list of open problems. A complementary article discusses applications to quantum nonlocality and contextuality.
Sparse matrix-vector multiplication on GPGPU clusters: A new storage format and a scalable implementation
Venue: arXiv cs.DC 2012
Year: 2012

Sparse matrix-vector multiplication (spMVM) is the dominant operation in many sparse solvers. We investigate performance properties of spMVM with matrices of various sparsity patterns on the nVidia "Fermi" class of GPGPUs. A new "padded jagged diagonals storage" (pJDS) format is proposed which may substantially reduce the memory overhead intrinsic to the widespread ELLPACK-R scheme. In our test scenarios the pJDS format cuts the overall spMVM memory footprint on the GPGPU by up to 70%, and achieves 95% to 130% of the ELLPACK-R performance. Using a suitable performance model we identify performance bottlenecks on the node level that invalidate some types of matrix structures for efficient multi-GPGPU parallelization. For appropriate sparsity patterns we extend previous work on distributed-memory parallel spMVM to demonstrate a scalable hybrid MPI-GPGPU code, achieving efficient overlap of communication and computation.
Optimal Resource Allocation and Relay Selection in Bandwidth Exchange Based Cooperative Forwarding
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we investigate joint optimal relay selection and resource allocation under bandwidth exchange (BE) enabled incentivized cooperative forwarding in wireless networks. We consider an autonomous network where N nodes transmit data in the uplink to an access point (AP) / base station (BS). We consider the scenario where each node gets an initial amount (equal, optimal based on direct path or arbitrary) of bandwidth, and uses this bandwidth as a flexible incentive for two hop relaying. We focus on alpha-fair network utility maximization (NUM) and outage reduction in this environment. Our contribution is two-fold. First, we propose an incentivized forwarding based resource allocation algorithm which maximizes the global utility while preserving the initial utility of each cooperative node. Second, defining the link weight of each relay pair as the utility gain due to cooperation (over noncooperation), we show that the optimal relay selection in alpha-fair NUM reduces to the maximum weighted matching (MWM) problem in a non-bipartite graph. Numerical results show that the proposed algorithms provide 20- 25% gain in spectral efficiency and 90-98% reduction in outage probability.
On the Stability of Random Multiple Access with Stochastic Energy Harvesting
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we consider the random access of nodes having energy harvesting capability and a battery to store the harvested energy. Each node attempts to transmit the head-of-line packet in the queue if its battery is nonempty. The packet and energy arrivals into the queue and the battery are all modeled as a discrete-time stochastic process. The main contribution of this paper is the exact characterization of the stability region of the packet queues given the energy harvesting rates when a pair of nodes are randomly accessing a common channel having multipacket reception (MPR) capability. The channel with MPR capability is a generalized form of the wireless channel modeling which allows probabilistic receptions of the simultaneously transmitted packets. The results obtained in this paper are fairly general as the cases with unlimited energy for transmissions both with the collision channel and the channel with MPR capability can be derived from ours as special cases. Furthermore, we study the impact of the finiteness of the batteries on the achievable stability region.
Vectorial FCSR constructed on totally ramified extension of the p-adic numbers
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we introduce a vectorial conception of d-FCSRs to build these registers over any finite field. We describe the structure of d-vectorial FCSRs and we develop an analysis to obtain basic properties like periodicity and the existence of maximal length sequences. To illustrate these vectorial d-FCSRs, we present simple examples and we compare with those of Goresky, Klapper and Xu. Keywords: LFSR, FCSR, vectorial FCSR, d-FCSR, sequences, periodicity, p-adic, ?-adic, maximal period.
Quotient Complexities of Atoms of Regular Languages
Venue: arXiv cs.FL 2012
Year: 2012

An atom of a regular language L with n (left) quotients is a non-empty intersection of uncomplemented or complemented quotients of L, where each of the n quotients appears in a term of the intersection. The quotient complexity of L, which is the same as the state complexity of L, is the number of quotients of L. We prove that, for any language L with quotient complexity n, the quotient complexity of any atom of L with r complemented quotients has an upper bound of 2^n-1 if r=0 or r=n, and 1+\sum_{k=1}^{r} \sum_{h=k+1}^{k+n-r} C_{h}^{n} \cdot C_{k}^{h} otherwise, where C_j^i is the binomial coefficient. For each n\ge 1, we exhibit a language whose atoms meet these bounds.
Let us first agree on what the term "semantics" means: An unorthodox approach to an age-old debate
Venue: arXiv cs.AI 2012
Year: 2012

Traditionally, semantics has been seen as a feature of human language. The advent of the information era has led to its widespread redefinition as an information feature. Contrary to this praxis, I define semantics as a special kind of information. Revitalizing the ideas of Bar-Hillel and Carnap I have recreated and re-established the notion of semantics as the notion of Semantic Information. I have proposed a new definition of information (as a description, a linguistic text, a piece of a story or a tale) and a clear segregation between two different types of information - physical and semantic information. I hope, I have clearly explained the (usually obscured and mysterious) interrelations between data and physical information as well as the relation between physical information and semantic information. Consequently, usually indefinable notions of "information", "knowledge", "memory", "learning" and "semantics" have also received their suitable illumination and explanation.