nils-herrmann/clean_scirepeval huggingface dataset:
Scalable wavelet video coding using aliasing-reduced hierarchical motion compensation

We describe a spatially scalable video coding framework in which motion correspondences between successive video frames are exploited in the wavelet transform domain. The basic motivation for our coder is that motion fields are typically smooth and, therefore, can be efficiently captured through a multiresolutional framework. A wavelet decomposition is applied to each video frame and the coefficients at each level are predicted from the coarser level through backward motion compensation. To remove the aliasing effects caused by downsampling in the transform, a special interpolation filter is designed with the weighted aliasing energy as part of the optimization goal, and motion estimation is carried out with low pass filtering and interpolation in the estimation loop. Further, to achieve robust motion estimation against quantization noise, we propose a novel backward/forward hybrid motion compensation scheme, and a tree structured dynamic programming algorithm to optimize the backward/forward mode choices. A novel adaptive quantization scheme is applied to code the motion predicted residue wavelet coefficients, Experimental results reveal 0.3-2-dB increase in coded PSNR at low bit rates over the state-of-the-art H.263 standard with all enhancement modes enabled, and similar improvements over MPEG-2 at high bit rates, with a considerable improvement in subjective reconstruction quality, while simultaneously supporting a scalable representation.
An efficient algorithm for optimal margin maximization in multicarrier communication systems

We present a computationally efficient, integer-bit power allocation algorithm for discrete multitone modulation (DMT) which optimally maximizes the performance margin. Using efficient lookup table searches and a Lagrange multiplier bisection search, our algorithm converges faster to the optimal solution than existing optimal techniques and can replace the use of suboptimal methods because of its low computational complexity. A fast algorithm is developed and pseudocode is given as well as numerical and qualitative comparisons to existing methods.
Sub-linear time compressed sensing using sparse-graph codes

We consider the problem of recovering the support of an arbitrary K-sparse N-length vector in the presence of noise, where the sparsity K = O(Nδ) is sub-linear in N for some 0 <; δ <; 1. A new family of sparse measurement matrices is introduced with a low-complexity recovery algorithm, which achieves a sub-linear measurement cost O(K log1.3̇ N) and sub-linear computational complexity O(K log1.3̇ N). Our measurement system is designed to capture observations of the signal through the parity constraints of sparse-graph codes, and to recover the signal by using a simple peeling decoder. We formally connect general sparse recovery problems with sparse-graph decoding, and showcase our design in terms of the measurement cost, computational complexity and recovery performance.
Unequal Growth Codes: Intermediate Performance and Unequal Error Protection for Video Streaming

We investigate the design of fountain codes with good intermediate performance and built-in unequal error protection for low-delay video multicast. In particular, we design novel short-blocklength fountain codes for media streaming applications to multiple heterogeneous receivers and analyze their performance. Our theoretical contribution is the generalization of the growth code analysis for unequal error protection to suit the characteristics of video data. Simulation results show that the proposed method can effectively increase the number of decodable packets over a very wide range of packet drop rates and provide smooth and graceful video quality degradation for users with various channel conditions. The proposed scheme also enjoys the important benefits of much lower decoder complexity and simpler system architecture compared to traditional MDS erasure coding based solutions.
Multi-server private information retrieval over unsynchronized databases

Search histories contain detailed and sensitive information about people. Private information retrieval (PIR) aims to hide search histories from service providers by allowing a user to retrieve the wth record of a database without revealing w to the server. However, most known PIR schemes are either very inefficient (and therefore unlikely to gain traction in a practical sense) or reliant on some restrictive assumptions. In this paper, we consider an efficient class of schemes called multi-server PIR. Multi-server PIR assumes that the client communicates with multiple, non-colluding servers, each possessing an identical copy of the database. The current literature does not address the assumption that servers store perfectly-synchronized databases. This seems implausible, especially if servers are not meant to collude. We propose the first multiserver PIR scheme to return the desired record even when servers' databases are not perfectly synchronized. Our scheme asymptotically has the same computational and communication complexity as state-of-the-art PIR schemes for synchronized databases; this comes at the expense of probabilistic success guarantees and two rounds of communication. As a secondary result, our approach can efficiently process multiple concurrent queries in one round of PIR.
Next generation techniques for robust and imperceptible audio data hiding

We combine recent theoretical and algorithmic advances in the area of information-hiding with the current mature knowledge-base in the human audio perception system to propose a novel audio data-hiding technique that significantly pushes the state-of-the-art in the field. Our work is based on a combination of advances in two disjoint fields: information-hiding and human auditory masking. The field of information-hiding has recently seen a resurgence due to advances in the understanding of fundamental bounds from information theory. By integrating this with the human perceptual system knowledge that has been successfully exploited for several years in the audio compression community, we derive a new and improved audio data-hiding technique that finds application in a number of exciting scenarios like music enhancement and digital communications over analog data channels. Our preliminary results show that we can embed data at a rate an order of magnitude higher than existing audio data hiding systems, while being robust to channel noise.
Enhancing peer-to-peer live multicast quality using helpers

