OpenRaiser/Intern-Atlas huggingface dataset:
A Graph Minor Perspective to Multicast Network Coding
Venue: arXiv cs.IT 2013
Year: 2013

Network Coding encourages information coding across a communication network. While the necessity, benefit and complexity of network coding are sensitive to the underlying graph structure of a network, existing theory on network coding often treats the network topology as a black box, focusing on algebraic or information theoretic aspects of the problem. This work aims at an in-depth examination of the relation between algebraic coding and network topologies. We mathematically establish a series of results along the direction of: if network coding is necessary/beneficial, or if a particular finite field is required for coding, then the network must have a corresponding hidden structure embedded in its underlying topology, and such embedding is computationally efficient to verify. Specifically, we first formulate a meta-conjecture, the NC-Minor Conjecture, that articulates such a connection between graph theory and network coding, in the language of graph minors. We next prove that the NC-Minor Conjecture is almost equivalent to the Hadwiger Conjecture, which connects graph minors with graph coloring. Such equivalence implies the existence of $K_4$, $K_5$, $K_6$, and $K_{O(q/\log{q})}$ minors, for networks requiring $\mathbb{F}_3$, $\mathbb{F}_4$, $\mathbb{F}_5$ and $\mathbb{F}_q$, respectively. We finally prove that network coding can make a difference from routing only if the network contains a $K_4$ minor, and this minor containment result is tight. Practical implications of the above results are discussed.
Community detection and graph partitioning
Venue: arXiv cs.SI 2013
Year: 2013

Many methods have been proposed for community detection in networks. Some of the most promising are methods based on statistical inference, which rest on solid mathematical foundations and return excellent results in practice. In this paper we show that two of the most widely used inference methods can be mapped directly onto versions of the standard minimum-cut graph partitioning problem, which allows us to apply any of the many well-understood partitioning algorithms to the solution of community detection problems. We illustrate the approach by adapting the Laplacian spectral partitioning method to perform community inference, testing the resulting algorithm on a range of examples, including computer-generated and real-world networks. Both the quality of the results and the running time rival the best previous methods.
Efficient Transmit Beamspace Design for Search-free Based DOA Estimation in MIMO Radar
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we address the problem of transmit beamspace design for multiple-input multiple-output (MIMO) radar with colocated antennas in application to direction-of-arrival (DOA) estimation. A new method for designing the transmit beamspace matrix that enables the use of search-free DOA estimation techniques at the receiver is introduced. The essence of the proposed method is to design the transmit beamspace matrix based on minimizing the difference between a desired transmit beampattern and the actual one under the constraint of uniform power distribution across the transmit array elements. The desired transmit beampattern can be of arbitrary shape and is allowed to consist of one or more spatial sectors. The number of transmit waveforms is even but otherwise arbitrary. To allow for simple search-free DOA estimation algorithms at the receive array, the rotational invariance property is established at the transmit array by imposing a specific structure on the beamspace matrix. Semi-definite relaxation is used to transform the proposed formulation into a convex problem that can be solved efficiently. We also propose a spatial-division based design (SDD) by dividing the spatial domain into several subsectors and assigning a subset of the transmit beams to each subsector. The transmit beams associated with each subsector are designed separately. Simulation results demonstrate the improvement in the DOA estimation performance offered by using the proposed joint and SDD transmit beamspace design methods as compared to the traditional MIMO radar technique.
Base Station Sleeping and Resource Allocation in Renewable Energy Powered Cellular Networks
Venue: arXiv cs.IT 2013
Year: 2013

We consider energy-efficient wireless resource management in cellular networks where BSs are equipped with energy harvesting devices, using statistical information for traffic intensity and harvested energy. The problem is formulated as adapting BSs' on-off states, active resource blocks (e.g. subcarriers) as well as power allocation to minimize the average grid power consumption in a given time period while satisfying the users' quality of service (blocking probability) requirements. It is transformed into an unconstrained optimization problem to minimize a weighted sum of grid power consumption and blocking probability. A two-stage dynamic programming (DP) algorithm is then proposed to solve this optimization problem, by which the BSs' on-off states are optimized in the first stage, and the active BS's resource blocks are allocated iteratively in the second stage. Compared with the optimal joint BSs' on-off states and active resource blocks allocation algorithm, the proposed algorithm greatly reduces the computational complexity, while at the same time achieves close to the optimal energy saving performance.
A Nonlinear Constrained Optimization Framework for Comfortable and Customizable Motion Planning of Nonholonomic Mobile Robots - Part I
Venue: arXiv cs.RO 2013
Year: 2013

