In this paper, we address the problem of Private Information Retrieval (PIR) over a public Additive White Gaussian Noise (AWGN) channel. In this setting, a curious server—a passive adversary following the protocol but attempting to infer private information from intercepted transmissions—can eavesdrop on other servers' responses, compromising the user's privacy. Prior work on PIR over shared media typically assumed that servers could not overhear each other's transmissions. In contrast, we remove this assumption and consider a fully public channel. We propose a novel joint PIR–channel coding scheme based on nested lattice codes to meet the resulting privacy and reliability challenges. The scheme simultaneously addresses channel noise, ensures user privacy, and protects against curious servers. We demonstrate that a positive PIR rate is achievable even in cases where the channel to the curious server is stronger than the channel to the user.

We consider a Markov decision process (MDP) in which actions prescribed by the controller are executed by a separate actuator, which may behave adversarially. At each time step, the controller selects and transmits an action to the actuator; however, the actuator may deviate from the intended action to degrade the control reward. Given that the controller observes only the sequence of visited states, we investigate whether the actuator can covertly deviate from the controller's policy to minimize its reward without being detected. We establish conditions for covert adversarial behavior over an infinite time horizon and formulate an optimization problem to determine the optimal adversarial policy under these conditions. Additionally, we derive the asymptotic error exponents for detection in two scenarios: (1) a binary hypothesis testing framework, where the actuator either follows the prescribed policy or a known adversarial strategy, and (2) a composite hypothesis testing framework, where the actuator may employ any stationary policy. For the latter case, we also propose an optimization problem to maximize the adversary's performance.

We consider the problem where an active DecisionMaker (DM) is tasked to identify the true hypothesis using as few as possible observations while maintaining accuracy. The DM collects observations according to its determined actions and knows the distributions under each hypothesis. We propose a deterministic and adaptive multi-stage hypothesis-elimination strategy where the DM selects an action, applies it repeatedly, and discards hypotheses in light of its obtained observations. The DM selects actions based on maximal separation expressed by the distance between the parameter vectors of each distribution under each hypothesis. Close distributions can be clustered, simplifying the search and significantly reducing the number of required observations. Our algorithms achieve vanishing Average Bayes Risk (ABR) as the error probability approaches zero, i.e., the algorithm is asymptotically optimal. Furthermore, we show that the ABR is bounded when the number of hypotheses grows. Simulations are carried out to evaluate the algorithm's performance compared to another multi-stage hypothesis-elimination algorithm, where an improvement of several orders of magnitude in the mean number of observations required is observed.

Consider the problem of best arm identification with a security constraint. Specifically, assume a setup of stochastic linear bandits with K arms of dimension d. In each arm pull, the player receives a reward that is the sum of the dot product of the arm with an unknown parameter vector and independent noise. The player’s goal is to identify the best arm after T arm pulls. Moreover, assume a copycat Chloe is observing the arm pulls. The player wishes to keep Chloe ignorant of the best arm.While a minimax–optimal algorithm identifies the best arm with an $\Omega \left({\frac{T}{{\log (d)}}}\right)$ error exponent, it easily reveals its best-arm estimate to an outside observer, as the best arms are played more frequently. A naïve secure algorithm that plays all arms equally results in an $\Omega \left({\frac{T}{d}}\right)$ exponent. In this paper, we propose a secure algorithm that plays with coded arms. The algorithm does not require any key or cryptographic primitives, yet achieves an $\Omega \left({\frac{T}{{{{\log }^2}(d)}}}\right)$ exponent while revealing almost no information on the best arm.

This paper addresses the challenge of best arm identification in stochastic multi-armed bandit (MAB) models under privacy-preserving constraints, such as in dynamic spectrum access networks where secondary users must privately detect underutilized channels. While previous network security research has explored securing MAB algorithms through techniques such as homomorphic encryption or differential privacy, these methods often suffer from high computational overhead or introduce noise that strictly decreases accuracy. In contrast, this work focuses on lightweight solutions that ensure data confidentiality without compromising the accuracy of best arm identification. We introduce two secure protocols that leverage additive secret sharing and threshold secret sharing. The proposed model, employing aggregation nodes and a comparator node, securely distributes computations to prevent any entity from accessing complete reward or ranking data. Furthermore, the protocol ensures resistance to collusion and fault tolerance, while maintaining computational efficiency. These contributions establish a scalable and robust framework for privacy-preserving best arm identification, offering practical and secure solutions that use MAB methods for network security.

This paper revisits the problems of Private Information Retrieval (PIR) and Symmetric PIR (SPIR). In PIR, a user retrieves a desired message fromNreplicated, non-communicating databases, each storing the sameMmessages, while preserving the privacy of the requested message index. SPIR extends this notion further by additionally protecting the privacy of the databases, ensuring that the user learns no information beyond the requested message. In this paper, we assume a block-fading Additive White Gaussian Noise Multiple Access Channel (AWGN MAC) linking the user and the databases. Previous work presented a joint channel-PIR scheme utilizing the Compute and Forward (C&F) protocol, demonstrating the potential of a joint PIR-channel coding scheme over a separated one, yet still lagging behind the channel capacity and requiring significant computational complexity. We propose an improved scheme that offers reduced computational complexity while improving the achievable rate for finite parameters, as well as its scaling laws. Specifically, the achievable rate outperforms the C&F-based approach and scales with the number of databasesNand the powerPsimilarly to the channel capacitywithout the privacy constraint. Furthermore, the analysis demonstrates that the improved rate exhibits only a finite gap from this unconstrained channel capacity –$1~bit/sec/Hz$asNincreases. Finally, we provide two SPIR schemes. The first is a modification for our PIR scheme to attain SPIR with no rate loss, which is accomplished by introducing shared common randomness among databases. The second is a novel joint channel-SPIR scheme that utilizes the channel and lattice codes characteristics to nontrivially achieve SPIR without requiring common randomness, at the price of a loss in the achievable rate.

Consider the problem of controlling an unstable process while using as little information as possible. There is a fundamental trade-off between the amount of information used per sample and the controller's performance. Indeed, very recently, Kostina et al. 2022 considered the specific case of an unstable AR(1) process with bounded noise in$[-B, B]$and showed that with a fixed rate per sample control, an unstable process with a gain$\alpha > 1$has a fundamental limit of$\lfloor\alpha\rfloor+1$quantization levels per sample. E.g., with$1 < \alpha < 2$, there is a fundamental limit of 1 bit per sample. We revisit the problem assuming an average rate per sample constraint. We show that not only the 1 bit per sample bound is pessimistic, one can control an unstable AR(1) process at a negligible rate for reasonable$\alpha$, with a simple interleaved application of$a$1-bit quantizer. In this case, we derive a new converse result for average rate control and show it is much lower than that with a fixed rate. The achievable scheme we suggest asymptotically matches the lower bound. We give a practical and simple controller with a bit-rate close to the theoretical limit shown in [l]. For example, with$\alpha=1+\epsilon$, we prove that a rate of$\log_{2}(1+\in)=\frac{\epsilon}{\ln(2)}+^{-}O(\epsilon^{2})$bits per sample is necessary, yet a rate$\frac{1}{\left\lfloor\frac{\ln (2)}{6}\right\rfloor}$is achievable.