Peer-to-peer (P2P) video streaming over the Internet plays an important role in reshaping today's Internet traffic. The performance of a P2P system is typically bottlenecked by the limited upload bandwidth of the participating peers, which typically have asymmetric upload/download bandwidth connections to the Internet. Increasing the streaming bitrate in P2P systems beyond what is sustainable with participating peers' upload bandwidths therefore places extra burden on the content server, clearly not a desirable solution in terms of scalability. Motivated by this, we explore here an alternative architecture based on the notion of "helpers", who are online users with spare upload capacity. We show how efficient utilization of helpers' spare upload capacity can lead to significantly improved streaming bitrate in a P2P network without incurring additional server burden. For instance, a 2000 node P2P system with an average upload bandwidth of 512 kbps can sustain streaming rate of 512 kbps with very little server usage. But with an additional 533 helpers, the system can stream at 640 kbps without incurring any additional server load.
Multicast and unicast real-time video streaming over wireless LANs

We address the problem of real-time video streaming over wireless LANs for both unicast and multicast transmission. The wireless channel is modeled as a packet-erasure channel at the IP level. For the unicast scenario, we describe a novel hybrid Automatic Repeat reQuest (ARQ) algorithm that efficiently combines forward error control (FEC) coding with the ARQ protocol. For the multiple-users scenario, we formulate the problem of real-time video multicast as an optimization of a maximum regret cost function across the multicast user space. The proposed solution efficiently combines progressive source coding with FEC coding. We present a theoretical analysis of the unicast and multicast cases, as well as experimental results that demonstrate the performance advantages of the proposed algorithms over existing methods.
Fundamental Bounds on Power Reduction during Data-Retention in Standby SRAM

The authors study leakage-power reduction in standby random access memories (SRAMs) during data-retention. An SRAM cell requires a minimum critical supply voltage (DRV) above which it preserves the stored-bit reliably. Due to process-variations, the intra-chip DRV exhibits variation with a distribution having a diminishing tail. In order to minimize leakage power while preserving data reliably, existing low-power design methods use a worst-case standby supply voltage. This worst-case voltage is larger than the highest DRV among all cells in an SRAM. In contrast, the approach uses aggressive voltage reduction and counters the ensuing unreliability by an error-control code based memory architecture. Using this approach, we explore fundamental trade-offs between power reduction and redundancy present in the SRAM. The authors establish fundamental bounds on the power reduction in terms of the DRV-distribution using techniques from information theory and algebraic coding theory. For an experimental test-chip DRV-distribution in the 90nm CMOS technology, the authors show that 49% power reduction with respect to (w.r.t.) the worst-case is a fundamental lower bound while 40% power reduction w.r.t. the worst-case is achievable by using a practical algebraic coding scheme. The authors also study the power reduction as a function of the block-length for low-latency codes since most applications using SRAM are latency constrained. The authors propose a reliable low-power memory architecture based on the Hamming code for the next test-chip implementation with a predicted power reduction of 33% while accounting for coding overheads
Achievable rates for multiple-access channels with correlated messages

In this paper, the multiterminal sources is mapped independently into a message set characterized by a graph which preserves a predetermined amount of correlation between the sources, and the message set becomes the input to channel encoder. In this work joint source-channel coding scheme is considered as a part with associated message graph for transmitting distributed correlated sources over MAC. Thus the parameters are allowed to increase exponentially with number of channels and the performance of this characterized set is measured using minimum average probability of error.
Ubiquitous access to distributed data in large-scale sensor networks through decentralized erasure codes

Consider a large-scale wireless sensor network of n nodes, where a fraction k out of n generate data packets of global interest. Assuming that the individual nodes have limited storage and computational capabilities, we address the problem of how to enable ubiquitous access to the distributed data packets. Specifically, we assume that each node can store at most one data packet, and study the problem of diffusing the data so that by querying any k nodes, it is possible to retrieve all the k data packets of interest (with high probability). We introduce a class of erasure codes and show how to solve this problem efficiently in a completely distributed and robust way. Specifically we show that we can efficiently diffuse the data by "pre-routing" only O(ln n) packets per data node to randomly selected storage nodes. By using the proposed scheme, the distributed data becomes available "at the fingertips" of a potential data collector located anywhere in the network.
Information-Theoretically Secure Erasure Codes for Distributed Storage