In this series of papers, we present a motion planning framework for planning comfortable and customizable motion of nonholonomic mobile robots such as intelligent wheelchairs and autonomous cars. In this first one we present the mathematical foundation of our framework. The motion of a mobile robot that transports a human should be comfortable and customizable. We identify several properties that a trajectory must have for comfort. We model motion discomfort as a weighted cost functional and define comfortable motion planning as a nonlinear constrained optimization problem of computing trajectories that minimize this discomfort given the appropriate boundary conditions and constraints. The optimization problem is infinite-dimensional and we discretize it using conforming finite elements. We also outline a method by which different users may customize the motion to achieve personal comfort. There exists significant past work in kinodynamic motion planning, to the best of our knowledge, our work is the first comprehensive formulation of kinodynamic motion planning for a nonholonomic mobile robot as a nonlinear optimization problem that includes all of the following - a careful analysis of boundary conditions, continuity requirements on trajectory, dynamic constraints, obstacle avoidance constraints, and a robust numerical implementation. In this paper, we present the mathematical foundation of the motion planning framework and formulate the full nonlinear constrained optimization problem. We describe, in brief, the discretization method using finite elements and the process of computing initial guesses for the optimization problem. Details of the above two are presented in Part II of the series.
A novel automatic thresholding segmentation method with local adaptive thresholds
Venue: arXiv cs.CV 2013
Year: 2013

A novel method for segmenting bright objects from dark background for grayscale image is proposed. The concept of this method can be stated simply as: to pick out the local-thinnest bands on the grayscale grade-map. It turns out to be a threshold-based method with local adaptive thresholds, where each local threshold is determined by requiring the average normal-direction gradient on the object boundary to be local minimal. The method is highly automatic and the segmentation mimics a man's natural expectation even the object boundaries are fuzzy.
Hang With Your Buddies to Resist Intersection Attacks
Venue: arXiv cs.CR 2013
Year: 2013

Some anonymity schemes might in principle protect users from pervasive network surveillance - but only if all messages are independent and unlinkable. Users in practice often need pseudonymity - sending messages intentionally linkable to each other but not to the sender - but pseudonymity in dynamic networks exposes users to intersection attacks. We present Buddies, the first systematic design for intersection attack resistance in practical anonymity systems. Buddies groups users dynamically into buddy sets, controlling message transmission to make buddies within a set behaviorally indistinguishable under traffic analysis. To manage the inevitable tradeoffs between anonymity guarantees and communication responsiveness, Buddies enables users to select independent attack mitigation policies for each pseudonym. Using trace-based simulations and a working prototype, we find that Buddies can guarantee non-trivial anonymity set sizes in realistic chat/microblogging scenarios, for both short-lived and long-lived pseudonyms.
A Supervised Neural Autoregressive Topic Model for Simultaneous Image Classification and Annotation
Venue: arXiv cs.CV 2013
Year: 2013

Topic modeling based on latent Dirichlet allocation (LDA) has been a framework of choice to perform scene recognition and annotation. Recently, a new type of topic model called the Document Neural Autoregressive Distribution Estimator (DocNADE) was proposed and demonstrated state-of-the-art performance for document modeling. In this work, we show how to successfully apply and extend this model to the context of visual scene modeling. Specifically, we propose SupDocNADE, a supervised extension of DocNADE, that increases the discriminative power of the hidden topic features by incorporating label information into the training objective of the model. We also describe how to leverage information about the spatial position of the visual words and how to embed additional image annotations, so as to simultaneously perform image classification and annotation. We test our model on the Scene15, LabelMe and UIUC-Sports datasets and show that it compares favorably to other topic models such as the supervised variant of LDA.
Energy Efficient Transmission over Space Shift Keying Modulated MIMO Channels
Venue: arXiv cs.IT 2013
Year: 2013

Energy-efficient communication using a class of spatial modulation (SM) that encodes the source information entirely in the antenna indices is considered in this paper. The energy-efficient modulation design is formulated as a convex optimization problem, where minimum achievable average symbol power consumption is derived with rate, performance, and hardware constraints. The theoretical result bounds any modulation scheme of this class, and encompasses the existing space shift keying (SSK), generalized SSK (GSSK), and Hamming code-aided SSK (HSSK) schemes as special cases. The theoretical optimum is achieved by the proposed practical energy-efficient HSSK (EE-HSSK) scheme that incorporates a novel use of the Hamming code and Huffman code techniques in the alphabet and bit-mapping designs. Experimental studies demonstrate that EE-HSSK significantly outperforms existing schemes in achieving near-optimal energy efficiency. An analytical exposition of key properties of the existing GSSK (including SSK) modulation that motivates a fundamental consideration for the proposed energy-efficient modulation design is also provided.
Approximate Sum-Capacity of the Y-channel
Venue: arXiv cs.IT 2013
Year: 2013

