nils-herrmann/clean_scirepeval huggingface dataset:
On the Role of Network Coding in Uncoordinated Multihop Content Distribution over Ad Hoc Networks

We consider the problem of multihop communication in ad hoc networks. This work was originally motivated by vehicular networks, and has application in numerous fields. The key constraint in such systems is the infeasibility of coordination. Because no single node has global knowledge of the network topology, centralized scheduling of transmissions and routing of packets is prohibitively expensive. We propose instead a simple distributed protocol, based on independent channel access and random network coding. This scheme does not require link level feedback, and nodes need not even track the identities of their current neighbors. Our main result shows that when using this scheme, the end-to-end throughput is identical to the throughput in a one hop network utilizing the same protocol. Thus, in an application requiring uncoordinated communication, network coding enables a multihop network to perform as efficiently as a single hop network. In the context of vehicular networks, in a region of congested traffic a constant throughput can be provided to vehicles arbitrarily far from the base station. In essence, every vehicle can be thought of as a digital repeater, despite the packet losses due to collisions and fading.
Explicit construction of optimal exact regenerating codes for distributed storage

Erasure coding techniques are used to increase the reliability of distributed storage systems while minimizing storage overhead. Also of interest is minimization of the bandwidth required to repair the system following a node failure. In a recent paper, Wu et al. characterize the tradeoff between the repair bandwidth and the amount of data stored per node. They also prove the existence of regenerating codes that achieve this tradeoff. In this paper, we introduce Exact Regenerating Codes, which are regenerating codes possessing the additional property of being able to duplicate the data stored at a failed node. Such codes require low processing and communication overheads, making the system practical and easy to maintain. Explicit construction of exact regenerating codes is provided for the minimum bandwidth point on the storage-repair bandwidth tradeoff, relevant to distributed-mail-server applications. A subspace based approach is provided and shown to yield necessary and sufficient conditions on a linear code to possess the exact regeneration property as well as prove the uniqueness of our construction. Also included in the paper, is an explicit construction of regenerating codes for the minimum storage point for parameters relevant to storage in peer-to-peer systems. This construction supports a variable number of nodes and can handle multiple, simultaneous node failures. All constructions given in the paper are of low complexity, requiring low field size in particular.
Application of continuous error detection for joint equalization and coding for ISI channels

Intersymbol interference (ISI) distorts digital signals transmitted over band-limited channels. While solutions like decision feedback equalization (DFE) suffer from error propagation, sequence estimation methods have exponential complexity. We present a scheme that effectively reduces the complexity of sequence estimation by removing paths that are in error on the fly, using continuous error detection (CED). The number of symbols taken for detecting an error can be tuned based on the amount of redundancy available for the particular application. Simulations show that our scheme can bring about a factor of two reduction in complexity in the trellis of Yellin, Vardy and Amrani  1997) and give about 0.5 dB performance improvement at the same complexity. CED can be implemented efficiently at low complexity in hardware and can enhance the performance of ARQ/FEC based digital transmission systems. This work presents the performance gains in a reduced state sequence estimation framework.
Robust distributed video compression based on multilevel coset codes

A new video coding paradigm (PRISM) built on distributed coding principles has recently been proposed in R. Puri and K. Ramchandran, (2002, 2003). The PRISM framework rests heavily on channel coding concepts. The basic idea is to do intra-frame coding but to approach the coding efficiency of motion-compensated inter-frame coding by using channel codes to derive a coding rate rebate by "exploiting" the correlated side-information present in the form of previous temporal frames at the decoder. The coding strategy described in R. Puri and K. Ramchandran, (2002, 2003) was limited to rate-1/2 trellis coset codes, which limit the granularity at which the correlated side-information can be exploited. In this work, we generalize the coset coding framework to multi-level codes which allow more flexible encoding rates and the capability to exploit correlations with much finer granularity. Simulation results validate the better compression performance (of the order of 1 dB for typical tests) of the multilevel framework.
Joint space-frequency segmentation using balanced wavelet packet trees for least-cost image representation