Repair operations in erasure-coded distributed storage systems involve a lot of data movement. This can potentially expose data to malicious acts of passive eavesdroppers or active adversaries, putting security of the system at risk. This paper presents coding schemes and repair algorithms that ensure security of the data in the presence of passive eavesdroppers and active adversaries while maintaining high availability, reliability, and resource efficiency in the system. The proposed codes are optimal in that they meet previously proposed lower bounds on storage and network-bandwidth requirements for a wide range of system parameters. The results thus establish the secure storage capacity of such systems. The proposed codes are based on an optimal class of codes called product-matrix codes. The constructions presented for security from active adversaries provide an additional appealing feature of “on-demand security,” where the desired level of security can be chosen separately for each instance of repair, and the proposed algorithms remain optimal simultaneously for all possible security levels. This paper also provides necessary and sufficient conditions governing the transformation of any (non-secure) code into one providing on-demand security.
An investigation of wavelet-based image coding using an entropy-constrained quantization framework

Wavelet image decompositions generate a tree-structured set of coefficients, providing an hierarchical data-structure for representing images. Several recently proposed image compression algorithms have focused on new ways for exploiting dependencies between this hierarchy of wavelet coefficients. This paper presents a new framework for understanding the efficiency of one such algorithm as a simplified attempt to a global entropy-constrained image quantizer. The principle insight offered by the new framework is that improved performance is achieved by more accurately characterizing the joint probabilities of arbitrary sets of wavelet coefficients. The specific algorithm described is designed around one conveniently structured collection of such sets. The efficiency of hierarchical wavelet coding algorithms derives from their success at identifying and exploiting dependencies between coefficients in the hierarchical structure. The second part of the paper presents an empirical study of the distribution of high-band wavelet coefficients, the band responsible for most of the performance improvements of the new algorithms.<<ETX>>
Interactive low-complexity codes for synchronization from deletions and insertions

We study the problem of synchronization of two remotely located data sources, which are mis-synchronized due to deletions and insertions. This is an important problem since a small number of synchronization errors can induce a large Hamming distance between the two sources. The goal is to effect synchronization with the rate-efficient use of lossless bidirectional links between the two sources. In this work, we focus on the following model. A binary sequence X of length n is edited to generate the sequence at the remote end, say Y, where the editing involves random deletions and insertions, possibly in small bursts. The problem is to synchronize Y with X with minimal exchange of information (in terms of both the average communication rate and the average number of interactive rounds of communication). We focus here on the case where the number of edits is much smaller than n, and propose an interactive algorithm which is computationally simple and has near-optimal communication complexity. Our algorithm works by efficiently splitting the source sequence into pieces containing either just a single deletion/insertion or a single burst deletion/insertion. Each of these pieces is then synchronized using an optimal one-way synchronization code, based on the single-deletion correcting channel codes of Varshamov and Tenengolts (VT codes).
Securing dynamic distributed storage systems from malicious nodes

We address the problem of securing distributed storage systems against adversarial node attacks. An important aspect of these systems is node failures over time, necessitating, thus, a repair mechanism in order to maintain a desired high system reliability. In such dynamic settings, an important security problem is to safeguard the system from a malicious adversary who may come at different time instances during the lifetime of the storage system to corrupt the data stored on some nodes. We provide upper bounds on the maximum amount of information that can be stored safely on the system in the presence of the adversary. For an important operating regime, which we call the bandwidth-limited regime, we show that our upper bounds are tight and provide explicit linear code constructions. Moreover, we provide a way to shortlist the malicious nodes and expurgate the system.
Tracking and exploiting correlations in dense sensor networks

In this paper, we propose a novel method for reducing energy consumption in a sensor network. It is important in a sensor network to minimize the energy usage of each sensor, because the nodes typically have finite battery life and if a node dies, this can lead to a loss of data or a network partition. As a result, several researchers have proposed various methods of routing and communication between nodes to reduce energy consumption. We propose an orthogonal approach to previous methods. In particular, we propose to exploit the inherent correlations that exist between sensor nodes by devising a novel algorithm that enables sensor nodes to compress their readings without knowing the exact measurements of the other nodes. Our simulations show that our algorithm used is promising as it leads to significant energy saving for various types of sensor nodes.
Sparse covariance estimation based on sparse-graph codes