This paper revisited the problem of Private Information Retrieval (PIR), where there are$N$replicated non-communicating databases containing the same$M$messages, and a user who wishes to retrieve one of the messages without revealing the wanted message's index to the databases. However, we assume a block-fading additive white Gaussian noise multiple access channel (AWGN MAC) linking the user and the databases. Previous work [1] presented a joint channel-PIR scheme, utilizing the Compute and Forward protocol, showing the potential of a joint channel-PIR scheme over a separated one. In this paper, we propose an improved joint scheme tailored for the PIR problem with$N$databases over a block-fading AWGN. Unlike the C&F protocol, our scheme offers reduced computational complexity while improving the scaling laws governing the achievable rate. Specifically, the achievable rate scales with the number of databases$N$and the power$P$similarly to the channel capacity without the privacy constraint and outperforms the C&F-based approach. Furthermore, the analysis demonstrates that the improved rate exhibits only a finite gap from the unconstrained channel capacity - one bit per second per Hz as$N$increases.

We consider the standard Multi-User Multiple-Input-Multiple-Output (MU-MIMO) system, where only$K$active users, unknown in advance, out of$N$, wish to convey their messages to a single receiver. We derive two necessary lower bounds on the number of antennas (degrees of freedom) on both the receiver and transmitter sides, where the first holds for any MU-MIMO system and the second holds for any energy detection-based MU-MIMO. Then, we revisit techniques with identical scaling laws, such as compressive sensing and group testing, and discuss when the optimal antenna scaling laws for the MU-MIMO problem can be obtained. We also numerically evaluate the presented bounds and compare them against recent achievability results from the last ISIT.

The number of wireless devices continues to grow, and more antennas per device are added, increasing the challenge of efficient resource allocation, especially for uplink streams. To address this, we propose a novel massive multiple-user multiple-input-multiple-output (MU-MIMO) scheme based on Group Testing (GT) with non-cooperative self-scheduling users, reducing the required overhead and complexity. Specifically, we show that out of a population ofNdevices withMmessages each, it is possible for the base station (BS) to jointly identify and decode up toKdevices, unknown in advance, simultaneously without the BS applying any scheduling algorithm or collecting channel state information. The BS efficiently decodes the transmissions with vanishing error probability using onlyO(KlogNM) antennas, which implies order–optimal number of antennas.

Consider the problem of covertly controlling a linear system. In this problem, Alice desires to control (stabilize or change the behavior of) a linear system, while keeping an observer, Willie, unable to decide if the system is indeed being controlled or not. We formally define the problem, under a model where Willie can only observe the system’s output. Focusing on AR(1) systems, we show that when Willie observes the system’s output through a clean channel, an inherently unstable linear system cannot be covertly stabilized. However, under some conditions on the parameters and observation time, an inherently stable linear system can be covertly controlled, in the sense of covertly changing its parameter or resetting its memory. Moreover, we give positive and negative results for two important controllers: a minimal-information controller, where Alice is allowed to use only 1 bit per sample, and a maximal-information controller, where Alice is allowed to view the real-valued output. The results reveal an interesting interplay in covert control, between the amount of information used by the c ontroller, control performance and covertness.

Group Testing (GT) addresses the problem of identifying a small subset of defective items from a large population, by grouping items into as few test pools as possible. In Adaptive GT (AGT), outcomes of previous tests can influence the makeup of future tests. Using an information theoretic point of view, Aldridge 2012 showed that in the regime of a few defectives, adaptivity does not help much, as the number of tests required is essentially the same as for non-adaptive GT. Secure GT considers a scenario where there is an eavesdropper who may observe on average a fraction$\delta $of the tests results, yet should not be able to infer the status of the items. In the non-adaptive scenario, the number of tests required is$1/(1-\delta)$times the number of tests without the secrecy constraint. In this paper, we consider Secure Adaptive GT. Specifically, when during the makeup of the pools one has access to a private feedback link from the lab, of rate$R_{f}$. We prove that the number of tests required for both correct reconstruction at the legitimate lab, with high probability, and negligible mutual information at the eavesdropper is$1/min\{1,1-\delta +R_{f}\}$times the number of tests required with no secrecy constraint. Thus, unlike non-secure GT, where an adaptive algorithm has only a mild impact, under a security constraint it can significantly boost performance. A key insight is that not only the adaptive link should disregard the actual test results and simply send keys, these keys should be enhanced through a “secret sharing” scheme before usage. We derive sufficiency and necessity bounds that completely characterizes the Secure Adaptive GT capacity. Moreover, we consider additional models of Secure Adaptive GT, where we make a clear distinction between the lab performing the tests, and the doctor analyzing the results. Specifically, we consider curious but non-malicious, non-cooperating labs. Each lab gets a fraction$\delta $of pool-tests to perform. Yet, we want to keep each lab ignorant regarding the status of the items. In contrast, the doctor who gets all outcomes, should successfully decode. When there is a feedback from each lab, we show that even if a curious lab obviously sees its own feedback (i.e., it is locally-public to Eve), secure adaptive GT is still possible, and at a rate that can be equal to the one without a security constraint at all, by an application of the Leftover Hash Lemma, using the data of one lab to protect against another.

In the above article[1], the authors introduced a PIR scheme for the Additive White Gaussian Noise (AWGN) Multiple Access Channel (MAC), both with and without fading. The authors utilized the additive nature of the channel and leveraged the linear properties and structure of lattice codes to retrieve the desired message without the servers acquiring any knowledge about the retrieved message’s index. Theorems 3 and 4 in[1]contain an error arising from the incorrect usage of the modulo operator. Moreover, the proofs assume a one-to-one mapping function,$\phi (\cdot)$, between a message$W_{j}\in \mathbb {F}_{p}^{L}$and the elements of$\mathcal { C}$, mistakenly suggesting that the user possesses all the required information in advance. To deal with that, we defined$\phi (\cdot)$as a one-to-one mapping function between a vector oflinformation bits and a lattice point$\lambda \in {\mathcal { C}}$. Herein, we present the corrected versions of these theorems.

The number of wireless devices continues to grow, and more antennas per device are being added, increasing the challenge of efficient resource allocation, especially for uplink streams. To address this, we propose a novel massive multipleuser multiple-input-multiple-output (MU-MIMO) scheme based on Group Testing (GT) with non-cooperative self-scheduling users, reducing the required overhead and complexity. Specifically, we show that out of a population of N devices with $\mathcal{M}$ messages each, it is possible for the base station (BS) to jointly identify and decode up to K devices, unknown in advance, simultaneously and without any scheduling or channel state information. The BS efficiently decodes the transmissions with vanishing error probability using only $O(K\log N\mathcal{M})$ antennas, which implies order–optimal sum-rate.

Consider the problem of guessing a sequence subject to a distortion constraint. Specifically, assume the following game between Alice and Bob: Alice has a sequence x of length n. Bob wishes to guess x, yet he is satisfied with finding any sequence $\hat x$ which is within a given distortion D from x. Thus, he successively submits queries to Alice, until receiving an affirmative answer, stating that his guess was within the required distortion. Finding guessing strategies which minimize the number of guesses and analyzing its properties has applications in information security, source and channel coding. Guessing subject to a distortion constraint is especially useful when considering biometrically-secured systems, where the "password" which protects the data is not a single, fixed vector but rather a ball of feature vectors centered at some x, and any feature vector within the ball results in acceptance. We formally define the guessing problem under distortion in four different setups: memoryless sources, guessing through a noisy channel, sources with memory, and individual sequences. We suggest a randomized guessing strategy which is asymptotically optimal for all setups and is five–fold universal, as it is independent of the source statistics, the channel, the moment to be optimized, the distortion measure and the distortion level.