We examine the question of how to choose a space varying filterbank tree representation that minimizes some additive cost function for an image. The idea is that for a particular cost function, e.g., energy compaction or quantization distortion, some tree structures perform better than others. While the wavelet tree represents a good choice for many signals, it is generally outperformed by the best tree from the library of wavelet packet frequency-selective trees. The double-tree library of bases performs better still, by allowing different wavelet packet trees over all binary spatial segments of the image. We build on this foundation and present efficient new pruning algorithms for both one- and two-dimensional (1-D and 2-D) trees that will find the best basis from a library that is many times larger than the library of the single-tree or double-tree algorithms. The augmentation of the library of bases overcomes the constrained nature of the spatial variation in the double-tree bases, and is a significant enhancement in practice. Use of these algorithms to select the least-cost expansion for images with a rate-distortion cost function gives a very effective signal adaptive compression scheme. This scheme is universal in the sense that, without assuming a model for the signal or making use of training data, it performs very well over a large class of signal types. In experiments it achieves compression rates that are competitive with the best training-based schemes.
Metadata-Conscious Anonymous Messaging

Anonymous messaging platforms allow users to spread messages over a network (e.g., a social network) without revealing message authorship to other users. Popular demand for anonymous messaging is evidenced by the success of mobile apps like Whisper and Yik Yak. In such platforms, the spread of messages is typically modeled as a diffusion process. Recent advances in network analysis have revealed that such diffusion processes are vulnerable to author deanonymization by adversaries with access to metadata, such as timing information. In this work, we ask the fundamental question of how to intervene in the propagation of anonymous messages in order to make it difficult to find the source. In particular, we study the performance of a message propagation protocol called adaptive diffusion. We prove that it achieves asymptotically optimal source-hiding and significantly outperforms standard diffusion. We further demonstrate empirically that adaptive diffusion hides the source effectively on real social graphs.
The Role of Signal Processing in Meeting Privacy Challenges: An Overview

With the increasing growth and sophistication of information technology, personal information is easily accessible electronically. This flood of released personal data raises important privacy concerns. However, electronic data sources exist to be used and have tremendous value (utility) to their users and collectors, leading to a tension between privacy and utility. This article aims to quantify that tension by means of an information-theoretic framework and motivate signal processing approaches to privacy problems. The framework is applied to a number of case studies to illustrate concretely how signal processing can be harnessed to provide data privacy.
Hybrid Digital-Analog Codes for Source-Channel Broadcast of Gaussian Sources Over Gaussian Channels

The problem of broadcasting a parallel Gaussian source over an additive white Gaussian noise broadcast channel under the mean-squared error distortion criterion is studied. A hybrid digital-analog coding strategy which combines source coding with side information, channel coding with side information, layered source coding, and superposition broadcast channel coding is presented. When specialized to the open problem of broadcasting a white Gaussian source over an additive white Gaussian noise broadcast channel with bandwidth mismatch, which has been the subject of several previous investigations, this coding scheme strictly improves on the state of the art.
On Compression of Encrypted Images

Coding schemes for secure and efficient communication over noiseless public channels traditionally compress and then encrypt the source data. In some cases reversing the ordering of compression and encryption would be useful, e.g., in enabling the efficient distribution of protected media content. Indeed, not only is it possible to reverse the order, but under some conditions neither security nor compression efficiency need be sacrificed. In earlier work on this problem we have assumed that the source data is either memoryless or has a 1-D Markov structure. Such models are poor matches for the 2-D structure of images. In this work, we use a 2-D source model, and develop a scheme to compress encrypted images based on LDPC codes. We present practical simulation results for compressing bi-level images. In tests, we are able to compress an encrypted 10, 000 bit bi-level image to 4, 299 bits and successfully recover the image exactly. In previous works, the best analogous 1-D model (operating on a raster scanned data sequence of the same source) could only compress the image to 7, 710 bits.
Detecting primary receivers for cognitive radio applications

In this paper we develop a framework for competition of future operators likely to operate in a mixed commons/property-rights regime under the regulation of a spectrum policy server (SPS). The operators dynamically compete for customers as well as portions of available spectrum. The operators are charged by the SPS for the amount of bandwidth they use in their services. Through demand responsive pricing, the operators try to come up with convincing service offers for the customers, while trying to maximize their profits. We first consider a single-user system as an illustrative example. We formulate the competition between the operators as a non-cooperative game and propose an SPS-based iterative bidding scheme that results in Nash equilibrium of the game. Numerical results suggest that, competition increases the user's (customer's) acceptance probability of the offered service, while reducing the profits achieved by the operators. It is also observed that as the cost of unit bandwidth increases relative to the cost of unit infrastructure (fixed cost), the operator with superior technology (higher fixed cost) becomes more competitive. We then extend the framework to a multiuser setting where the operators are competing for a number of users at once. We propose an SPS-based bandwidth allocation scheme in which the SPS optimally allocates bandwidth portions for each user-operator session to maximize its overall expected revenue resulting from the operator payments. Comparison of the performance of this scheme to one in which the bandwidth is equally shared between the user-operator pairs reveals that such an SPS-based scheme improves the user acceptance probabilities and the bandwidth utilization in multiuser systems
Multimodal Location Estimation of Consumer Media: Dealing with Sparse Training Data

