OpenRaiser/Intern-Atlas huggingface dataset:
Variable and Thread Bounding for Systematic Testing of Multithreaded Programs
Venue: arXiv cs.PL 2013
Year: 2013

Previous approaches to systematic state-space exploration for testing multi-threaded programs have proposed context-bounding and depth-bounding to be effective ranking algorithms for testing multithreaded programs. This paper proposes two new metrics to rank thread schedules for systematic state-space exploration. Our metrics are based on characterization of a concurrency bug using v (the minimum number of distinct variables that need to be involved for the bug to manifest) and t (the minimum number of distinct threads among which scheduling constraints are required to manifest the bug). Our algorithm is based on the hypothesis that in practice, most concurrency bugs have low v (typically 1- 2) and low t (typically 2-4) characteristics. We iteratively explore the search space of schedules in increasing orders of v and t. We show qualitatively and empirically that our algorithm finds common bugs in fewer number of execution runs, compared with previous approaches. We also show that using v and t improves the lower bounds on the probability of finding bugs through randomized algorithms. Systematic exploration of schedules requires instrumenting each variable access made by a program, which can be very expensive and severely limits the applicability of this approach. Previous work [5, 19] has avoided this problem by interposing only on synchronization operations (and ignoring other variable accesses). We demonstrate that by using variable bounding (v) and a static imprecise alias analysis, we can interpose on all variable accesses (and not just synchronization operations) at 10-100x less overhead than previous approaches.
Fundamental Limits of Communications in Interference Networks-Part I: Basic Structures
Venue: arXiv cs.IT 2013
Year: 2013

In these series of multi-part papers, a systematic study of fundamental limits of communications in interference networks is established. Here, interference network is referred to as a general single-hop communication scenario with arbitrary number of transmitters and receivers, and also arbitrary distribution of messages among transmitters and receivers. It is shown that the information flow in such networks follows similar derivations from many aspects. This systematic study is launched by considering the basic building blocks in Part I. The Multiple Access Channel (MAC), the Broadcast Channel (BC), the Classical Interference Channel (CIC) and the Cognitive Radio Channel (CRC) are proposed as the main building blocks for all interference networks. First, a brief review of existing results regarding these basic structures is presented. New observations are also presented in this regard. Specifically, it is shown that the well-known strong interference conditions for the two-user CIC do not change if the inputs are dependent. Next, new capacity outer bounds are established for the basic structures with two receivers. These outer bounds are all derived based on a unified framework. By using the derived outer bounds, some new capacity results are proved for the CIC and the CRC; a mixed interference regime is identified for the two-user discrete CIC where the sum-rate capacity is established. Also, a noisy interference regime is derived for the one-sided discrete CIC. For the CRC, a full characterization of the capacity region for a class of more-capable channels is obtained. Moreover, it is shown that the derived outer bounds are useful to study the channels with one-sided receiver side information wherein one of the receivers has access to the non-intended message; capacity bounds are also discussed in details for such scenarios.
Fundamental Limits of Communications in Interference Networks-Part IV: Networks with a Sequence of Less-Noisy Receivers
Venue: arXiv cs.IT 2013
Year: 2013

In this fourth part of our multi-part papers, classes of interference networks with a sequence of less-noisy receivers are identified for which a successive decoding scheme achieve the sum-rate capacity. First, the two-receiver networks are analyzed: it is demonstrated that the unified outer bounds derived in Part III of our multi-part papers are sum-rate optimal for network scenarios which satisfy certain less-noisy conditions. Then, the multi-receiver networks are considered. These networks are far less understood. One of the main difficulties in the analysis of such scenarios is how to establish useful capacity outer bounds. In this paper, a novel technique requiring a sequential application of the Csiszar-Korner identity is developed to establish powerful single-letter outer bounds on the sum-rate capacity of multi-receiver interference networks which satisfy certain less-noisy conditions. By using these outer bounds, a full characterization of the sum-rate capacity is derived for general interference networks of arbitrary large sizes with a sequence of less-noisy receivers. Some generalizations of these outer bounds are also presented each of which is efficient to obtain the exact sum-rate capacity for various scenarios.
Buffer-Aided Relaying with Adaptive Link Selection - Fixed and Mixed Rate Transmission
Venue: arXiv cs.IT 2013
Year: 2013