Consider the problem of covertly controlling a linear system. In this problem, Alice desires to control (stabilize or change the parameters of) a linear system, while keeping an observer, Willie, unable to decide if the system is indeed being controlled or not.We formally define the problem, under the model when Willie can only observe the system’s output. Focusing on AR(1) systems, we show that when Willie observes the system’s output through a clean channel, an inherently unstable linear system can not be covertly stabilized. However, an inherently stable linear system can be covertly controlled, in the sense of covertly changing its parameter. Moreover, we give positive and negative results for two important controllers: a minimal-information controller, where Alice is allowed to use only 1 bit per sample, and a maximal-information controller, where Alice is allowed to view the real-valued output. Unlike covert communication, where the trade-off is between rate and covertness; and in cyber-physical systems the trade-off is between control and attack detection, the results reveal an interesting three–fold trade–off in covert control: the amount of information used by the controller, control performance and covertness. To the best of our knowledge, this is the first study formally defining covert control.

In this paper, we consider the problem of guessing a sequence subject to a distortion constraint. Specifically, we assume the following game between Alice and Bob: Alice has a sequence${x}$of length$n$. Bob wishes to guess${x}$, yet he is satisfied with finding any sequence$\hat {x}$which is within a given distortion$D$from$x$. Thus, he successively submits queries to Alice, until receiving an affirmative answer, stating that his guess was within the required distortion. Finding guessing strategies which minimize the number of guesses (the guesswork), and analyzing its properties (e.g., its$\rho $–th moment) has several applications in information security, source and channel coding. Guessing subject to a distortion constraint is especially useful when considering contemporary biometrically–secured systems, where the “password” which protects the data is not a single, fixed vector but rather a ball of feature vectors centered at some${x}$, and any feature vector within the ball results in acceptance. We formally define the guessing problem under distortion in four different setups: memoryless sources, guessing through a noisy channel, sources with memory and individual sequences. We suggest a randomized guessing strategy which is asymptotically optimal for all setups and is five–fold universal, as it is independent of the source statistics, the channel, the moment to be optimized, the distortion measure and the distortion level.

Distributed scheduling is an attractive approach for the Multiple-Access Channel (MAC). However, when a subset of the users access the channel simultaneously, distributed rate coordination is necessary, and is a major challenge, since the achievable rate of each user highly depends on the channels of other active users. That is, given a detection technique, e.g., Zero-Forcing (ZF), the rate at which a user can transmit depends on the channels other transmitting users have, a knowledge which is usually unavailable in distributed schemes. Fixing a rate and accepting some outage probability when this rate is too high is common practice in these cases. In this paper, we analyze the outage probability of a distributed, asymptotically optimal threshold-based scheduling algorithm under ZF. We rigorously evaluate the distribution of the relevant projections and give upper and lower bounds on the outage probability as a function of the algorithm parameters. At the limit of a large number of users, the bounds match, resulting in the true asymptotic characterization of the outage probability.

Covert communication conceals transmission of messages between Alice and Bob from an adversary, Willie, who tries to determine if a transmission took place or not. While covert communication in a basic, standard setting where all variables are known to Willie, results in the well-known square-root law, when a jammer is present and assists Alice by creating uncertainty in Willie's decoder, a strictly positive transmission rate is possible. In this work, we analyze the case where the jammer is equipped with multiple antennas. Specifically, we analyze the effect of multiple antennas at the jammer on Alice's transmission power and consequently on the transmission rate. We consider both the case where the channel knowledge of Willie is known as well as the case where it is unknown. We formulate several optimization problems for the transmission strategies of the jammer to maximize his assistance to Alice, in terms of maximizing Bob's received SNR and consequently the covert rate. When the channel information is known to the jammer, we show that under an achievable covertness scheme, the optimal strategy of the jammer is to perform beamforming towards a single direction with all his available power. This direction though, is not trivial, since it reflects a tradeoff point between minimizing the interference at Bob and maximizing the interference at Willie. When the channel knowledge is unknown, we show that the optimal strategy of the jammer is either to transmit isotropically to all directions or to the null-space of Bob, where this choice depends on certain channel conditions. This is in contrast to current schemes in the literature. Furthermore, we extend the optimization problems to the case where Bob is also equipped with multiple antennas, and provide insightful results, shown to be asymptotically optimal, accompanied by simulations.

The principal goal ofGroup Testing(GT) is to identify a small subset of “defective” items from a large population, by grouping items into as few test pools as possible. The test outcome of a pool is positive if it contains at least one defective item, and is negative otherwise. GT algorithms are utilized in numerous applications, and in many of them maintaining the privacy of the tested items, namely, keeping secret whether they are defective or not, is critical. In this paper, we consider a scenario where there is an eavesdropper (Eve) who is able to observe a subset of the GT outcomes (pools). We propose a new non-adaptiveSecure Group Testing(SGT) scheme based on information-theoretic principles. The new proposed test design keeps the eavesdropper ignorant regarding the items’ status. Specifically, when the fraction of tests observed by Eve is$0 \leq \delta < 1$, we prove that with the naive Maximum Likelihood (ML) decoding algorithm the number of tests required for both correct reconstruction at the legitimate user (with high probability) and negligible information leakage to Eve is$\frac {1}{1-\delta }$times the number of tests required with no secrecy constraint for the fixed$K$regime. By a matching converse, we completely characterize the Secure GT capacity. Moreover, we consider the Definitely Non-Defective (DND) computationally efficient decoding algorithm, proposed in the literature for non-secure GT. We prove that with the new secure test design, for$\delta < 1/2$, the number of tests required, without any constraint on$K$, is at most$\frac {1}{1/2-\delta }$times the number of tests required with no secrecy constraint.

Compute and Forward (CF) is a coding scheme which enables receivers to decode linear combinations of simultaneously transmitted messages while exploiting the linear properties of lattice codes and the additive nature of a shared medium. The scheme was originally designed for relay networks, yet, it was found useful in other communication problems, such as MIMO communication. Works in the current literature assume a fixed number of transmitters and receivers in the system. However, following the increase in communication networks density, it is interesting to investigate the performance of CF when the number of transmitters is large. In this work, we show that as the number of transmitters, L, grows, CF becomes degenerated, in the sense that a relay prefers to decode only one (strongest) user instead of any other linear combination of the transmitted codewords, treating the other users as noise. Moreover, the system's sum-rate tends to zero as well. This makes scheduling necessary in order to maintain the superior abilities CF provides. We thus examine the problem of scheduling for CF. We start with insights on why good scheduling opportunities can be found. Then, we provide an asymptotically optimal, polynomial-time scheduling algorithm and analyze its performance. We conclude that with proper scheduling, CF is not merely non-degenerated, but, in fact, provides a gain for the system sum-rate, up to the optimal scaling law of O(loglogL).

We propose to exploit the structure of the correlation between two random variables X and Y via a relaxation on the Common Information problem of Gács and Körner (GK Common Information). Consider two correlated sources X and Y generated from a joint distribution PX,Y. We study embeddings of X into discrete random variables U, such that H(U|Y) ≤ δ, while maximizing I(X; U). When δ = 0, this reduces to the GK Common Information problem. However, unlike the GK Common Information, which is known to be zero for many pairs of random variables (X, Y), we show that this relaxation allows to capture the structure in the correlation between X and Y for a much broader range of joint distributions, and showcase applications for some problems in multi-terminal information theory.

Consider the problem of Private Information Retrieval (PIR) where a user wishes to retrieve a single message from N non-communicating and non-colluding databases (servers). All servers store the same set of M messages and they respond to the user through a block fading Gaussian Multiple Access Channel (MAC). The goal in this setting is to keep the index of the required message private from the servers while minimizing the overall communication overhead.This work provides joint privacy-channel coding retrieval schemes for the AWGN MAC with and without fading. The schemes exploit the linearity of the channel while using the Compute and Forward (CF) coding scheme. Consequently, single-user encoding and decoding are performed to retrieve the private message. The achievable retrieval rates are shown to outperform a separation-based scheme for which the retrieval and the channel coding are designed separately. Moreover, these rates are asymptotically optimal as the SNR grows and are up to a constant gap of 2 bits per channel use for every SNR.