This article describes a novel approach to the problem of associating geo-locations to consumer-produced multimedia data such as videos and photos that are publicly available on social networking websites such as Flickr. We specifically focus on the case where the available training data is sparse both in absolute numbers as well as geographic coverage when compared to the number of untagged query data. We develop a novel graphical model based framework for the problem of interest and pose the problem of geotagging as one of inference over this graph. The novelty of our algorithm lies in the fact that we jointly estimate the geo-locations of all the query videos, which helps obtain performance improvements over existing algorithms in the literature that process each query video independently. Our system enables the query videos to act as "virtual" training data that effectively bootstrap the geo-tagging process. The quality of the database improves with each additional query video in the system. Further, our modeling provides a generic theoretical framework that can be used to incorporate any other available textual, visual or audio features. We evaluate our algorithm on the MediaEval 2011 Placing Task data set and show that for fixed training data the system performance improves with an increasing number of unlabeled test data. The performance gains are shown to be over 10% as compared to existing algorithms in the literature.
Distributed source coding using syndromes (DISCUS): design and construction

We address the problem of distributed source coding, i.e. compression of correlated sources that are not co-located and/or cannot communicate with each other to minimize their joint description cost. In this work we tackle the related problem of compressing a source that is correlated with another source which is available only at the decoder. In contrast to prior information-theoretic approaches, we introduce a new construction and practical framework for tackling the problem based on the judicious incorporation of channel coding principles into this source coding problem. We dub our approach as distributed source coding using syndromes (DISCUS). We focus in this paper on trellis-structured constructions of the framework to illustrate its utility. Simulation results confirm the power of DISCUS, opening up a new and exciting constructive playing-ground for the distributed source coding problem. For the distributed coding of correlated i.i.d. Gaussian sources that are noisy versions of each other with "correlation-SNR" in the range of 12 to 20 dB, the DISCUS method attains gains of 7-15 dB in SNR over the Shannon-bound using "naive" independent coding of the sources.
A general joint source-channel matching method for wireless video transmission

With the rapid growth of multimedia content in wireless communication, there is an increasing demand for efficient image and video transmission systems. We present a joint source-channel matching scheme for wireless video transmission which jointly optimizes the source and channel coder to yield the optimal transmission quality while satisfying real-time delay and buffer constraints. We utilize a parametric model approach which avoids the necessity of having detailed a priori knowledge of the coders, thus making the scheme applicable to a wide variety of source and channel coder pairs. Simulations show that the scheme yields excellent results and works for several different types of source and channel coders.
Capacity-approaching PhaseCode for low-complexity compressive phase retrieval

In this paper, we tackle the general compressive phase retrieval problem. The problem is to recover (to within a global phase uncertainty) a K-sparse complex vector of length n, x ∈ ℂn, from the magnitudes of m linear measurements, y = |Ax|, where A ∈ ℂm×n can be designed, and the magnitudes are taken component-wise for vector Ax ∈ ℂm. We propose a variant of the PhaseCode algorithm, first introduced in , and show that under some mild assumptions, using an irregular left-degree sparse-graph code construction, the algorithm can recover almost all the K non-zero signal components using only slightly more than 4K measurements, with orderoptimal time and memory complexity of O(K). It is known that the fundamental limit for the number of measurements in compressive phase retrieval problem is 4K - o(K) [2, 3]. To the best of our knowledge, this is the first constructive capacityapproaching compressive phase retrieval algorithm: in fact, our algorithm is also order-optimal in complexity and memory.
A hybrid DFT-LDPC framework for fast, efficient and robust compressive sensing