We consider the problem of recovering a sparse covariance matrix Σ∈ℝn×n from m quadratic measurements yi = aiTΣai+wi, 1 ≤ i ≤ m, where ai ∈ ℓn is a measurement vector and wi is additive noise. We assume that ℝ has K non-zero off-diagonal entries. We first consider the simplified noiseless problem where wi = 0 for all i. We introduce two low complexity algorithms, the first a “message-passing” algorithm and the second a “forward” algorithm, that are based on a sparse-graph coding framework. We show that under some simplifying assumptions, the message passing algorithm can recover an arbitrarily-large fraction of the K non-zero components with cK measurements, where c is a small constant that can be precisely characterized. As one instance, the message passing algorithm can recover, with high probability, a fraction 1 - 10-4 of the non-zero components, using only m = 6K quadratic measurements, which is a small constant factor from the fundamental limit, with an optimal O(K) decoding complexity. We further show that the forward algorithm can recover all the K non-zero entries with high probability with m = Θ(K) measurements and O(K log(K)) decoding complexity. However, the forward algorithm suffers from significantly larger constants in terms of the number of required measurements, and is indeed less practical despite providing stronger theoretical guarantees. We then consider the noisy setting, and show that both proposed algorithms can be robustified to noise with m = Θ(K log2(n)) measurements. Finally, we provide extensive simulation results that support our theoretical claims.
Morphological representation of wavelet data for image coding

Proposes an improved statistical characterization of the field of wavelet coefficients of natural images. Based on this characterization, the authors introduce morphological representation of wavelet data (MRWD), a novel coding framework for both image and video coding applications. MRWD departs from existing wavelet-based coders in its use of a radically different set of primitive operations-non-linear, morphological operations-for efficiently encoding the wavelet data field. Simulation results are very encouraging: a preliminary algorithm based on the morphological data structure is able to achieve about 0.5 dB of gain in SNR over Shapiro's (1993) state-of-the-art zerotree-based wavelet coder at a coding rate of 1 bpp for the "Lena" image.
Secure distributive storage of decentralized source data: Can interaction help?

We consider the problem of securing a distributed storage system with decentralized data, where some of the nodes are compromised by an eavesdropper. The system is formed of n storage nodes among which k nodes (k > n) have information sources. The system is required to have the “MDS property”, i.e., to allow any user to recover all the sources by contacting any k nodes. To achieve this goal, the source nodes need to disseminate their data to the other nodes in the system while revealing no information to the eavesdropper. We investigate the role of interaction between the sources in reducing the total required bandwidth. When the sources are independent, we show that interaction does not help and that there always exists an optimal non-interactive scheme.
Flexible tree-structured signal expansions using time-varying wavelet packets

Addresses the problem of finding the best time-varying filter bank tree-structured representation for a signal. The tree is allowed to vary at regular intervals, and the spacing of these changes can be arbitrarily short. The question of how to choose tree-structured representations of signals based on filter banks is considered. Wavelets and their adaptive version, known as wavelet packets, represent one approach that is popular. Wavelet packets are subband trees where the tree is chosen to match the characteristics of the signal. Variations where the tree varies over time have been proposed as the double tree and the time-frequency tree algorithms. Time-variation adds a further level of adaptivity. In all of the approaches proposed so far, the tree must be either fixed for the whole duration of the signal or fixed for its dyadic subintervals. The solution that we propose, as it allows more flexible variation, is an advance on the wavelet packet algorithm, the double tree algorithm, and the recently proposed time-frequency tree algorithm. Our solution is based on casting it in a dynamic programming (DP) setting. Focusing on compression applications, we use a Lagrangian cost of distortion +/spl lambda//spl times/rate as the objective function and explain our algorithm in detail, pointing out its relation to existing approaches to the problem. We demonstrate that the new algorithm indeed searches a larger library of representations than previously possible and that overcoming the constraint of dyadic time segmentations gives a significant improvement in practice.
Secure source coding with a helper

We consider a secure lossless source coding problem with a rate-limited helper. In particular, Alice observes an i.i.d. source Xn and wishes to transmit this source loss-lessly to Bob at a rate R x . A helper, say Helen, observes a correlated source Yn and transmits at a rate R y to Bob. A passive eavesdropper can observe the coded output of Alice. The equivocation Δ is measured by the conditional entropy H(Xn\ J x )/n, where J x is the coded output of Alice. We first completely characterize the rate-equivocation region for this secure source coding model, where we show that Slepian-Wolf type coding is optimal. We next study two generalizations of this model and provide single-letter characterizations for the respective rate-equivocation regions. In particular, we first consider the case of a two-sided helper where Alice also has access to the coded output of Helen. We show that for this case, Slepian-Wolf type coding is suboptimal and one can further decrease the information leakage to the eavesdropper by utilizing the side-information at Alice. We finally generalize this result to the case when there are both secure and insecure rate-limited links from Helen and additional uncoded side informations Wn and Zn available at Bob and Eve, respectively. For this model, we provide a complete characterization of the rate-equivocation region when Yn → Xn → (Wn, Zn) forms a Markov chain.