According to recent empirical studies, a majority of users have the same, or very similar, passwords across multiple password-secured online services. This practice can have disastrous consequences, as one password being compromised puts all the other accounts at much higher risk. Generally, an adversary may use any side-information he/she possesses about the user, be it demographic information, password reuse on a previously compromised account, or any other relevant information to devise a better brute-force strategy (so called targeted attack). In this work, we consider a distributed brute-force attack scenario in which m adversaries, each observing some side information, attempt breaching a password secured system. We compare two strategies: an uncoordinated attack in which the adversaries query the system based on their own side-information until they find the correct password, and a fully coordinated attack in which the adversaries pool their side-information and query the system together. For passwords X of length n, generated independently and identically from a distribution PX, we establish an asymptotic closed-form expression for the uncoordinated and coordinated strategies when the side-information Y(m) are generated independently from passing X through a memoryless channel PY|X, as the length of the password n goes to infinity. We illustrate our results for binary symmetric channels and binary erasure channels, two families of side-information channels which model password reuse. We demonstrate that two coordinated agents perform asymptotically better than any finite number of uncoordinated agents for these channels, meaning that sharing side-information is very valuable in distributed attacks.

The 802.11ac is a significant landmark in wireless communications, as it pushes towards new rate limits by utilizing downlink multiuser multiple-input multiple-output (MIMO) beamforming to transmit data to various locations simultaneously. However, successful beamforming relies on intelligent user selection which requires, in turn, extensive overhead of channel calibration between the AP and each of the candidate users. The large overhead involved in the user selection procedure overwhelms the multiuser gain and hinders the utilization of multiuser MIMO. The phenomenon is even more acute when APs handle large groups of mobile users, which frequently associate and disconnect, making the process of acquiring channel state from all users and selecting the appropriate group even harder. Thus, the subtle relation between the achievable rate of a scheduling algorithm and the overhead it requires is significant for the 802.11ac performance analysis. In this paper, we provide a rigorous analysis of distributed algorithms that schedule a group of users for the downlink. In particular, we accommodate common scheduling methods for the 802.11ac protocol and analyze both their achievable rate and their calibration process overhead. Both analysis and extensive simulations depict the superiority of simple threshold-based methods in terms of the throughput.

Data collection in Wireless Sensor Networks (WSN) draws significant attention, due to emerging interest in technologies ranging from Internet of Things (IoT) networks to simple “Presence” applications, which identify the status of the devices (active or inactive). Numerous Medium Access Control (MAC) protocols for WSN, which can address the challenge of data collection in dense networks, were suggested over the years. Most of these protocols utilize the traditional layering approach, in which the MAC layer is unaware of the encapsulated packet payload, and therefore there is no connection between the data collected, the physical layer and the signaling mechanisms. Nonetheless, in many of the applications that intend to utilize such protocols, nodes may need to exchange very little information, and do so only sporadically, that is, while the number of devices in the network can be very large, only a subset wishes to transmit at any given time. Thus, a tailored protocol, which matches the signaling, physical layer and access control to traffic patterns is required. In this work, we design and analyze a data collection protocol based on information theoretic principles. In the suggested protocol, the sink collects messages from up to K sensors simultaneously, out of a large population of sensors, without knowing in advance which sensors will transmit, and without requiring any synchronization, coordination or management overhead. In other words, neither the sink nor the other sensors need to know who are the actively transmitting sensors, and this data is decoded directly from the channel output. We provide a simple codebook construction with very simple encoding and decoding procedures. We further design a secure version of the protocol, in which an eavesdropper observing only partial information sent on the channel cannot gain significant information on the messages transmitted or even which are the sources that sent these messages.

In this work, we study the optimal configuration of the physical layer in wireless networks by means of Semi-Markov Decision Process (SMDP) modeling. In particular, assume the physical layer is characterized by a set of potential operating points, with each point corresponding to a rate and reliability pair; for example, these pairs might be obtained through a now-standard diversity-multiplexing tradeoff characterization. Given the current network state (e.g., buffer occupancies), a Decision Maker (DM) needs to dynamically decide which operating point to use. The SMDP problem formulation allows us to choose from these points. A solution to the SMDP problem is an optimal selection of operating points, which is expressed by a decision rule as a function of the number of packets in the source's finite queue, the channel state, and the size of the packet to be transmitted. We derive a general solution to the SMDP which covers various model configurations, packet size distributions and channel dynamics. For the specific case of exponential transmission times, we analytically prove the optimal policy has a threshold structure. Numerical results validate this finding, as well as depict muti-threshold policies for time varying channels such as the Gilbert-Elliott channel.

Consider the problem of guessing a random vector X by submitting queries (guesses) of the form "Is X equal to x?" until an affirmative answer is obtained. A key figure of merit is the number of queries required until the right vector is guessed, termed the guesswork. The goal is to devise a guessing strategy which minimizes a certain guesswork moment. We study a universal, decentralized scenario where the guesser does not know the distribution of X, and is not allowed to prepare a list of words to be guessed in advance, or to remember its past guesses. Such a scenario is useful, for example, if bots within a Botnet carry out a brute-force attack to guess a password or decrypt a message, yet cannot coordinate the guesses or even know how many bots actually participate in the attack. We devise universal decentralized guessing strategies, first, for memoryless sources, and then generalize them to finite-state sources. For both, we derive the guessing exponent and prove its asymptotic optimality by deriving a matching converse. The strategies are based on randomized guessing using a universal distribution. We also extend the results to guessing with side information (SI). Finally, we design simple algorithms for sampling from the universal distributions.

Covert communication conceals transmission of messages from Alice to Bob out of a watchful adversary, Willie, which tries to determine if a transmission took place or not. While covert communication in a basic, vanilla settings where all variables are known to Willie results in the well known square-root law, when a jammer is present and assists Alice by creating uncertainty in Willie's decoder, this transmission may have a positive rate.In this work, we analyze the case where the jammer is equipped with multiple antennas and obtain the optimal transmission strategy of the jammer in order to maximize his assistance to Alice, in terms of maximizing a ratio between Willie's and Bob's noise variance. We show that the optimal strategy of the jammer is to perform beamforming towards a single direction with all his available power. This direction though, is not trivial, since it reflects an optimal tradeoff point between minimizing the interference at Bob and maximizing the interference at Willie.

The principal mission of multi-source multicast (MSM) is to disseminate all messages from all sources in a network to all destinations. MSM is utilized in numerous applications. In many of them, securing the messages disseminated is critical. A common secure model is to consider a network where there is an eavesdropper which is able to observe a subset of the network links, and seeks a code which keeps the eavesdropper ignorant regarding all the messages. While this is solved when all messages are located at a single source, secure MSM (SMSM) is an open problem, and the rates required are hard to characterize in general. In this paper, we consider individual security, which promises that the eavesdropper has zero mutual information with each message individually, or, more generally, with sub sets of messages. We completely characterize the rate region for SMSM under individual security, and show that such a security level is achievable at the full capacity of the network, that is, the cut-set bound is the matching converse, similar to non-secure MSM. Moreover, we show that the field size is similar to non-secure MSM and does not have to be larger due to the security constraint.