We use a hybrid mix of the Discrete Fourier Transform (DFT), an old workhorse in digital signal processing, and Low Density Parity Check (LDPC) codes, a recent workhorse in coding theory, to generate a linear measurement lens through which to perform compressive sensing (CS) of sparse high-dimensional signals. This novel hybrid DFT-LDPC framework represents a new family of sparse measurement matrices, and induces a fast algorithm (dubbed the Short-and-Wide Iterative Fast Transform based or SWIFT algorithm) for robustly recovering a high-dimensional k-sparse signal x, in Cn, from a near-optimal (upto a small constant multiple of k) number of linear observations, with a decoding complexity of k steps, under high signal-to-noise-ratio (SNR). A key attribute of our sensing framework and the SWIFT recovery algorithm is that both the sensing efficiency (number of measurements) and the recovery efficiency (decoding complexity) are independent of the ambient signal dimension n for the noiseless and high-SNR noisy regimes, which is particularly attractive when k <;<; n. This contrasts existing solutions1 in the CS literature based on the class of Linear Programming (LP)-based optimization techniques and the class of expander graph based greedy-pursuit (sketching) algorithms; for both these classes, both the number of measurements and the decoding complexity depend explicitly on the ambient signal dimension n, even for the noiseless and high-SNR regimes. We provide both an explicit constructions of the DFT-LDPC based matrix framework and an analytical characterization of the SWIFT recovery algorithm. Although our analytical characterization is for asymptotic values of k, n and for high SNR regime, our simulation results validate the efficiency of the SWIFT algorithm even for the low-to-moderate SNR regimes and modest problem dimensions (e.g., k = 250 and n = 20000), beyond what we can currently prove analytically.
Data funneling: routing with aggregation and compression for wireless sensor networks

This paper considers the problem of minimizing the amount of communication needed to send readings from a set of sensors to a single destination in energy constrained wireless networks. Substantial gains can be obtained using packet aggregation techniques while routing. The proposed routing algorithm, called Data Funneling, allows the network to considerably reduce the amount of energy spent on communication setup and control, an important concern in low data-rate communication. This is achieved by sending only one data stream from a group of sensors to the destination instead of having an individual data stream from each sensor to the destination. Doing so also reduces the probability of packet collisions in the wireless medium because the same amount of information can be transmitted by having fewer nodes send longer packets. Additional gains can be realized by efficient compression of data. This is achieved by losslessly compressing the data by encoding information in the ordering of the sensors' packets. This "coding by ordering" scheme compresses data by suppressing certain readings and encoding their values in the ordering of the remaining packets. Using these techniques together can more than halve the energy spent in communication.
Secure network coding for distributed secret sharing with low communication cost

Shamir's (n, k) threshold secret sharing is an important component of several cryptographic protocols, such as those for secure multiparty-computation. These protocols typically assume the presence of direct communication links from the dealer to all participants, in which case the dealer can directly pass the shares of the secret to every participant. In this paper, we consider the problem of secret sharing when the dealer does not have direct communication links to all participants, and instead, they form a general network. We present an algorithm for secret sharing over networks that satisfy what we call the k-propagating-dealer condition. The algorithm is communication-efficient, distributed and deterministic. Interestingly, the solution constitutes an instance of a network coding problem admitting a distributed and deterministic solution, and furthermore, handles the case of nodal-eavesdropping, about which very little appears to be known in the literature. In the second part of the paper, we derive information-theoretic lower bounds on the communication complexity of secret sharing over any network, which may also be of independent interest. We show that for networks satisfying the k-propagating-dealer condition, the communication complexity of our algorithm is Θ(n), and furthermore, is always within a constant factor of the lower bound. We also show that, in contrast, existing solutions in the literature entail a communication-complexity that is superlinear for a wide class of networks, and is Θ(n2) in the worst case. Our algorithm thus allows for efficient generalization of several cryptographic protocols to a large class of networks.
A low-complexity region-based video compression framework using morphology

We introduce a novel region-based video compression framework based on morphology to efficiently capture motion correspondences between consecutive frames in an image sequence. Our coder is built on the observation that the motion field associated with typical image sequences can be segmented into component motion subfield "clusters" associated with distinct objects or regions in the scene, and further that these clusters can be efficiently captured using morphological operators in a "backward" framework that avoids the need to send region shape information. The cluster motion field is obtained using a novel "cluster matching" approach which is computationally efficient due to the use of only a small cluster "core" that serves as a reliable representative of the entire cluster. A novel morphological dilation operation is used to expand the cluster based on the motion information, and quantization of the cluster motion prediction error is directly incorporated in the region-growing process. Experimental results reveal a 10-30% reduction in coding bit rate over the standard MPEG-1 coder at typical bit rates of 500 kbits/sec to 1 Mb/sec on standard test sequences, while also requiring much lower computational complexity.