A network where three users want to establish multiple unicasts between each other via a relay is considered. This network is called the Y-channel and resembles an elemental ingredient of future wireless networks. The sum-capacity of this network is studied. A characterization of the sum-capacity within an additive gap of 2 bits, and a multiplicative gap of 4, for all values of channel gains and transmit powers is obtained. Contrary to similar setups where the cut-set bounds can be achieved within a constant gap, they can not be achieved in our case, where they are dominated by our new genie-aided bounds. Furthermore, it is shown that a time-sharing strategy, in which at each time two users exchange information using coding strategies of the bi-directional relay channel, achieves the upper bounds to within a constant gap. This result is further extended to the K-user case, where it is shown that the same scheme achieves the sum-capacity within 2log(K-1) bits.
Using LDGM Codes and Sparse Syndromes to Achieve Digital Signatures
Venue: arXiv cs.CR 2013
Year: 2013

In this paper, we address the problem of achieving efficient code-based digital signatures with small public keys. The solution we propose exploits sparse syndromes and randomly designed low-density generator matrix codes. Based on our evaluations, the proposed scheme is able to outperform existing solutions, permitting to achieve considerable security levels with very small public keys.
Algorithms of an optimal integer tree labeling
Venue: arXiv cs.DS 2013
Year: 2013

Suppose we label the vertices of a tree by positive integers. The weight of an edge is defined by a monotonically increasing function of the absolute value of the difference of the labels of its endpoints. We define the total cost of the labeling to be the sum of weight of all the edges.The problem we consider is that of determining for a given tree G and given a labeling of the leaves of G the minimum total cost labellings of G. In this paper we present an algorithm that works for any cost function satisfies the condition of monotony mentioned above. In a case of the function defined as the absolute value of the difference of the labels the fast algorithm is presented.
Diversity Backpressure Scheduling and Routing with Mutual Information Accumulation in Wireless Ad-hoc Networks
Venue: arXiv cs.NI 2013
Year: 2013

We suggest and analyze algorithms for routing in multi-hop wireless ad-hoc networks that exploit mutual information accumulation as the physical layer transmission scheme, and are capable of routing multiple packet streams (commodities) when only the average channel state information is present and that only locally. The proposed algorithms are modifications of the Diversity Backpressure (DIVBAR) algorithm, under which the packet whose commodity has the largest "backpressure metric" is chosen to be transmitted and is forwarded through the link with the largest differential backlog (queue length). In contrast to traditional DIVBAR, each receiving node stores and accumulates the partially received packet in a separate "partial packet queue", thus increasing the probability of successful reception during a later possible retransmission. We present two variants of the algorithm: DIVBAR-RMIA, under which all the receiving nodes clear the received partial information of a packet once one or more receiving nodes firstly decode the packet; and DIVBAR-MIA, under which all the receiving nodes retain the partial information of a packet until the packet has reached its destination. We characterize the network capacity region with RMIA and prove that (under certain mild conditions) it is strictly larger than the network capacity region with the repetition (REP) transmission scheme that is used by the traditional DIVBAR. We also prove that DIVBAR-RMIA is throughput-optimum among the polices with RMIA, i.e., it achieves the network capacity region with RMIA, which in turn demonstrates that DIVBAR-RMIA outperforms traditional DIVBAR on the achievable throughput. Moreover, we prove that DIVBAR-MIA performs at least as well as DIVBAR-RMIA with respect to throughput. Simulations also confirm these results.
Erasure/list exponents for Slepian-Wolf decoding
Venue: arXiv cs.IT 2013
Year: 2013

We analyze random coding error exponents associated with erasure/list Slepian-Wolf decoding using two different methods and then compare the resulting bounds. The first method follows the well known techniques of Gallager and Forney and the second method is based on a technique of distance enumeration, or more generally, type class enumeration, which is rooted in the statistical mechanics of a disordered system that is related to the random energy model (REM). The second method is guaranteed to yield exponent functions which are at least as tight as those of the first method, and it is demonstrated that for certain combinations of coding rates and thresholds, the bounds of the second method are strictly tighter than those of the first method, by an arbitrarily large factor. In fact, the second method may even yield an infinite exponent at regions where the first method gives finite values. We also discuss the option of variable-rate Slepian-Wolf encoding and demonstrate how it can improve on the resulting exponents.
Geographica: A Benchmark for Geospatial RDF Stores
Venue: arXiv cs.DB 2013
Year: 2013