In September 2017, McAffee Labs quarterly report estimated that brute force attacks represent 20\% of total network attacks, making them the most prevalent type of attack ex-aequo with browser based vulnerabilities. These attacks have sometimes catastrophic consequences, and understanding their fundamental limits may play an important role in the risk assessment of password-secured systems, and in the design of better security protocols. While some solutions exist to prevent online brute-force attacks that arise from one single IP address, attacks performed by botnets are more challenging. In this paper, we analyze these distributed attacks by using a simplified model. Our aim is to understand the impact of distribution and asynchronization on the overall computational effort necessary to breach a system. Our result is based on Guesswork, a measure of the number of queries (guesses) required of an adversary before a correct sequence, such as a password, is found in an optimal attack. Guesswork is a direct surrogate for time and computational effort of guessing a sequence from a set of sequences with associated likelihoods. We model the lack of synchronization by a worst-case optimization in which the queries made by multiple adversarial agents are received in the worst possible order for the adversary, resulting in a min-max formulation. We show that, even without synchronization, and for sequences of growing length, the asymptotic optimal performance is achievable by using randomized guesses drawn from an appropriate distribution. Therefore, randomization is key for distributed asynchronous attacks. In other words, asynchronous guessers can asymptotically perform brute-force attacks as efficiently as synchronized guessers.

Group Testing (GT) addresses the problem of identifying a small subset of defective items from a large population, by grouping items into as few test pools as possible. In Adaptive GT (AGT), outcomes of previous tests can influence the makeup of future tests. This scenario has been studied from an information theoretic point of view. Aldridge 2012 showed that in the regime of a few defectives, adaptivity does not help much, as the number of tests required for identification of the set of defectives is essentially the same as for non-adaptive GT. Secure GT considers a scenario where there is an eavesdropper who may observe a fraction δ of the outcomes, and should not be able to infer the status of the items. In the non-adaptive scenario, the number of tests required is 1/(1-δ) times the number of tests without the secrecy constraint. In this paper, we consider Secure Adaptive GT. Specifically, when an adaptive algorithm has access to a private feedback link of rate Rf, we prove that the number of tests required for both correct reconstruction at the legitimate user, with high probability, and negligible mutual information at the eavesdropper is 1/min{1,1-δ+Rf} times the number of tests required with no secrecy constraint. Thus, unlike non-secure GT, where an adaptive algorithm has only a mild impact, under a security constraint it can significantly boost performance. A key insight is that not only the adaptive link should disregard test results and send keys, these keys should be enhanced through a “secret sharing” scheme before usage.

Distributed scheduling is an attractive approach for the Multiple-Access Channel (MAC). However, when a subset of the users access the channel simultaneously, distributed rate coordination is necessary, and is a major challenge, since the channel capacity of each user highly depends on the channels of other active users. That is, given a detection technique, e.g., Zero-Forcing (ZF), the rate at which a user can transmit depends on the channels other transmitting users have, a knowledge which is usually unavailable in distributed schemes. Fixing a rate and accepting some outage probability when this rate is too high is common practice in these cases. In this paper, we analyze the outage probability of a distributed, asymptotically optimal threshold-based scheduling algorithm under ZF. We rigorously evaluate the distribution of the relevant projections, and give upper and lower bounds on the outage probability as a function of the algorithm parameters.

Consider a Compute and Forward (CF) relay network with L users and a single relay. The relay tries to decode a linear function of the transmitted signals. For such a network, letting all L users transmit simultaneously, especially when L is large, causes a significant degradation in the rate in which the relay is able to decode. In fact, the rate goes to zero very fast with L. Therefore, in each transmission phase only a fixed number of users should transmit, i.e., users should be scheduled. In this work, we examine the problem of scheduling for CF and lay the foundations for identifying the optimal schedule which, to date, lacks a clear understanding. Specifically, we start with insights why when the number of users is large, good scheduling opportunities can be found. Then, we provide an asymptotically optimal, polynomial time scheduling algorithm and analyze it's performance. We conclude that scheduling under CF provides a gain in the system sum-rate, up to the optimal scaling law of O(log log L).

A distributed binary hypothesis testing problem involving two parties, a remote observer and a detector, is studied. The remote observer has access to a discrete memoryless source, and communicates its observations to the detector via a rate-limited noiseless channel. The detector tests for the independence of its own observations with that of the observer, conditioned on some additional side information. While the goal is to maximize the type 2 error exponent of the test for a given type 1 error probability constraint, it is also desired to keep a private part, which is correlated with the observer's observations, as oblivious to the detector as possible. Considering equivocation and average distortion as the metrics of privacy at the detector, a tight single-letter characterization of the rate-error exponent-equivocation and rate-error exponent-distortion tradeoff is obtained.

Consider the problem of a multiple access channel with a large number of users. In such a system, mostly due to practical constraints (e.g., decoding complexity), not all users can be scheduled together, and usually only one user may transmit at any given time. Assuming a distributed, opportunistic scheduling algorithm, we analyze the system's properties, such as delay, QoS, and capacity scaling laws. Specifically, we start with analyzing the performance while assuming the users are not necessarily fully backlogged, focusing on the queuing problem and, especially, on the strong dependence between the queues. We first extend a known queuing model by Ephremides and Zhu, to give new results on the convergence of the probability of collision to its average value (as the number of users grows), and hence for the ensuing system performance metrics, such as throughput and delay. This model, however, is limited in the number of users one can analyze. We thus suggest a new model, which is much simpler yet can accurately describe the system behavior when the number of users is large. We then proceed to the analysis of this system under the assumption of time dependent channels. Specifically, we assume each user experiences a different channel state sequence, expressing different channel fluctuations (specifically, the Gilbert-Elliott model). The system performance under this setting is analyzed, along with the channel capacity scaling laws.

Consider the problem of a multiple-input multiple-output multiple-access channel at the limit of large number of users. Clearly, in practical scenarios, only a small subset of the users can be scheduled to utilize the channel simultaneously. Thus, a problem of user selection arises. However, since solutions which collect channel state information from all users and decide on the best subset to transmit in each slot do not scale when the number of users is large, distributed algorithms for user selection are advantageous. In this paper, we analyze a distributed user selection algorithm, which selects a group of users to transmit without coordinating between users and without all users sending CSI to the base station. This threshold-based algorithm is analyzed for both zero-forcing and minimum mean square error receivers, and its expected sum rate in the limit of large number of users is investigated. It is shown that for large number of users, it achieves the same scaling laws as the optimal centralized scheme.

Network traffic classification is fundamental to network management and its performance. However, traditional approaches for traffic classification, which were designed to work on a dedicated hardware at very high line rates, may not function well in a virtual software-based environment. In this paper, we devise a novel fingerprinting technique that can be utilized as a software-based solution which enables machine-learning-based classification of ongoing flows. The suggested scheme is very simple to implement and requires minimal resources, yet attains very high accuracy. Specifically, for TCP flows, we suggest a fingerprint that is based on zero-length packets, hence enables a highly efficient sampling strategy which can be adopted with a single content-addressable memory rule. The suggested fingerprinting scheme is robust to network conditions such as congestion, fragmentation, delay, retransmissions, duplications, and losses and to varying processing capabilities. Hence, its performance is essentially independent of placement and migration issues, and thus yields an attractive solution for virtualized software-based environments. We suggest an analogous fingerprinting scheme for user datagram protocol traffic, which benefits from the same advantages as the TCP one and attains very high accuracy as well. Results show that our scheme correctly classified about 97% of the flows on the dataset tested, even on encrypted data.