We consider a simple network consisting of a source, a half-duplex DF relay with a buffer, and a destination. We assume that the direct source-destination link is not available and all links undergo fading. We propose two new buffer-aided relaying schemes. In the first scheme, neither the source nor the relay have CSIT, and consequently, both nodes are forced to transmit with fixed rates. In contrast, in the second scheme, the source does not have CSIT and transmits with fixed rate but the relay has CSIT and adapts its transmission rate accordingly. In the absence of delay constraints, for both fixed rate and mixed rate transmission, we derive the throughput-optimal buffer-aided relaying protocols which select either the source or the relay for transmission based on the instantaneous SNRs of the source-relay and the relay-destination links. In addition, for the delay constrained case, we develop buffer-aided relaying protocols that achieve a predefined average delay. Compared to conventional relaying protocols, which select the transmitting node according to a predefined schedule independent of the link instantaneous SNRs, the proposed buffer-aided protocols with adaptive link selection achieve large performance gains. In particular, for fixed rate transmission, we show that the proposed protocol achieves a diversity gain of two as long as an average delay of more than three time slots can be afforded. Furthermore, for mixed rate transmission with an average delay of $E{T}$ time slots, a multiplexing gain of $r=1-1/(2E{T})$ is achieved. Hence, for mixed rate transmission, for sufficiently large average delays, buffer-aided half-duplex relaying with and without adaptive link selection does not suffer from a multiplexing gain loss compared to full-duplex relaying.
Improved Concentration Bounds for Count-Sketch
Venue: arXiv cs.DS 2013
Year: 2013