Geospatial extensions of SPARQL like GeoSPARQL and stSPARQL have recently been defined and corresponding geospatial RDF stores have been implemented. However, there is no widely used benchmark for evaluating geospatial RDF stores which takes into account recent advances to the state of the art in this area. In this paper, we develop a benchmark, called Geographica, which uses both real-world and synthetic data to test the offered functionality and the performance of some prominent geospatial RDF stores.
An Inventory of Preposition Relations
Venue: arXiv cs.CL 2013
Year: 2013

We describe an inventory of semantic relations that are expressed by prepositions. We define these relations by building on the word sense disambiguation task for prepositions and propose a mapping from preposition senses to the relation labels by collapsing semantically related senses across prepositions.
Maximum st-flow in directed planar graphs via shortest paths
Venue: arXiv cs.DS 2013
Year: 2013

Minimum cuts have been closely related to shortest paths in planar graphs via planar duality - so long as the graphs are undirected. Even maximum flows are closely related to shortest paths for the same reason - so long as the source and the sink are on a common face. In this paper, we give a correspondence between maximum flows and shortest paths via duality in directed planar graphs with no constraints on the source and sink. We believe this a promising avenue for developing algorithms that are more practical than the current asymptotically best algorithms for maximum st-flow.
Performance of Opportunistic Fixed Gain Bidirectional Relaying With Outdated CSI
Venue: arXiv cs.IT 2013
Year: 2013

This paper studies the impact of using outdated channel state information for relay selection on the performance of a network where two sources communicate with each other via fixed-gain amplifyand- forward relays. For a Rayleigh faded channel, closed-form expressions for the outage probability, moment generating function and symbol error rate are derived. Simulations results are also presented to corroborate the derived analytical results. It is shown that adding relays does not improve the performance if the channel is substantially outdated. Furthermore, relay location is also taken into consideration and it is shown that the performance can be improved by placing the relay closer to the source whose channel is more outdated.
Query Representation with Global Consistency on User Click Graph
Venue: arXiv cs.IR 2013
Year: 2013

Extensive research has been conducted on query log analysis. A query log is generally represented as a bipartite graph on a query set and a URL set. Most of the traditional methods used the raw click frequency to weigh the link between a query and a URL on the click graph. In order to address the disadvantages of raw click frequency, researchers proposed the entropy-biased model, which incorporates raw click frequency with inverse query frequency of the URL as the weighting scheme for query representation. In this paper, we observe that the inverse query frequency can be considered a global property of the URL on the click graph, which is more informative than raw click frequency, which can be considered a local property of the URL. Based on this insight, we develop the global consistency model for query representation, which utilizes the click frequency and the inverse query frequency of a URL in a consistent manner. Furthermore, we propose a new scheme called inverse URL frequency as an effective way to capture the global property of a URL. Experiments have been conducted on the AOL search engine log data. The result shows that our global consistency model achieved better performance than the current models.
Strong Coordination over a Line Network
Venue: arXiv cs.IT 2013
Year: 2013

We study the problem of strong coordination in a three-terminal line network, in which agents use common randomness and communicate over a line network to ensure that their actions follow a prescribed behavior, modeled by a target joint distribution of actions. We provide inner and outer bounds to the coordination capacity region, and show that these bounds are partially optimal. We leverage this characterization to develop insight into the interplay between communication and coordination. Specifically, we show that common randomness helps to achieve optimal communication rates between agents, and that matching the network topology to the behavior structure may reduce inter-agent communication rates.
On the $\ell_1$-Norm Invariant Convex k-Sparse Decomposition of Signals
Venue: arXiv cs.IT 2013
Year: 2013

Inspired by an interesting idea of Cai and Zhang, we formulate and prove the convex $k$-sparse decomposition of vectors which is invariant with respect to $\ell_1$ norm. This result fits well in discussing compressed sensing problems under RIP, but we believe it also has independent interest. As an application, a simple derivation of the RIP recovery condition $δ_k+θ_{k,k} < 1$ is presented.
The Dynamics of Creativity in Software Development
Venue: arXiv cs.SE 2013
Year: 2013

Software is primarily developed for people by people and human factors must be studied in all software engineering phases. Creativity is the source to improvise solutions to problems for dominating complex systems such as software development. However, there is a lack of knowledge in what creativity is in software development and what its dynamics are. This study describes the current state of the research plan towards a theory on creativity in software development. More specifically, it (1) states the motivation for studying creativity in software development under a multidisciplinary view; it (2) provides a first review of the literature identifying the shortcomings in the field; it (3) proposes a research design, which includes rarely employed methods in software engineering. To understand creativity in software development will provide a better knowledge of the software construction process and how individuals intellectually contribute to the creation of better, innovative products.