The principal mission of Multi-Source Multicast (MSM) is to disseminate all messages from all sources in a network to all destinations. MSM is utilized in numerous applications. In many of them, securing the messages disseminated is critical. A common secure model is to consider a network where there is an eavesdropper which is able to observe a subset of the network links, and seek a code which keeps the eavesdropper ignorant regarding all the messages. While this is solved when all messages are located at a single source, Secure MSM (SMSM) is an open problem, and the rates required are hard to characterize in general. In this paper, we consider Individual Security, which promises that the eavesdropper has zero mutual information with each message individually. We completely characterize the rate region for SMSM under individual security, and show that such a security level is achievable at the full capacity of the network, that is, the cut-set bound is the matching converse, similar to non-secure MSM. Moreover, we show that the field size is similar to non-secure MSM and does not have to be larger due to the security constraint.

We study a notion of guesswork, where multiple agents intend to launch a coordinated brute-force attack to find a single binary secret string, and each agent has access to side information generated through either a BEC or a BSC. The average number of trials required to find the secret string grows exponentially with the length of the string, and the rate of the growth is called the guesswork exponent. We compute the guesswork exponent for several multi-agent attacks. We show that a multi-agent attack reduces the guesswork exponent compared to a single agent, even when the agents do not exchange information to coordinate their attack, and try to individually guess the secret string using a predetermined scheme in a decentralized fashion. Further, we show that the guesswork exponent of two agents who do coordinate their attack is strictly smaller than that of any finite number of agents individually performing decentralized guesswork.

Compute and Forward (CF) is a promising relaying scheme which, instead of decoding single messages or forwarding/amplifying information at the relay, decodes linear combinations of the simultaneously transmitted messages. The current literature includes several coding schemes and results on the degrees of freedom in CF, yet for systems with a fixed number of transmitters and receivers. It is unclear, however, how CF behaves at the limit of a large number of transmitters. In this paper, we investigate the performance of CF in that regime. Specifically, we show that as the number of transmitters grows, CF becomes degenerated, in the sense that a relay prefers to decode only one (strongest) user instead of any other linear combination of the transmitted codewords, treating the other users as noise. Moreover, the sum-rate tends to zero as well. This makes scheduling necessary in order to maintain the superior abilities CF provides. Indeed, under scheduling, we show that non-trivial linear combinations are chosen, and the sum-rate does not decay, even without state information at the transmitters and without interference alignment.

This paper studies the problem of the distributed compression of correlated sources with an action-dependent joint distribution. This class of problems is, in fact, an extension of the Slepian-Wolf model, but where cost-constrained actions taken by the encoder or the decoder affect the generation of one of the sources. The purpose of this paper is to study the impact of actions on the achievable rates. In particular, two cases where transmission occurs over a rate-limited link are studied; case A for actions taken at the decoder and case B where actions are taken at the encoder. A complete single-letter characterization of the set of achievable rates is given in both cases. Furthermore, a network coding setup for the case where actions are taken at the encoder is investigated. The sources are generated at different nodes of the network and are required at a set of terminal nodes, yet transmission occurs over a general, acyclic, directed network. For this setup, generalized cut-set bounds are derived, and a full characterization of the set of achievable rates using single-letter expressions is provided. For this scenario, random linear network coding is proved to be optimal, even though this is not a classical multicast problem. In addition, two binary examples are investigated and demonstrate how actions taken at different nodes of the system have a significant effect on the achievable rate region, when compared with a naive time-sharing strategy.

In this paper, we introduce construction techniques for network coding in bidirectional networks with arbitrary transmission delays. These coding schemes reduce the number of transmissions and achieve the optimal rate region in the corresponding broadcast model for both multiple unicast and multicast cases with up to three users, under the equal rate constraint. The coding schemes are presented in two phases; first, coding schemes for line, star and line-star topologies with arbitrary transmission delays are provided and second, any general topology with multiple bidirectional unicast and multicast sessions is shown to be decomposable into these canonical topologies to reduce the number of transmissions. As a result, the coding schemes developed for the line, star, and line-star topologies serve as building blocks for the construction of more general coding schemes for all networks. The proposed schemes are proved to be real time in the sense that they achieve the minimum decoding delay. With a negligible size header, these coding schemes are shown to be applicable to unsynchronized networks, i.e., networks with arbitrary transmission delays. Finally, we demonstrate the applicability of these schemes by extensive simulations. The implementation of such coding schemes on a wireless network with arbitrary transmission delays can improve performance and power efficiency.

The principal mission of Group Testing (GT) is to identify a small subset of “defective” items from a large population, by grouping items into as little as possible test pools. The test outcome of a pool is positive if it contains at least one defective item, and is negative otherwise. GT algorithms are utilized in numerous applications, and in most of them the privacy of the tested subjects, namely, whether they are defective or not, is critical. In this paper, we consider a scenario where there is an eavesdropper (Eve) which is able to observe a subset of the GT outcomes (pools). We propose a new non-adaptive Secure Group Testing (SGT) algorithm based on information theoretic principles, which keeps the eavesdropper ignorant regarding the items' status. Specifically, when the fraction of tests observed by Eve is 0 ≤ δ <; 1, we prove that the number of tests required for both correct reconstruction at the legitimate user (with high probability) and negligible mutual information at Eve's side is 1/1-δ times the number of tests required with no secrecy constraint.

In this paper, we study the secrecy rate and outage probability in Multiple-Input-Single-Output (MISO) Gaussian wiretap channels at the limit of a large number of legitimate users and eavesdroppers. In particular, we analyze the asymptotic achievable secrecy rates and outage, when only statistical knowledge on the wiretap channels is available to the transmitter. The analysis provides exact expressions for the reduction in the secrecy rate as the number of eavesdroppers grows, compared to the boost in the secrecy rate as the number of legitimate users grows.

In this paper, we consider the secrecy capacity of a wiretap channel in the presence of causal state information and secure rate-limited feedback. In this scenario, the causal state information from the channel is available to both the legitimate transmitter and the legitimate receiver. In addition, the legitimate receiver can send secure feedback to the transmitter at a limited rate Rf. We derive upper and lower bounds on the secrecy capacity and show that, when the channel to the eavesdropper is degraded, the bounds are tight and the secrecy capacity is completely characterized. The capacity achieving scheme is based on Wyner, Csiszár, and Körner wiretap coding and two steps of shared-key generation: one from the state information and one via the noiseless feedback. The upper bound is more involved and requires a nontrivial recursive lemma extending previous results in the literature to include both state and feedback. We conclude the paper by showing that a few interesting known results can be seen as special cases of the above, as well as discussing the case where the source of local randomness at the encoder is limited.

Consider a transmission scheme with a single transmitter and multiple receivers over a faulty broadcast channel. For each receiver, the transmitter has a unique infinite stream of packets, and its goal is to deliver them at the highest throughput possible. While such multiple-unicast models are unsolved in general, several network coding-based schemes were suggested. In such schemes, the transmitter can either send an uncoded packet, or a coded packet which is the function of a few packets. The packets sent can be received by the designated receiver (with some probability) or heard and stored by other receivers. Two functional modes are considered; the first presumes that the storage time is unlimited, while in the second one it is limited by the given time to expire (TTE) parameter. We model the transmission process as an infinite-horizon Markov decision process (MDP). Since the large state space renders exact solutions computationally impractical, we introduce policy-restricted and induced MDPs with significantly reduced state space, and prove that with proper reward function they have equal optimal value function (hence equal optimal throughput). We then derive a reinforcement learning algorithm, which learns the optimal policy for the induced MDP. This optimal strategy of the induced MDP, once applied to the policy of the restricted one, significantly improves over uncoded schemes. Next, we enhance the algorithm by means of analysis of the structural properties of the resulting cost functional. We demonstrate that our method scales well in the number of users, and automatically adapts to the packet loss rates, unknown in advance. In addition, the performance is compared to the recent bound by Wang, which assumes much stronger coding (e.g., intrasession and buffering of coded packets), yet is shown to be comparable