We present a refined analysis of the classic Count-Sketch streaming heavy hitters algorithm [CCF02]. Count-Sketch uses O(k log n) linear measurements of a vector x in R^n to give an estimate x' of x. The standard analysis shows that this estimate x' satisfies ||x'-x||_infty^2 < ||x_tail||_2^2 / k, where x_tail is the vector containing all but the largest k coordinates of x. Our main result is that most of the coordinates of x' have substantially less error than this upper bound; namely, for any c < O(log n), we show that each coordinate i satisfies (x'_i - x_i)^2 < (c/log n) ||x_tail||_2^2/k with probability 1-2^{-Omega(c)}, as long as the hash functions are fully independent. This subsumes the previous bound and is optimal for all c. Using these improved point estimates, we prove a stronger concentration result for set estimates by first analyzing the covariance matrix and then using a median-of-median-of-medians argument to bootstrap the failure probability bounds. These results also give improved results for l_2 recovery of exactly k-sparse estimates x^* when x is drawn from a distribution with suitable decay, such as a power law or lognormal. We complement our results with simulations of Count-Sketch on a power law distribution. The empirical evidence indicates that our theoretical bounds give a precise characterization of the algorithm's performance: the asymptotics are correct and the associated constants are small. Our proof shows that any symmetric random variable with finite variance and positive Fourier transform concentrates around 0 at least as well as a Gaussian. This result, which may be of independent interest, gives good concentration even when the noise does not converge to a Gaussian.
CSS-like Constructions of Asymmetric Quantum Codes
Venue: arXiv cs.IT 2013
Year: 2013

Asymmetric quantum error-correcting codes (AQCs) may offer some advantage over their symmetric counterparts by providing better error-correction for the more frequent error types. The well-known CSS construction of $q$-ary AQCs is extended by removing the $\F_{q}$-linearity requirement as well as the limitation on the type of inner product used. The proposed constructions are called CSS-like constructions and utilize pairs of nested subfield linear codes under one of the Euclidean, trace Euclidean, Hermitian, and trace Hermitian inner products. After establishing some theoretical foundations, best-performing CSS-like AQCs are constructed. Combining some constructions of nested pairs of classical codes and linear programming, many optimal and good pure $q$-ary CSS-like codes for $q \in {2,3,4,5,7,8,9}$ up to reasonable lengths are found. In many instances, removing the $\F_{q}$-linearity and using alternative inner products give us pure AQCs with improved parameters than relying solely on the standard CSS construction.
Relay Selection for OFDM Wireless Systems under Asymmetric Information: A Contract-Theory Based Approach
Venue: arXiv cs.NI 2013
Year: 2013

User cooperation although improves performance of wireless systems, it requires incentives for the potential cooperating nodes to spend their energy acting as relays. Moreover, these potential relays are better informed than the source about their transmission costs, which depend on the exact channel conditions on their relay-destination links. This results in asymmetry of available information between the source and the relays. In this paper, we use contract theory to tackle the problem of relay selection under asymmetric information in OFDM-based cooperative wireless system that employs decode-and-forward (DF) relaying. We first design incentive compatible offers/contracts, consisting of a menu of payments and desired signal-to-noise-ratios (SNR)s at the destination and then the source broadcasts this menu to nearby mobile nodes. The nearby mobile nodes who are willing to relay notify back the source with the contracts they are willing to accept in each subcarrier. We show that when the source is under a budget constraint, the problem of relay selection in each subcarrier in order to maximize the capacity is a nonlinear non-separable knapsack problem. We propose a heuristic relay selection scheme to solve this problem. We compare the performance of our overall mechanism and the heuristic solution with a simple relay selection scheme and selected numerical results showed that our solution performs better and is close to optimal. The overall mechanism introduced in this paper is simple to implement, requires limited interaction with potential relays and hence requires minimal signalling overhead.
Gaussian process regression as a predictive model for Quality-of-Service in Web service systems
Venue: arXiv cs.NI 2013
Year: 2013

In this paper, we present the Gaussian process regression as the predictive model for Quality-of-Service (QoS) attributes in Web service systems. The goal is to predict performance of the execution system expressed as QoS attributes given existing execution system, service repository, and inputs, e.g., streams of requests. In order to evaluate the performance of Gaussian process regression the simulation environment was developed. Two quality indexes were used, namely, Mean Absolute Error and Mean Squared Error. The results obtained within the experiment show that the Gaussian process performed the best with linear kernel and statistically significantly better comparing to Classification and Regression Trees (CART) method.
Answering n^{2+o(1)} Counting Queries with Differential Privacy is Hard
Venue: arXiv cs.CR 2013
Year: 2013

A central problem in differentially private data analysis is how to design efficient algorithms capable of answering large numbers of counting queries on a sensitive database. Counting queries of the form "What fraction of individual records in the database satisfy the property q?" We prove that if one-way functions exist, then there is no algorithm that takes as input a database D in ({0,1}^d)^n, and k = n^{2+o(1)} arbitrary efficiently computable counting queries, runs in time poly(d, n), and returns an approximate answer to each query, while satisfying differential privacy. We also consider the complexity of answering "simple" counting queries, and make some progress in this direction by showing that the above result holds even when we require that the queries are computable by constant depth (AC-0) circuits. Our result is almost tight in the sense that nearly n^2 counting queries can be answered efficiently while satisfying differential privacy. Moreover, super-polynomially many queries can be answered in exponential time. We prove our results by extending the connection between differentially private counting query release and cryptographic traitor-tracing schemes to the setting where the queries are given to the sanitizer as input, and by constructing a traitor-tracing scheme that is secure in this setting.
Signal Space CoSaMP for Sparse Recovery with Redundant Dictionaries
Venue: arXiv cs.IT 2013
Year: 2013

Compressive sensing (CS) has recently emerged as a powerful framework for acquiring sparse signals. The bulk of the CS literature has focused on the case where the acquired signal has a sparse or compressible representation in an orthonormal basis. In practice, however, there are many signals that cannot be sparsely represented or approximated using an orthonormal basis, but that do have sparse representations in a redundant dictionary. Standard results in CS can sometimes be extended to handle this case provided that the dictionary is sufficiently incoherent or well-conditioned, but these approaches fail to address the case of a truly redundant or overcomplete dictionary. In this paper we describe a variant of the iterative recovery algorithm CoSaMP for this more challenging setting. We utilize the D-RIP, a condition on the sensing matrix analogous to the well-known restricted isometry property. In contrast to prior work, the method and analysis are "signal-focused"; that is, they are oriented around recovering the signal rather than its dictionary coefficients. Under the assumption that we have a near-optimal scheme for projecting vectors in signal space onto the model family of candidate sparse signals, we provide provable recovery guarantees. Developing a practical algorithm that can provably compute the required near-optimal projections remains a significant open problem, but we include simulation results using various heuristics that empirically exhibit superior performance to traditional recovery algorithms.
Rejecting the Attack: Source Authentication for Wi-Fi Management Frames using CSI Information
Venue: arXiv cs.NI 2013
Year: 2013

Comparing to well protected data frames, Wi-Fi management frames (MFs) are extremely vulnerable to various attacks. Since MFs are transmitted without encryption, attackers can forge them easily. Such attacks can be detected in cooperative environment such as Wireless Intrusion Detection System (WIDS). However, in non-cooperative environment it is difficult for a single station to identify these spoofing attacks using Received Signal Strength (RSS)-based detection, due to the strong correlation of RSS to both the transmission power (Txpower) and the location of the sender. By exploiting some unique characteristics (i.e., rapid spatial decorrelation, independence of Txpower, and much richer dimensions) of the Channel State Information (CSI), a standard feature in 802.11n Specification, we design a prototype, called CSITE, to authenticate the Wi-Fi management frames by a single station without external support. Our design CSITE, built upon off-the-shelf hardware, achieves precise spoofing detection without collaboration and in-advance finger-print. Several novel techniques are designed to address the challenges caused by user mobility and channel dynamics. To verify the performances of our solution, we implement a prototype of our design and conduct extensive evaluations in various scenarios. Our test results show that our design significantly outperforms the RSS-based method in terms of accuracy, robustness, and efficiency: we observe about 8 times improvement by CSITE over RSS-based method on the falsely accepted attacking frames.
Description of the Chord Protocol using ASMs Formalism
Venue: arXiv cs.DC 2013
Year: 2013

This paper describes the overlay protocol Chord using the formalism of Abstract State Machines. The formalization concerns Chord actions that maintain ring topology and manipulate distributed keys. We define a class of runs and prove the correctness of our formalization with respect to it.
Link Scheduling for Throughput Maximization in Multihop Wireless Networks Under Physical Interference
Venue: arXiv cs.NI 2013
Year: 2013

We consider the problem of link scheduling for throughput maximization in multihop wireless networks. Majority of previous methods are restricted to graph-based interference models. In this paper we study the link scheduling problem using a more realistic physical interference model. Through some key observations about this model, we develop efficient link scheduling algorithms by exploiting the intrinsic connections between the physical interference model and the graph-based interference model. For one variant of the problem where each node can dynamically adjust its transmission power, we design a scheduling method with O(g(E)) approximation to the optimal throughput capacity where g(E) denotes length diversity. For the other variant where each node has a fixed but possible different transmission powers for different nodes, we design a method with O(g(E))-approximation ratio when the transmission powers of all nodes are within a constant factor of each other, and in general with an approximation ratio of O(g(E)logρ) where logρis power diversity. We further prove that our algorithm for fixed transmission power case retains O(g(E)) approximation for any length-monotone, sub-linear fixed power setting. Furthermore, all these approximation factors are independent of network size.
Fast-Decodable MIDO Codes with Large Coding Gain
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, a new method is proposed to obtain full-diversity, rate-2 (rate of 2 complex symbols per channel use) space-time block codes (STBCs) that are full-rate for multiple input, double output (MIDO) systems. Using this method, rate-2 STBCs for $4\times2$, $6 \times 2$, $8\times2$ and $12 \times 2$ systems are constructed and these STBCs are fast ML-decodable, have large coding gains, and STBC-schemes consisting of these STBCs have a non-vanishing determinant (NVD) so that they are DMT-optimal for their respective MIDO systems. It is also shown that the SR-code [R. Vehkalahti, C. Hollanti, and F. Oggier, "Fast-Decodable Asymmetric Space-Time Codes from Division Algebras," IEEE Trans. Inf. Theory, Apr. 2012] for the $4\times2$ system, which has the lowest ML-decoding complexity among known rate-2 STBCs for the $4\times2$ MIDO system with a large coding gain for 4-/16-QAM, has the same algebraic structure as the STBC constructed in this paper for the $4\times2$ system. This also settles in positive a previous conjecture that the STBC-scheme that is based on the SR-code has the NVD property and hence is DMT-optimal for the $4\times2$ system.
Sets of Zero-Difference Balanced Functions and Their Applications
Venue: arXiv cs.IT 2013
Year: 2013

Zero-difference balanced (ZDB) functions can be employed in many applications, e.g., optimal constant composition codes, optimal and perfect difference systems of sets, optimal frequency hopping sequences, etc. In this paper, two results are summarized to characterize ZDB functions, among which a lower bound is used to achieve optimality in applications and determine the size of preimage sets of ZDB functions. As the main contribution, a generic construction of ZDB functions is presented, and many new classes of ZDB functions can be generated. This construction is then extended to construct a set of ZDB functions, in which any two ZDB functions are related uniformly. Furthermore, some applications of such sets of ZDB functions are also introduced.
Compressed Hypothesis Testing: to Mix or Not to Mix?
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we study the hypothesis testing problem of, among $n$ random variables, determining $k$ random variables which have different probability distributions from the rest $(n-k)$ random variables. Instead of using separate measurements of each individual random variable, we propose to use mixed measurements which are functions of multiple random variables. It is demonstrated that $O({\displaystyle \frac{k \log(n)}{\min_{P_i, P_j} C(P_i, P_j)}})$ observations are sufficient for correctly identifying the $k$ anomalous random variables with high probability, where $C(P_i, P_j)$ is the Chernoff information between two possible distributions $P_i$ and $P_j$ for the proposed mixed observations. We characterized the Chernoff information respectively under fixed time-invariant mixed observations, random time-varying mixed observations, and deterministic time-varying mixed observations; in our derivations, we introduced the \emph{inner and outer conditional Chernoff information} for time-varying measurements. It is demonstrated that mixed observations can strictly improve the error exponent of hypothesis testing, over separate observations of individual random variables. We also characterized the optimal mixed observations maximizing the error exponent, and derived an explicit construction of the optimal mixed observations for the case of Gaussian random variables. These results imply that mixed observations of random variables can reduce the number of required samples in hypothesis testing applications. Compared with compressed sensing problems, this paper considers random variables which are allowed to dramatically change values in different measurements.