In this paper, we design and analyze information spreading algorithms for dynamic networks with correlated data. In these networks, either the data to be distributed, the data already available at the nodes, or both are correlated. Moreover, nodes' availability and connectivity is dynamic - a scenario typical for wireless networks. Our contribution is twofold. First, although coding schemes for correlated data have been studied extensively, the focus has been on characterizing the rate region in static networks. In an information spreading scheme, however, nodes may communicate by continuously exchanging packets according to some underlying communication model. The main figure of merit is the stopping time - the time required until nodes can successfully decode. While information spreading schemes, such as gossip, are practical, distributed, and scalable, they have only been studied for uncorrelated data. We close this gap by providing techniques to analyze network-coded information spreading in dynamic networks with correlated data. Second, we give a clean framework for oblivious dynamic network models that in particular applies to a multitude of wireless network and communication scenarios. We specify a general setting for the data model and give tight bounds on the stopping times of network-coded protocols in this wide range of settings. En route, we analyze the capacities seen by nodes under a network-coded information spreading protocol, a previously unexplored question. We conclude with extensive simulations, clearly validating the key trends and phenomena predicted in the analysis.

This work studies the problem of distributed compression of correlated sources with an action-dependent joint distribution. This class of problems are in fact extensions of the Slepian-Wolf model, but where cost-constrained actions affect the generation of one of the sources. A network setup is investigated for the case where actions are taken at the encoder. The first source is available at a node in the network, this node can take actions which affect the generation of the other source which is available at different node in the network. Transmission occurs over a general, acyclic, directed network and both sources are required in a set of terminal nodes. The purpose of this work is to study the implications of actions on the set of achievable rates. For this network, generalized cut-set bounds are derived, and a full characterization of the set of achievable rates using single-letter expressions is provided, showing how actions affect the achievable region in a non-trivial manner. Random linear network coding is proved to be optimal in this setup, even though this is not a classical multicast problem. As a special case of this network we study a multi-user setup with two encoders and one decoder, each source is available to one encoder and transmission occurs over rate-limited link. The optimal rate region for this case is characterized, and calculated for a binary example.

In this work, we consider the problem of a Multiple-Input Single-Output (MISO) Multiple-Access Channel with a large number of users K. In practical scenarios, only a small sub-set of the users can be scheduled simultaneously. However, since solutions which collect Channel State Information (CSI) from all users and schedule the best subset to transmit do not scale with K, distributed scheduling algorithms are advantageous. We analyze a distributed scheduling algorithm, which selects a group of users to transmit without coordinating between the users and without all users sending CSI to the base station. The expected capacity under Minimum Mean Squared Error (MMSE) decoding is given, with a special emphasis on large K. It is shown that the algorithm achieves the same scaling laws as the optimal centralized scheme.

In this paper, we design novel distributed scheduling algorithms for multiuser multiple-input multiple-output systems and evaluate the resulting system capacity analytically. In particular, we consider algorithms which do not require sending channel state information to a central processing unit, nor do they require communication between the users themselves, yet, the resulting capacity closely approximates that of a centrally controlled system, which is able to schedule the strongest user in each time-slot. In other words, multiuser diversity is achieved in a distributed fashion. Our analysis is based on a novel application of the point-process approximation. This technique, besides tackling previously suggested models successfully, allows an analytical examination of new models, such as nonhomogeneous cases (nonidentically distributed users) or various quality of service considerations. This results in asymptotically exact expressions for the capacity of the system under these schemes, solving analytically problems which to date had been open. Possible applications include, but are not limited to, modern 4G networks, such as 3GPP LTE, or random access protocols.

Consider the problem of joint uplink scheduling and power allocation. Being inherent in almost any wireless system, this resource allocation problem has received extensive attention. Yet, most common techniques either adopt classical power control, in which mobile stations are received with the same Signal-to-Interference-plus-Noise Ratio, or use centralized schemes, in which base stations coordinate their allocations. In this work, we suggest a novel scheduling approach in which each base station, besides allocating the time and frequency according to given constraints, also manages its uplink power budget such that the aggregate interference, "Noise Rise", caused by its subscribers at the neighboring cells is bounded. Our suggested scheme is distributed, requiring neither coordination nor message exchange between the base stations. We rigorously define the allocation problem under noise rise constraints. Inspired by the fact that under the noise-rise constraints, interference experienced by base stations is bounded and its variance is expected to be low, we suggested an approximation in which each base station assumes fixed interference. Under this approximation we formalize the joint scheduling and power control under the noise rise constraints as an optimization problem and characterize the optimal solution. For the special case of homogeneous deployment we give the optimal solution and derive an efficient iterative algorithm to achieve it. We then discuss a relaxed problem, where the noise rise is constrained separately for each sub-channel or resource unit. While sub-optimal, this view renders the scheduling and power allocation problems separate, yielding an even simpler and more efficient solution, while the essence of the scheme is kept. Via extensive simulations, we show that the suggested approach increases overall performance dramatically, with the same level of fairness and power consumption.

Consider the problem of a multiple-antenna Multiple-Access Channel at the limit of large number of users. Clearly, in practical scenarios, only a small subset of the users can be scheduled to utilize the channel simultaneously. Thus, a problem of user selection arises. Since solutions which collect Channel State Information (CSI) from all users and decide on the best subset to transmit in each slot do not scale when the number of users is large, distributed algorithms for user selection are advantageous. In this paper, we suggest distributed user selection algorithms which select a group of users to transmit without coordinating between all users and without all users sending CSI to the base station. These threshold-based algorithms are analyzed, and their expected capacity in the limit of large number of users is investigated. It is shown that for large number of users a distributed algorithm can achieve the same scaling laws as the optimal centralized scheme.

In this paper, we present a new family of fountain codes which overcome adversarial errors. That is, we consider the possibility that some portion of the arriving packets of a rateless erasure code are corrupted in an undetectable fashion. In practice, the corrupted packets may be attributed to a portion of the communication paths which are controlled by an adversary or to a portion of the sources that are malicious. The presented codes resemble and extend rateless codes. Yet, their benefits over existing coding schemes are manifold. First, to overcome the corrupted packets, our codes use information theoretic techniques, rather than cryptographic primitives. Thus, no secret channel between the senders and the receivers is required. Second, the encoders in the suggested scheme are oblivious to the strength of the adversary, yet perform as if its strength was known in advance. Third, the sparse structure of the codes facilitates efficient decoding. Finally, the codes easily fit a decentralized scenario with several sources, when no communication between the sources is allowed. We present both exhaustive as well as efficient decoding rules. Beyond the obvious use as a rateless codes, our codes have important applications in distributed computing.

Estimation of the parameters of the electric network signal, usually present in many audio and video recordings, is known to have several important forensic applications. In this paper, we consider the problem of estimating the base frequency and signal to noise ratio (SNR). Although the electric network signal is present via its base frequency and its integer multiplies, recent estimators in the literature focus on single-tone models. In this work, we offer a multitone harmonic model for the electric network signal. We use the Cramer-Rao bound for the frequency estimation problem and show that this approach can lead to a theoreticalO(M3) factor improvement in the estimation accuracy, whereMis the number of harmonics. We then derive the computationally efficient form of the maximum-likelihood estimator, applicable in the limit of large number of measurements. The problem of estimating the SNR of the signal is also discussed. Through extensive tests on real data and data sets reported in the current literature, the performance of the new estimators is evaluated. Results indeed show a significant gain compared to the single-tone model, and are better than previously reported estimators in the literature for moderate and high SNR values.

We design and analyze gossip algorithms for networks with correlated data. In these networks, either the data to be distributed, the data already available at the nodes, or both, are correlated. Although coding schemes for correlated data have been studied extensively, the focus has been on characterizing the rate region in static memory-free networks. In a gossip-based scheme, however, nodes communicate among each other by continuously exchanging packets according to some underlying communication model. The main figure of merit in this setting is the stopping time - the time required until nodes can successfully decode. While Gossip schemes are practical, distributed and scalable, they have only been studied for uncorrelated data. We wish to close this gap by providing techniques to analyze network coded gossip in (dynamic) networks with correlated data. We give a clean framework for oblivious network models that applies to a multitude of network and communication scenarios, specify a general setting for distributed correlated data, and give tight bounds on the stopping times of network coded protocols in this wide range of scenarios.

This paper studies the reception zones of a wireless network in the SINR model with receivers that employ interference cancellation (IC). IC is a recently developed technique that allows a receiver to decode interfering signals, and cancel them from the received signal in order to decode its intended message. We first derive the important topological properties of the reception zones and their relation to high-order Voronoi diagrams and other geometric objects. We then discuss the computational issues that arise when seeking an efficient description of the zones. Our main fundamental result states that although potentially there are exponentially many possible cancellation orderings, and as a result, reception zones, in fact there are much fewer nonempty such zones. We prove a linear bound (hence tight) on the number of zones and provide a polynomial time algorithm to describe the diagram. Moreover, we introduce a novel parameter, the Compactness Parameter, which influences the tightness of our bounds. We then utilize these properties to devise a logarithmic time algorithm to answer point-location queries for networks with IC.

Consider the problem of source coding with side information in large networks with multiple receivers. In this case, standard coding techniques are either prohibitively complex to decode, or require source-network coding separation, resulting in sub-optimal transmission schemes. To alleviate this problem, we offer a joint network-source coding scheme based on matrix sparsification at the code design phase, which allows the terminals to use an efficient decoding procedure (syndrome decoding using LDPC), despite the network coding throughout the network. Via a novel relation between matrix sparsification and rate-distortion theory, we give lower and upper bounds on the best achievable sparsification performance, and analyze our scheme in the limit of weak side information at the receivers. Simulation results motivate the use of this scheme at non-limiting rates as well.

In this paper, we generalize the lossless coded side information problem from the three-node network of Ahlswede and Korner to more general network scenarios. We derive inner and outer bounds on the achievable rate region in the general network scenario and show that they are tight for some families of networks. Our approach demonstrates how solutions to canonical source coding problems can be used to derive bounds for more complex networks and reveals an interesting connection between networks with side information, successive refinement, and network coding.

We consider the problem of sequential decision making for random fields corrupted by noise. In this scenario, the decision maker observes a noisy version of the data, yet judged with respect to the clean data. In particular, we first consider the problem of scanning and sequentially filtering noisy random fields. In this case, the sequential filter is given the freedom to choose the path over which it traverses the random field (e.g., noisy image or video sequence), thus it is natural to ask what is the best achievable performance and how sensitive this performance is to the choice of the scan. We formally define the problem of scanning and filtering, derive a bound on the best achievable performance, and quantify the excess loss occurring when nonoptimal scanners are used, compared to optimal scanning and filtering.

We consider the problem of sequential decision making on random fields corrupted by Additive White Gaussian Noise (AWGN). In particular, we first consider the problem of sequentially filtering an AWGN-corrupted random field. In this scenario, the sequential filter may be given the freedom to choose the path over which it traverses the random field (e.g., noisy image), thus it is natural to ask what is the best achievable performance and how far is the performance of widely used scanning methods from the optimum. We formally define the problem of scanning and filtering, derive a bound on the best achievable performance and quantify the excess loss occurring when non-optimal scanners are used, compared to optimal scanning and filtering. We then discuss the problem of sequential scanning and prediction of noisy random fields. This setting is a natural model for applications such as restoration and coding of noisy images. In this scenario, using predictive coding methods on the noisy image results in both enhancement and compression of the input image, as one expects that the prediction error consists mainly of the noise signal. We formally define the problem of sequential prediction in a noisy array and compute the optimal performance in terms of the clean scandictability defined by Merhav and Weissman.

We investigate the problem of scanning and prediction (ldquoscandiction,rdquo for short) of multidimensional data arrays. This problem arises in several aspects of image and video processing, such as predictive coding, for example, where an image is compressed by coding the error sequence resulting from scandicting it. Thus, it is natural to ask what is the optimal method to scan and predict a given image, what is the resulting minimum prediction loss, and whether there exist specific scandiction schemes which are universal in some sense. Specifically, we investigate the following problems: first, modeling the data array as a random field, we wish to examine whether there exists a scandiction scheme which is independent of the field's distribution, yet asymptotically achieves the same performance as if this distribution were known. This question is answered in the affirmative for the set of all spatially stationary random fields and under mild conditions on the loss function. We then discuss the scenario where a nonoptimal scanning order is used, yet accompanied by an optimal predictor, and derive bounds on the excess loss compared to optimal scanning and prediction. This paper is the first part of a two-part paper on sequential decision making for multidimensional data. It deals with clean, noiseless data arrays. The second part deals with noisy data arrays, namely, with the case where the decision maker observes only a noisy version of the data, yet it is judged with respect to the original, clean data.

We investigate several problems in scanning of multidimensional data arrays, such as universal scanning and prediction ("scandiction", for short), and scandiction of noisy data arrays. These problems arise in several aspects of image and video processing, such as predictive coding, filtering and denoising. In predictive coding of images, for example, an image is compressed by coding the prediction error sequence resulting from scandicting it. Thus, it is natural to ask what is the optimal method to scan and predict a given image, what is the resulting minimum prediction loss, and if there exist specific scandiction schemes which are universal in some sense. More specifically, we investigate the following problems: first, given a random field, we examine whether there exists a scandiction scheme which is independent of the field's distribution, yet asymptotically achieves the same performance as if this distribution was known. This question is answered in the affirmative for the set of all spatially stationary random fields and under mild conditions on the loss function. We then discuss the scenario where a non-optimal scanning order is used, yet accompanied by an optimal predictor, and derive a bound on the excess loss compared to optimal scandiction. Finally, we examine the scenario where the random field is corrupted by noise, but the scanning and prediction (or filtering) scheme is judged with respect to the underlying noiseless field

New lower bounds on the error probability of block codes with maximum-likelihood decoding are proposed. The bounds are obtained by applying a new lower bound on the probability of a union of events, derived by improving on de Caen's lower bound. The new bound includes an arbitrary function to be optimized in order to achieve the tightest results. Since the optimal choice of this function is known, but leads to a trivial and useless identity, we find several useful approximations for it, each resulting in a new lower bound. For the additive white Gaussian noise (AWGN) channel and the binary-symmetric channel (BSC), the optimal choice of the optimization function is stated and several approximations are proposed. When the bounds are further specialized to linear codes, the only knowledge on the code used is its weight enumeration. The results are shown to be tighter than the latest bounds in the current literature, such as those by Seguin (1998) and by Keren and Litsyn (2001). Moreover, for the BSC, the new bounds widen the range of rates for which the union bound analysis applies, thus improving on the bound to the error exponent compared with the de Caen-based bounds.