We observe an infinite sequence of independent identically distributed random variables$X_{1},X_{2},\ldots $drawn from an unknown distributionpover$[n]$, and our goal is to estimate the entropy$H(p)=-\mathop {\mathrm {\mathbb {E}}}\nolimits [\log p(X)]$within an$\varepsilon $-additive error. To that end, at each time point we are allowed to update a finite-state machine withSstates, using a possibly randomized but time-invariant rule, where each state of the machine is assigned an entropy estimate. Our goal is to characterize the minimax memory complexity$S^{*}$of this problem, which is the minimal number of states for which the estimation task is feasible with probability at least$1-\delta $asymptotically, uniformly inp. Specifically, we show that there exist universal constants$C_{1}$and$C_{2}$such that$ S^{*} \leq C_{1}\cdot \frac {n (\log n)^{4}}{\varepsilon ^{2}\delta }$for$\varepsilon $not too small, and$S^{*} \geq C_{2} \cdot \max \left \{{{n, \frac {\log n}{\varepsilon }}}\right \}$for$\varepsilon $not too large. The upper bound is proved using approximate counting to estimate the logarithm ofp, and a finite memory bias estimation machine to estimate the expectation operation. The lower bound is proved via a reduction of entropy estimation to uniformity testing. We also apply these results to derive bounds on the memory complexity of mutual information estimation.

Learning algorithms that divide the data into batches are prevalent in many machine-learning applications, typically offering useful trade-offs between computational efficiency and performance. In this paper, we examine the benefits of batch-partitioning through the lens of a minimum-norm overparametrized linear regression model with isotropic Gaussian features. We suggest a natural small-batch version of the minimum-norm estimator and derive bounds on its quadratic risk. We then characterize the optimal batch size and show it is inversely proportional to the noise level, as well as to the overparametrization ratio. In contrast to minimum-norm, our estimator admits a stable risk behavior that is monotonically increasing in the overparametrization ratio, eliminating both the blowup at the interpolation point and the double-descent phenomenon. We further show that shrinking the batch minimum-norm estimator by a factor equal to the Weiner coefficient further stabilizes it and results in lower quadratic risk in all settings. Interestingly, we observe that the implicit regularization offered by the batch partition is partially explained by feature overlap between the batches. Our bound is derived via a novel combination of techniques, in particular normal approximation in the Wasserstein metric of noisy projections over random subspaces.

We consider the task of detecting a hidden bipartite subgraph in a given random graph. This is formulated as a hypothesis testing problem, under the null hypothesis, the graph is a realization of an Erdős-Rényi random graph over n vertices with edge density q. Under the alternative, there exists a planted$k_{ \mathsf {R}} \times k_{ \mathsf {L}}$bipartite subgraph with edge density$p>q$. We characterize the statistical and computational barriers for this problem. Specifically, we derive information-theoretic lower bounds, and design and analyze optimal algorithms matching those bounds, in both the dense regime, where$p,q = \Theta \left ({1}\right)$, and the sparse regime where$p,q = \Theta \left ({n^{-\alpha }}\right), \alpha \in \left ({0,2}\right]$. We also consider the problem of testing in polynomial-time. As is customary in similar structured high-dimensional problems, our model undergoes an “easy-hard-impossible” phase transition and computational constraints penalize the statistical performance. To provide an evidence for this statistical computational gap, we prove computational lower bounds based on the low-degree conjecture, and show that the class of low-degree polynomials algorithms fail in the conjecturally hard region.

We consider the task of detecting a hidden bipartite subgraph in a given random graph. Specifically, under the null hypothesis, the graph is a realization of an Erdős-Rényi random graph over n vertices with edge density q. Under the alternative, there exists a planted kR× kLbipartite subgraph with edge density p > q. We derive asymptotically tight upper and lower bounds for this detection problem in both the dense regime, where q, p = Θ(1), and the sparse regime where q, p = Θ(n−α), α ∈ (0, 2]. Moreover, we consider a variant of the above problem, where one can only observe a relatively small part of the graph, by using at most Q edge queries. For this problem, we derive upper and lower bounds in both the dense and sparse regimes, and observe a gap between them.

Let$G$be a large (simple, unlabeled) dense graph on$n$vertices. Suppose that we only know, or can estimate, the empirical distribution of the number of subgraphs$F$that each vertex in$G$participates in, for some fixed small graph$F$. How many other graphs would look essentially the same to us, i.e., would have a similar local structure? In this paper, we derive upper and lower bounds on the number of graphs whose empirical distribution lies close (in the Kolmogorov-Smirnov distance) to that of$G$. Our bounds are given as solutions to a maximum entropy problem on random graphs of a fixed size$k$that does not depend on$n$, under$d$global density constraints. The bounds are asymptotically close, with a gap that vanishes with$d$at a rate that depends on the concentration function of the distribution at the center of the Kolmogorov-Smirnov ball.

In this paper we consider the problem of uniformity testing with limited memory. We observe a sequence of independent identically distributed random variables drawn from a distribution $p$ over $[n]$, which is either uniform or is $\eps$-far from uniform under the total variation distance, and our goal is to determine the correct hypothesis. At each time point we are allowed to update the state of a finite-memory machine with $S$ states, where each state of the machine is assigned one of the hypotheses, and we are interested in obtaining an asymptotic probability of error at most $0<\delta<1/2$ uniformly under both hypotheses. The main contribution of this paper is deriving upper and lower bounds on the number of states $S$ needed in order to achieve a constant error probability $\delta$, as a function of $n$ and $\eps$, where our upper bound is $O(\frac{n\log n}{\eps})$ and our lower bound is $\Omega (n+\frac{1}{\eps})$. Prior works in the field have almost exclusively used collision counting for upper bounds, and the Paninski mixture for lower bounds. Somewhat surprisingly, in the limited memory with unlimited samples setup, the optimal solution does not involve counting collisions, and the Paninski prior is not hard, thus different proof techniques are needed in order to attain our bounds.

Let G be a large (simple, unlabeled) dense graph on n vertices. Suppose that we only know, or can estimate, the empirical distribution of the number of subgraphs F that each vertex in G participates in, for some fixed small graph F. How many other graphs would look essentially the same to us, i.e., would have a similar local structure? In this paper, we derive upper and lower bounds on the number graphs whose empirical distribution lies close (in the Kolmogorov-Smirnov distance) to that of G. Our bounds are given as solutions to a maximum entropy problem on random graphs of a fixed size k that does not depend on n, under d global density constraints. The bounds are asymptotically close, with a gap that vanishes with d at a rate that depends on the concentration function of the center of the Kolmogorov-Smirnov ball.

The method of types presented by Csiszár and Körner is a central tool used to develop and analyze the basic properties and constraints on sequences of data over finite alphabets. A central problem considered using these tools is that of data compression, and specifically lossy data compression. In this work we consider this very problem, however, instead of sequences of data we consider directed graphs. We show that given a more natural distortion measure, fitting the data structure of a directed graph, the method of types cannot be applied. The suggested distortion measure aims to preserves the local structure of a directed graph. We build on the recent work of Barvinok and extend the method of types to the two dimensional setting of directed graphs. We see that the extension is quite natural in many ways. Given this extension we provide a lower and upper bound on the rate-distortion problem of lossy compression given the suggested distortion measure.

Recommendation systems often use online collaborative filtering (CF) algorithms to identify items a given user likes over time, based on ratings that this user and a large number of other users have provided in the past. This problem has been studied extensively when users’ preferences do not change over time (static case); an assumption that is often violated in practical settings. In this paper, we introduce a novel model for online non-stationary recommendation systems which allows for temporal uncertainties in the users’ preferences. For this model, we propose a user-based CF algorithm, and provide a theoretical analysis of its achievable reward. Compared to related non-stationary multi-armed bandit literature, the main fundamental difficulty in our model lies in the fact that variations in the preferences of a certain user may affect the recommendations for other users severely. We also test our algorithm over real-world datasets, showing its effectiveness in real-world applications. One of the main surprising observations in our experiments is the fact our algorithm outperforms other static algorithms even when preferences do not change over time. This hints toward the general conclusion that in practice, dynamic algorithms, such as the one we propose, might be beneficial even in stationary environments.

In this paper we consider the problem of estimating a Bernoulli parameter using finite memory. Let $X_1,X_2,\ldots$ be a sequence of independent identically distributed Bernoulli random variables with expectation $\theta$, where $\theta \in [0,1]$. Consider a finite-memory deterministic machine with $S$ states, that updates its state $M_n \in \{1,2,\ldots,S\}$ at each time according to the rule $M_n = f(M_{n-1},X_n)$, where $f$ is a deterministic time-invariant function. Assume that the machine outputs an estimate at each time point according to some fixed mapping from the state space to the unit interval. The quality of the estimation procedure is measured by the asymptotic risk, which is the long-term average of the instantaneous quadratic risk. The main contribution of this paper is an upper bound on the smallest worst-case asymptotic risk any such machine can attain. This bound coincides with a lower bound derived by Leighton and Rivest, to imply that $\Theta(1/S)$ is the minimax asymptotic risk for deterministic $S$-state machines. In particular, our result disproves a longstanding $\Theta(\log S/S)$ conjecture for this quantity, also posed by Leighton and Rivest.

The essential interactive capacity of a discrete memoryless channel is defined in this paper as the maximal rate at which the transcript of any interactive protocol can be reliably simulated over the channel, using a deterministic coding scheme. In contrast to other interactive capacity definitions in the literature, this definition makes no assumptions on the order of speakers (which can be adaptive) and does not allow any use of private/public randomness; hence, the essential interactive capacity is a function of the channel model only. It is shown that the essential interactive capacity of any binary memoryless symmetric (BMS) channel is at least 0.0302 its Shannon capacity. To that end, we present a simple coding scheme, based on extended-Hamming codes combined with error detection, that achieves the lower bound in the special case of the binary symmetric channel (BSC). We then adapt the scheme to the entire family of BMS channels, and show that it achieves the same lower bound using extremes of the Bhattacharyya parameter.

We consider the problem of distributed source simulation with no communication, in which Alice and Bob observe sequences$U^{n}$and$V^{n}$respectively, drawn from a joint distribution$p_{UV}^ {\otimes n}$, and wish to locally generate sequences$X^{n}$and$Y^{n}$respectively with a joint distribution that is close (in KL divergence) to$p_{XY}^ {\otimes n}$. We provide a single-letter condition under which such a simulation is asymptotically possible with a vanishing KL divergence. Our condition is nontrivial only in the case where the Gàcs-Körner (GK) common information between$U$and$V$is nonzero, and we conjecture that only scalar Markov chains$X-U-V-Y$can be simulated otherwise. Motivated by this conjecture, we further examine the case where both$p_{UV}$and$p_{XY}$are doubly symmetric binary sources with parameters$p,q\leq 1/2$respectively. While it is trivial that in this case$p\leq q$is both necessary and sufficient, we use Fourier analytic tools to show that when$p$is close to$q$then any successful simulation is close to being scalar in the total variation sense.

We analyze a sequential decision making model in which decision makers (or, players) take their decisions based on their own private information as well as the actions of previous decision makers. Such decision making processes often lead to what is known as the \emph{information cascade} or \emph{herding} phenomenon. Specifically, a cascade develops when it seems rational for some players to abandon their own private information and imitate the actions of earlier players. The risk, however, is that if the initial decisions were wrong, then the whole cascade will be wrong. Nonetheless, information cascade are known to be fragile: there exists a sequence of \emph{revealing} probabilities $\{p_{\ell}\}_{\ell\geq1}$, such that if with probability $p_{\ell}$ player $\ell$ ignores the decisions of previous players, and rely on his private information only, then wrong cascades can be avoided. Previous related papers which study the fragility of information cascades always assume that the revealing probabilities are known to all players perfectly, which might be unrealistic in practice. Accordingly, in this paper we study a mismatch model where players believe that the revealing probabilities are $\{q_\ell\}_{\ell\in\mathbb{N}}$ when they truly are $\{p_\ell\}_{\ell\in\mathbb{N}}$, and study the effect of this mismatch on information cascades. We consider both adversarial and probabilistic sequential decision making models, and derive closed-form expressions for the optimal learning rates at which the error probability associated with a certain decision maker goes to zero. We prove several novel phase transitions in the behaviour of the asymptotic learning rate.

In this paper we consider the problem of binary hypothesis testing with finite memory systems. Let X1, X2, .. . be a sequence of independent identically distributed Bernoulli random variables, with expectation p under H0and q under H1. Consider a finite-memory deterministic machine with S states that updates its state Mn∈ {1, 2, ... , S} at each time according to the rule Mn= f(Mn-1, Xn), where f is a deterministic time-invariant function. Assume that we let the process run for a very long time (n → ∞), and then make our decision according to some mapping from the state space to the hypothesis space. The main contribution of this paper is a lower bound on the Bayes error probability Peof any such machine. In particular, our findings show that the ratio between the maximal exponential decay rate of Pewith S for a deterministic machine and for a randomized one, can become unbounded, complementing a result by Hellman.

We study a guessing game where Alice holds a discrete random variable X, and Bob tries to sequentially guess its value. Before the game begins, Bob can obtain side-information about X by asking an oracle, Carole, any binary question of his choosing. Carole's answer is however unreliable, and is incorrect with probability ϵ. We show that Bob should always ask Carole whether the index of X is odd or even with respect to a descending order of probabilities - this question simultaneously minimizes all the guessing moments for any value of ϵ. In particular, this result settles a conjecture of Burin and Shayevitz. We further consider a more general setup where Bob can ask a multiple-choice M-ary question, and then observe Carole's answer through a noisy channel. When the channel is completely symmetric, i.e., when Carole decides whether to lie regardless of Bob's question and has no preference when she lies, a similar question about the ordered index of X (modulo M) is optimal. Interestingly however, the problem of testing whether a given question is optimal appears to be generally difficult in other symmetric channels. We provide supporting evidence for this difficulty, by showing that a core property required in our proofs becomes NP-hard to test in the general M-ary case. We establish this hardness result via a reduction from the problem of testing whether a system of modular difference disequations has a solution, which we prove to be NP-hard for M ≥ 3.

Consider two sequences of n independent and identically distributed fair coin tosses, X = (X1, . . . , Xn) and Y = (Y1, . . . , Yn), which are ρ-correlated for each j, i.e. P[Xj= Yj] = 1+ρ/2 .We study the question of how large (small) the probability P[X ∈ A, Y ∈ B] can be among all sets A, B ⊂ {0, 1}nof a given cardinality. For sets |A|, |B| = Θ(2n) it is well known that the largest (smallest) probability is approximately attained by concentric (anti-concentric) Hamming balls, and this can be proved via the hypercontractive inequality (reverse hypercontractivity). Here we consider the case of |A|, |B| = 2Θ(n). By applying a recent extension of the hypercontractive inequality of Polyanskiy-Samorodnitsky (J. Functional Analysis, 2019), we show that Hamming balls of the same size approximately maximize P[X ∈ A, Y ∈ B] in the regime of p → 1. We also prove a similar tight lower bound, i.e. show that for p → 0 the pair of opposite Hamming balls approximately minimizes the probability P[X ∈ A, Y ∈ B].

A phase detection sequence is a length-n cyclic sequence such that the location of any length-k contiguous subsequence can be determined from a noisy observation of that subsequence. In this paper, we consider the problem of designing phase detection sequences that allow adaptive phase detection for different noise levels at the detector. We discuss two detection scenarios: depending on the noise level, the detector adaptively chooses the length k of the observation period, or adaptively chooses the detection resolution. We establish the optimal rate regions in both settings.

We define the interactive capacity of the binary symmetric channel (BSC) as the maximal rate for which any interactive protocol can be fully and reliably simulated over a pair of BSC's. We show that this quantity is at least 1/40 of the BSC Shannon capacity, uniformly for all channel crossover probabilities. Our result is based on a public-coin rewind-if-error coding scheme in the spirit of Kol & Raz 2013 [1].

We address the problem of simulating a binary interactive protocol over a pair of binary symmetric channels with crossover probability ε. We are interested in the achievable rates of reliable simulation, i.e., in characterizing the smallest possible blowup in communications such that a vanishing error probability in the protocol length can be attained. We analyze the family of Mth-order Markovian protocols in which the transmission at every time depends only on the last M bits of the protocol. For M =1 (first-order Markovian) we prove that all protocols can be simulated at Shannon's capacity. For M > 1 we characterize large classes of protocols that can be simulated at Shannon's capacity.

We study the problem of communicating over a discrete memoryless two-way channel using non-adaptive schemes, under a zero probability of error criterion. We derive inner and outer bounds on the zero-error capacity region, based on random coding, linear programming, and linear codes. Our work generalizes arguments of Holzman and Körner, and of Tolhuizen, obtained in the special case of the binary multiplying channel.

We study a distributed hypothesis testing problem where two parties observe i.i.d. samples from two ρ-correlated standard normal random variables X and Y. The party that observes the X-samples can communicate R bits per sample to the second party, that observes the Y-samples, in order to test between two correlation values. We investigate the best possible type-II error subject to a fixed type-I error, and derive an upper (impossibility) bound on the associated type-II error exponent. Our techniques include representing the conditional Y-samples as a trajectory of the Ornstein-Uhlenbeck process, and bounding the associated KL divergence using the subadditivity of the Wasserstein distance and the Gaussian Talagrand inequality.

We consider the problem of transmitting reliably one bit of information across a tandem of binary symmetric channels interconnected by a relay/processor station. In our setting, the relay is instantaneous in the sense that its outputs are allowed to causally depend on previous received noisy bits. For this model, we investigate the optimal exponential decay rate of the average probability of error, when relaying one bit of information using n synchronous channel uses, by devising good relaying schemes.

We revisit the problem of counting the number of directed graphs with a specified degree sequence, which was recently studied and solved by Barvinok using generating functions and convex duality techniques. We describe a systematic information-theoretic approach to this type of problems, based on studying invariant distributions and establishing suitable continuity and concentration properties. Our techniques recover and shed further light on Barvinok's solution, and may be applicable in other similar problems. As a simple example, we also apply our approach to estimating the number of undirected graphs with a given degree sequence. In particular, we show this number is approximately given by the square root of the number of associated directed graphs, whose input and output degree sequences are equal to that of the undirected graph.

We consider the problem of distributed source simulation with no communication, in which Alice and Bob observe sequences Unand Vnrespectively, drawn from a joint distribution $p_{UV}^{\otimes n}$, and wish to locally generate sequences Xnand Ynrespectively with a joint distribution that is close (in KL divergence) to $p_{XY}^{\otimes n}$. We provide a single-letter condition under which such a simulation is asymptotically possible with a vanishing KL divergence. Our condition is nontrivial only in the case where the Gàcs-Körner (GK) common information between U and V is nonzero, and we conjecture that only scalar Markov chains $X-U-V-Y$ can be simulated otherwise. Motivated by this conjecture, we further examine the case where both pUVand pXYare doubly symmetric binary sources with parameters $p, q\leq 1/2$ respectively. While it is trivial that in this case $p\leq q$ is both necessary and sufficient, we show that when p is close to q then any successful simulation is close to being scalar in the total variation sense.

We characterize the communication complexity of the following distributed estimation problem. Alice and Bob observe infinitely many iid copies of ρ-correlated unit-variance (Gaussian or ±1 binary) random variables, with unknown ρ∈[−1,1]. By interactively exchanging k bits, Bob wants to produce an estimate ρ of ρ. We show that the best possible performance (optimized over interaction protocol Π and estimator ρ) satisfies infΠ ρsupρE [|ρ−ρ|2] = k−1 (1/2 ln2 + o(1)). Curiously, the number of samples in our achievability scheme is exponential in k; by contrast, a naive scheme exchanging k samples achieves the same Ω(1/k) rate but with a suboptimal prefactor. Our protocol achieving optimal performance is one-way (non-interactive). We also prove the Ω(1/k) bound even when ρ is restricted to any small open sub-interval of [−1,1] (i.e. a local minimax lower bound). Our proof techniques rely on symmetric strong data-processing inequalities and various tensorization techniques from information-theoretic interactive common-randomness extraction. Our results also imply an Ω(n) lower bound on the information complexity of the Gap-Hamming problem, for which we show a direct information-theoretic proof.

We study a guessing game where Alice holds a discrete random variable X, and Bob is trying to sequentially guess its value. Before the game begins, Bob can obtain side-information about X by asking an oracle, Carole, any binary question of his choosing. Carole's answer is unreliable, and is incorrect with probability ε. We show that Bob should always ask Carole whether the index of X is odd or even with respect to a descending order of probabilities - this question minimizes all the guessing moments for any value of ε. This in particular settles a conjecture of Burin and Shayevitz. We further count the number of optimal questions, and discuss some extensions including asymmetric channels from Carole to Bob and to multiple-choice questions.

Two remotely located agents, Alice and Bob, observe an unlimited number of i.i.d. samples, each of a different part of a Gaussian vector. Alice can send a fixed number of bits on average to Bob, who in turn wants to estimate the correlations between the two parts of the vector. In the case where the agents observe scalar Gaussian random variables with unknown correlation, we obtain two constructive and simple unbiased estimators whose performance coincides with a known but nonconstructive random coding result of Zhang and Berger. In the vector case, which was not treated before, we obtain a nontrivial multidimensional extension that employs the coupling between the correlations to yield better performance. We also discuss application of our technique to cases where the underlying distribution is not fully known.

What is the value of one bit of side information to a guesser? We study this problem in a setup where Alice wishes to guess a uniform binary random vector, and can obtain a single bit of information from Bob, who observes this vector through a binary symmetric channel. Our goal is to charaterize the guessing efficiency, namely the maximal reduction factor in Alice's guessing-time moments obtainable by observing Bob's bit. We provide two lower bounds on the guessing efficiency by analyzing the performance of the Dictator and Majority functions, and two upper bounds via maximum entropy and Fourier-analytic/hypercontractivity arguments.

A Boolean function $g$ is said to be an optimal predictor for another Boolean function $f$ if it minimizes the probability that $f(X^n)=g(Y^n)$ among all functions, where $X^n$ is uniform over the Hamming cube and $Y^n$ is obtained from $X^n$ by independently flipping each coordinate with probability $\delta$. This paper is about self-predicting functions, which are those that coincide with their optimal predictor.

We prove an upper bound on the Shannon capacity of a graph via a linear programming variation. We show that our bound can outperform both the Lovász theta number and the Haemers minimum rank bound. As a by-product, we also obtain a new upper bound on the broadcast rate of index coding.

We investigate the maximal asymptotic rates of length-$n$ binary codes with VC-dimension at most $dn$ and minimum distance at least $\delta n$. Two upper bounds are obtained, one as a simple corollary of a result by Haussler and the other via a shortening approach combining the Sauer--Shelah lemma and the linear programming bound. Two lower bounds are given using Gilbert--Varshamov-type arguments over constant-weight and Markov-type sets.

Alice holds a random variable X, and Bob is trying to guess its value by asking questions of the form “is X = x?”. Alice answers truthfully and the game terminates once Bob guesses correctly. Before the game begins, Bob is allowed to reach out to an oracle, Carole, and ask her any yes/no question, i.e., a question of the form “is X ∈ A?”. Carole is known to lie with a given probability p. What should Bob ask Carole if he would like to minimize his expected guessing time? When Carole is always truthful (p = 0), it is not difficult to check that Bob should order the symbol probabilities in descending order and ask Carole whether the index of X with respect to this order is even or odd. We show that this strategy is almost optimal for any lying probability p, up to a small additive constant upper bounded by 1/4. We discuss a connection to the cutoff rate of the BSC with feedback.

Consider a target moving at a constant velocity on a unit-circumference circle, starting at an arbitrary location. To acquire the target, any region of the circle can be probed to obtain a noisy measurement of the target’s presence, where the noise level increases with the size of the probed region. We are interested in the expected time required to find the target to within some given resolution and error probability. For a known velocity and a given reliability, we provide an asymptotical characterization of the optimal tradeoff between time and resolution. Considering an asymptotically diminishing error probability, we derive the maximal targeting rate, and show that in contrast to the well-studied case of constant measurement noise, measurement dependent noise incurs a multiplicative gap in the maximal targeting rate between adaptive and non-adaptive search strategies. Moreover, for all rates below this maximal rate, our adaptive strategy attains the optimal rate-reliability tradeoff. We further show that accounting for a target moving at an unknown fixed velocity, the optimal non-adaptive search strategy incurs a factor of at least two in the maximal targeting rate.

We consider lossy compression of random binary matrices under distortion constraints that strive to preserve the structure of the matrix. Specifically, we assume that matrix elements are statistically independent (but not necessarily identically distributed), and that the worst case row/column average distortion is to be controlled. We discuss a natural notion of matrix types termed (R, c)-type, and provide various results concerning its probability and cardinality, as well as a “Sanov-type” result, in the spirit of the method-of-types. We then derive bounds on the associated matrix ratedistortion function via a suitable matrix version of the covering lemma.

We prove an upper bound on the Shannon capacity of a graph via a linear programming variation. We also show that our bound can be better than Lovász theta number and Haemers minimum rank bound.

We investigate the asymptotic rates of length-n binary codes with VC-dimension at most dn and minimum distance at least δn. Two upper bounds are obtained, one as a simple corollary of a result by Haussler and the other via a shortening approach combining Sauer-Shelah lemma and the linear programming bound. Two lower bounds are given using Gilbert-Varshamov type arguments over constant-weight and Markov-type sets.

We introduce the notion of information ratio Ir(H/G) between two (simple, undirected) graphs G and H, which characterizes the maximal number of source symbols per channel use that can be reliably sent over a channel with confusion graph H, where reliability is measured w.r.t. a source confusion graph G. Many different results are provided, including in particular lower and upper bounds on Ir(H/G) in terms of various graph properties, inequalities and identities for behavior under strong product and disjoint union, relations to graph cores, and notions of graph criticality. Informally speaking, Ir(H/G) can be interpreted as a measure of similarity between G and H. We make this notion precise by introducing the concept of information equivalence between graphs, a more quantitative version of homomorphic equivalence. We then describe a natural partial ordering over the space of information equivalence classes, and endow it with a suitable metric structure that is contractive under the strong product. Various examples and intuitions are discussed.

We introduce the notion of information ratio Ir$(H/G)$ between two (simple, undirected) graphs $G$ and $H$, defined as the supremum of ratios $k/n$ such that there exists a mapping between the strong products $G^k$ to $H^n$ that preserves nonadjacency. Operationally speaking, the information ratio is the maximal number of source symbols per channel use that can be reliably sent over a channel with a confusion graph $H$, where reliability is measured w.r.t. a source confusion graph $G$. Various results are provided, including, in particular, lower and upper bounds on Ir$(H/G)$ in terms of different graph properties, inequalities, and identities for behavior under strong product and disjoint union, relations to graph cores, and notions of graph criticality. Informally speaking, Ir$(H/G)$ can be interpreted as a measure of similarity between $G$ and $H$. We make this notion precise by introducing the concept of information equivalence between graphs, a more quantitative version of homomorphic equivalence. We then describe a natural partial ordering over the space of information equivalence classes, and endow it with a suitable metric structure that is contractive under the strong product. Various examples and open problems are discussed.

We study the problem of communication over an additive white Gaussian noise (AWGN) channel with an AWGN feedback channel. When the feedback channel is noiseless, the classic Schalkwijk-Kailath (S-K) scheme is known to achieve capacity in a simple sequential fashion, while attaining reliability superior to non-feedback schemes. In this paper, we show how simplicity and reliability can be attained even when the feedback is noisy, provided that the feedback channel is sufficiently better than the feedforward channel. Specifically, we introduce a low-complexity low-delay interactive scheme that operates close to capacity for a fixed bit error probability (e.g., 10-6). We then build on this scheme to provide two asymptotic constructions, one based on high dimensional lattices, and the other based on concatenated coding, that admit an error exponent significantly exceeding the best possible non-feedback exponent. Our approach is based on the interpretation of feedback transmission as a side-information problem, and employs an interactive modulo-lattice solution.

Motivated by the problem of zero-error broadcasting, we introduce a new notion of graph capacity, termed ρ-capacity, that generalizes the Shannon capacity of a graph. We derive upper and lower bounds on the p-capacity of arbitrary graphs, and provide a Lovász-type upper bound for regular graphs. We study the behavior of the ρ-capacity under two graph operations: the strong product and the disjoint union. Finally, we investigate the connection between the structure of a graph and its ρ-capacity.

A phase detection sequence is a length-n cyclic sequence, such that the location of any length-k contiguous subsequence can be determined from a noisy observation of that subsequence. In this paper, we derive bounds on the minimal possible k in the limit of n → ∞, and describe some sequence constructions. We further consider multiple phase detection sequences, where the location of any length-k contiguous subsequence of each sequence can be determined simultaneously from a noisy mixture of those subsequences. We study the optimal trade-offs between the lengths of the sequences, and describe some sequence constructions. We compare these phase detection problems to their natural channel coding counterparts, and show a strict separation between the fundamental limits in the multiple sequence case. Both adversarial and probabilistic noise models are addressed.

Suppose Ynis obtained by observing a uniform Bernoulli random vector Xnthrough a binary symmetric channel. Courtade and Kumar asked how large the mutual information between Yn and a Boolean function b(Xn) could be, and conjectured that the maximum is attained by a dictator function. An equivalent formulation of this conjecture is that dictator minimizes the prediction cost in a sequential prediction of Ynunder logarithmic loss, given b(Xn). In this paper, we study the question of minimizing the sequential prediction cost under a different (proper) loss function-the quadratic loss. In the noiseless case, we show that majority asymptotically minimizes this prediction cost among all Boolean functions. We further show that for weak noise, majority is better than a dictator, and that for a strong noise dictator outperforms majority. We conjecture that for quadratic loss, there is no single sequence of Boolean functions that is simultaneously (asymptotically) optimal at all noise levels.

Motivated by the problem of zero-error broadcasting, we introduce a new notion of graph capacity, termed ρ-capacity, that generalizes the Shannon capacity of a graph. We derive upper and lower bounds on the ρ-capacity of arbitrary graphs, and provide a tighter upper bound for regular graphs. The ρ-capacity is employed to characterize the zero-error capacity region of the degraded broadcast channel.

Suppose X is a uniformly distributed n-dimensional binary vector and Y is obtained by passing X through a binary symmetric channel with crossover probability α. A recent conjecture by Courtade and Kumar postulates that I(f(X); Y ) ≤ 1 - h(α) for any Boolean function f. So far, the best known upper bound was essentially I(f(X); Y ) ≤ (1 - 2α)2. In this paper, we derive a new upper bound that holds for all balanced functions, and improves upon the best known previous bound for α > 1 over 3.

We consider the problem of designing a length-n binary sequence, such that the location of any length-k contiguous subsequence can be determined from a noisy observation of that subsequence. We derive bounds on the minimal possible k in the limit of n → ∞, and describe some sequence constructions. Both adversarial and probabilistic noise models are addressed. Two applications of the problem include fast positioning and card tricks.

Suppose Ynis obtained by observing a uniform Bernoulli random vector Xnthrough a binary symmetric channel. Courtade and Kumar asked how large the mutual information between Y n and a Boolean function b(Xn) could be, and conjectured that the maximum is attained by the dictator function. An equivalent formulation of this conjecture is that dictator minimizes the prediction cost in sequentially predicting Ynunder logarithmic loss, given b(Xn). In this paper, we study the question of minimizing the sequential prediction cost under a different (proper) loss function - the quadratic loss. In the noiseless case, we show that majority asymptotically minimizes this prediction cost among all Boolean functions. We further show that for weak noise, majority is better than dictator, and that for strong noise dictator outperforms majority. We conjecture that for quadratic loss, there is no single Boolean function that is simultaneously optimal at all noise levels.

Let $\mathcal{F}_1$ and $\mathcal{F}_2$ be two families of subsets of an $n$-element set. We say that $\mathcal{F}_1$ and $\mathcal{F}_2$ are multiset-union-free if for any $A,B\in \mathcal{F}_1$ and $C,D\in \mathcal{F}_2$ the multisets $A\uplus C$ and $B\uplus D$ are different, unless both $A = B$ and $C= D$. We derive a new upper bound on the maximal sizes of multiset-union-free pairs, improving a result of Urbanke and Li.

The mutual information between two jointly distributed random variables X and Y is a functional of the joint distribution PXY, which is sometimes difficult to handle or estimate. A coarser description of the statistical behavior of (X, Y) is given by the marginal distributions PX, PY and the adjacency relation induced by the joint distribution, where x and y are adjacent if P(x, y) > 0. We derive a lower bound on the mutual information in terms of these entities. The bound is obtained by viewing the channel from X to Y as a probability distribution on a set of possible actions, where an action determines the output for any possible input, and is independently drawn. We also provide an alternative proof based on convex optimization that yields a generally tighter bound. Finally, we derive an upper bound on the mutual information in terms of adjacency events between the action and the pair (X, Y), where in this case, an action a and a pair (x, y) are adjacent if y = a(x). As an example, we apply our bounds to the binary deletion channel and show that for the special case of an independent identically distributed input distribution and a range of deletion probabilities, our lower and upper bounds both outperform the best known bounds for the mutual information.

Posterior matching (PM) is a sequential horizon-free feedback communication scheme introduced by the authors, who also provided a rather involved optimality proof, showing that it achieves capacity for a large class of memoryless channels. Naghshvar et al. considered a non-sequential variation of PM with a fixed number of messages and a random decision-time, and gave a simpler proof establishing its optimality via a novel extrinsic Jensen-Shannon divergence argument. Another simpler optimality proof was given by Li and El Gamal, who considered a fixed-rate fixed block-length variation of PM with an additional randomization. Both these works also provided error exponent bounds. However, their simpler achievability proofs apply only to discrete memoryless channels, and are restricted to a non-sequential setup with a fixed number of messages. In this paper, we provide a short and transparent proof for the optimality of the fully sequential randomized horizon-free PM scheme over general memoryless channels. Borrowing the key randomization idea of Li and El Gamal, our proof is based on analyzing the random walk behavior of the shrinking posterior intervals induced by a reversed iterated function system decoder.

Consider a pair of terminals connected by two independent (feedforward and feedback) Additive White Gaussian Noise (AWGN) channels, and limited by individual power constraints. The first terminal would like to reliably send information to the second terminal at a given rate. While the reliability in the cases of no feedback and of noiseless feedback is well studied, not much is known about the case of noisy feedback. In this work, we present an interactive scheme that significantly improves the reliability relative to the no-feedback setting, whenever the feedback Signal to Noise Ratio (SNR) is sufficiently larger than the feedforward SNR. The scheme combines Schalkwijk-Kailath (S-K) coding and modulo-lattice analog transmission.

We consider a search problem in which multiple targets are uniformly placed on the unit interval. An agent, who might not know the number of targets in advance, is interested in acquiring all targets to within some resolution δ as quickly as possible. To that end, at each time unit, the agent can probe any region of the unit interval for the presence of targets but the associated measurement noise increases with the size of the probed region. We characterize the maximal targeting rate, the optimal tradeoff between resolution and expected search time, with adaptive and non-adaptive search strategies, highlighting the advantage of adaptive strategies. We show that even when the number of targets is known, in contrast to the case of constant measurement noise, there is a multiplicative gap between the performance of adaptive and non-adaptive search. This gap, however, diminishes as the number of targets grow.

The binary adder is a two-user multiple access channel whose inputs are binary and whose output is the real sum of the inputs. While the Shannon capacity region of this channel is well known, little is known regarding its zero-error capacity region, and a large gap remains between the best inner and outer bounds. In this paper, we provide an improved outer bound for this problem. To that end, we introduce a soft variation of the Saur-Perles-Shelah Lemma, that is then used in conjunction with an outer bound for the Shannon capacity region with an additional common message.

We consider the problem of communication over a two-user Additive White Gaussian Noise Broadcast Channel (AWGN-BC) with an AWGN Multiple Access (MAC) active feedback. We describe a constructive reduction from this setup to the well-studied setup of linear-feedback coding over the AWGN-BC with noiseless feedback (and different parameters). This reduction facilitates the design of linear-feedback coding schemes in the (passive) noiseless feedback regime, which can then be easily and constructively transformed into coding schemes in the MAC feedback regime that attain the exact same rates. Our construction introduces an element of interaction into the coding protocol, and is based on modulo-lattice operations. As an example, we apply our method to the Ozarow-Leung scheme, and demonstrate how MAC feedback can be used to enlarge the capacity region of the AWGN-BC.

A lossy source code C with rate R for a discrete memoryless source S is called subset-universal if for every 0nR'of its codewords achieves average distortion close to the source's distortion-rate function D(R'). In this paper we prove the asymptotic existence of such codes. Moreover, we show the asymptotic existence of a code that is subset-universal with respect to all sources with the same alphabet.

Mrs. Gerber's Lemma lower bounds the entropy at the output of a binary symmetric channel in terms of the entropy of the input process. In this paper, we lower bound the output entropy via a different measure of input uncertainty, pertaining to the minimum mean squared error prediction cost of the input process. We show that in many cases our bound is tighter than the one obtained from Mrs. Gerber's Lemma. As an application, we evaluate the bound for binary hidden Markov processes, and obtain new estimates for the entropy rate.

A channel can generally be defined by a probability distribution on a set of possible actions. These actions determine the output for any possible input, and are independently drawn. The intrinsic uncertainty of a channel is defined as the conditional entropy of the action given the input and output sequences. For many channels, such as the deletion channel, the insertion channel, and various permutation channels, e.g., the trapdoor channel, quantifying the intrinsic uncertainty is the main challenge in determining the capacity. In this paper, we derive an alternative expression for the intrinsic uncertainty via the Laplace variational principle, and utilize it to obtain a general lower bound for the capacity. As an example, we apply our bound to the binary deletion channel and show that for the special case of an i.i.d. input distribution and a range of deletion probabilities, it outperforms the best known lower bound for the mutual information.

Consider a target moving with a constant velocity on a unit-circumference circle, starting from an arbitrary location. To acquire the target, any region of the circle can be probed for its presence, but the associated measurement noise increases with the size of the probed region. We are interested in the expected time required to find the target to within some given resolution and error probability. For a known velocity, we characterize the optimal tradeoff between time and resolution (i.e., maximal rate), and show that in contrast to the case of constant measurement noise, measurement dependent noise incurs a multiplicative gap between adaptive search and non-adaptive search. Moreover, our adaptive scheme attains the optimal rate-reliability tradeoff. We further show that for optimal non-adaptive search, accounting for an unknown velocity incurs a factor of two in rate.

Two remote senders observe X and Y, respectively, and can noiselessly send information via a common relay node to a receiver that observes Z. The receiver wants to compute a function f (X, Y, Z) of these possibly related observations, without error. We study the average number of bits that need to be conveyed to that end by each sender to the relay and by the relay to the receiver, in the limit of multiple instances. We relate these quantities to the entropy region of a probabilistic graph with respect to a Cartesian representation of its vertex set, which we define as a natural extension of graph entropy. General properties and bounds for the graph entropy region are derived, and mapped back to special cases of the distributed computing setup.

The penalty incurred by imposing a finite delay constraint in lossless source coding of a memoryless source is investigated. It is well known that for the so-called block-to-variable and variable-to-variable codes, the redundancy decays at best polynomially with the delay, where in this case the delay is identified with the source block length or maximal source phrase length, respectively. In stark contrast, it is shown that for sequential codes (e.g., a delay-limited arithmetic code) the redundancy can be made to decay exponentially with the delay constraint. The corresponding redundancy-delay exponent is shown to be at least as good as the Rényi entropy of order 2 of the source, but (for almost all sources) not better than a quantity depending on the minimal source symbol probability and the alphabet size.

A coding scheme for the discrete memoryless broadcast channel with {noiseless, noisy, generalized} feedback is proposed, and the associated achievable region derived. The scheme is based on a block-Markov strategy combining the Marton scheme and a lossy version of the Gray–Wyner scheme with side information. In each block, the transmitter sends fresh data and update information that allows the receivers to improve the channel outputs observed in the previous block. For a generalization of Dueck's broadcast channel, our scheme achieves the noiseless-feedback capacity, which is strictly larger than the no-feedback capacity. For a generalization of Blackwell's channel and when the feedback is noiseless, our new scheme achieves rate points that are outside the no-feedback capacity region. It follows by a simple continuity argument that for both these channels and when the feedback noise is sufficiently low, our scheme improves on the no-feedback capacity even when the feedback is noisy.

A sender knows X and a receiver knows a correlated Z and would like to learn X, without error. The sender can communicate with the receiver only via a relay, that knows a correlated Y. We study the expected number of bits per instance that need to be sent to and from the relay to that end, in the limit of multiple instances.

We provide a variational characterization for the various Rényi information measures via their Shannon counterparts, and demonstrate how properties of the former can be recovered from first principle via the associated properties of the latter. Motivated by this characterization, we give a new operational interpretation for the Rényi divergence in a two-sensor composite hypothesis testing framework.

In this paper, we introduce a fundamental principle for optimal communication over general memoryless channels in the presence of noiseless feedback, termed posterior matching. Using this principle, we devise a (simple, sequential) generic feedback transmission scheme suitable for a large class of memoryless channels and input distributions, achieving any rate below the corresponding mutual information. This provides a unified framework for optimal feedback communication in which the Horstein scheme (BSC) and the Schalkwijk-Kailath scheme (AWGN channel) are special cases. Thus, as a corollary, we prove that the Horstein scheme indeed attains the BSC capacity, settling a longstanding conjecture. We further provide closed form expressions for the error probability of the scheme over a range of rates, and derive the achievable rates in a mismatch setting where the scheme is designed according to the wrong channel model. Several illustrative examples of the posterior matching scheme for specific channels are given, and the corresponding error probability expressions are evaluated. The proof techniques employed utilize novel relations between information rates and contraction properties of iterated function systems.

It is known that modeling an information source via a symbolic dynamical system evolving over the unit interval, leads to a natural lossless compression scheme attaining the entropy rate of the source, under general conditions. We extend this notion to the lossy compression regime assuming a feedforward link is available, by modeling a source via a two-dimensional symbolic dynamical system where one component corresponds to the compressed signal, and the other essentially corresponds to the feedforward signal. For memoryless sources and an arbitrary bounded distortion measure, we show this approach leads to a family of simple deterministic compression schemes that attain the rate-distortion function of the source. The construction is dual to a recent optimal scheme for channel coding with feedback.

A coding scheme for the discrete memoryless broadcast channel with (possible noisy) feedback is proposed, and the corresponding achievable region derived. The scheme is based on a block-Markov strategy where in each block the transmitter sends fresh data and update information that allows the receivers to improve the channel outputs observed in the previous block. The region is analyzed for two specific broadcast channels: 1) A generalization of Dueck's channel, where it is shown that for noiseless output-feedback the region coincides with the capacity region; 2) A noisy version of Blackwell's channel, where it is shown that for noiseless - and in some cases noisy - output-feedback, the region improves upon the no-feedback capacity region.

When transmitting a Gaussian source over an AWGN channel with an input power constraint and a quadratic distortion measure, it is well known that optimal performance can be obtained using an analog joint source-channel scalar scheme which merely scales the input and output signals. In the case of bandwidth expansion, such a joint source-channel analog scheme attaining optimal performance is no longer simple. However, when feedback is available a simple and sequential analog linear procedure based on the Schalkwijk-Kailath scheme for communication, is optimal. Recently, we have introduced a fundamental feedback communication scheme, termedposteriormatching, which generalizes the Schalkwijk-Kailath scheme to arbitrary memoryless channels and input distributions. In this paper, we show how the posterior matching scheme can be adapted to the joint source-channel coding setting with bandwidth expansion and a general distortion measure, when feedback is available.

This work provides some preliminary results on the problem of error correction in the presence of noiseless feedback, where list-of-L decoding is allowed. The methods introduced by Berlekamp for the list-of-1 setting are generalized, and some basic finite-block constraints are described. These constraints are then combined to derive an upper bound on the asymptotically achievable rates for a large family of strategies, as a function of the maximal error fraction p and the list size L.

We address the problem of universal communications over an unknown channel with an instantaneous noiseless feedback, and show how rates corresponding to the empirical behavior of the channel can be attained, although no rate can be guaranteed in advance. First, we consider a discrete modulo-additive channel with alphabet${\cal X}$, where the noise sequence$Z^n$isarbitrary and unknownand may causally depend on the transmitted and received sequences and on the encoder's message, possibly in an adversarial fashion. Although the classical capacity of this channel is zero, we show that rates approaching theempirical capacity$\log{\vert {\cal X}\vert}-H_{\rm emp}(Z^n)$can be universally attained, where$H_{\rm emp}(Z^n)$is the empirical entropy of$Z^n$. For the more general setting, where the channel can map its input to an output in an arbitrary unknown fashion subject only to causality, we model the empirical channel actions as the modulo-addition of a realized noise sequence, and show that the same result applies if common randomness is available. The results are proved constructively, by providing a simple sequential transmission scheme approaching the empirical capacity.

In a previous paper we derived an upper bound on the redundancy of an arithmetic-type encoder for a memoryless source, designed to meet a finite end- to-end strict delay constraint. It was shown that the redundancy decays exponentially with the delay constraint and that the redundancy-delay exponent is lower bounded by log(1/alpha) where alpha is the probability of the most likely source symbol. In this work, we prove a corresponding upper bound for the redundancy-delay exponent, C - log 1/beta where beta is the probability of the least likely source symbol. This bound is valid for almost all memoryless sources and for all arithmetic-type (possibly time-varying, memory dependent) lossless delay-constrained encoders. We also shed some light on the difference between our exponential bounds and the polynomial O(d-5'3) upper bound on the redundancy with an average delay constraint d, derived in an elegant paper by Bugeaud, Drmota and Szpankowski for another class of variable-to-variable encoders, and show that the difference is due to the precision needed to memorize the encoder's state.

Recently, we have introduced a sequential communication scheme for general memoryless channels with feedback based on the idea of posterior matching, providing a unified framework in which the known Horstein and Schalkwijk-Kailath schemes are special cases. In this paper, we show that the posterior matching scheme achieves the mutual information for a large family of channels and input distributions, and provide closed-form expressions for the attainable error probability over a range of rates. Moreover, we derive the achievable rates in a mismatched setting, where the scheme is designed according to the wrong channel model. In particular, our results hold for discrete memoryless channels, thereby confirming a longstanding conjecture that the Horstein scheme achieves capacity. The proof techniques employed utilize novel relations between information rates and convergence properties of iterated function systems.

We address the problem of a finite delay constraint in an arithmetic coding system. Due to the nature of the arithmetic coding process, source sequences causing arbitrarily large encoding or decoding delays exist. Therefore, to meet a finite delay constraint, it is necessary to intervene with the normal flow of the coding process, e.g., to insert fictitious symbols. This results in an inevitable coding rate redundancy. In this paper, we derive an upper bound on the achievable redundancy for a memoryless source. We show that this redundancy decays exponentially as a function of the delay constraint, and thus it is clearly superior to block to variable methods in that aspect. The redundancy-delay exponent is shown to be lower bounded by log(1/alpha), where alpha is the probability of the most likely source symbol. Our results are easily applied to practical problems such as the compression of English text

In this paper we describe a general algorithmic scheme for communication over any memoryless channel in the presence of noiseless feedback. The scheme is based on the idea of posterior matching, in which the information still missing at the receiver is extracted from the a-posteriori density function, and matched to any desirable input distribution. We analyze the error probability attained by this scheme for additive noise channels, and show that the well-known Schalkwijk-Kailath scheme for the AWGN channel with average power constraint and the Horstein scheme for the BSC, can be derived as special cases.

We address the problem of delay in an arithmetic coding system. Due to the nature of the arithmetic coding process, source sequences causing arbitrarily large encoding or decoding delays exist. This phenomena raises the question of just how large is the expected input to output delay in these systems, i.e., once a source sequence has been encoded, what is the expected number of source letters that should be further encoded to allow full decoding of that sequence. In this paper, we derive several new upper bounds on the expected delay for a memoryless source, which improve upon a known bound due to Gallager. The bounds provided are uniform in the sense of being independent of the sequence's history. In addition, we give a sufficient condition for a source to admit a bounded expected delay, which holds for a stationary ergodic Markov source of any order

We address the problem of decoding in unknown frequency selective fading channels, using an OFDM signaling scheme and adopting a block fading model. For a given codebook, we seek a decoder independent of the channel fading, whose worst case performance, relative to a maximum likelihood (ML) decoder that knows the channel, is optimal. Specifically, the decoder is selected from a family of quadratic decoders, and the optimal decoder is referred to as a quadratic minimax (QMM) decoder for that family. The intuitively appealing QMM decoding procedure is derived for the case where the fading is unknown, and also for the case where the fading coefficients satisfy some general constraints. The QMM decoder is also shown to outperform the generalized likelihood ratio test (GLRT), while maintaining a comparable complexity. Simulations verify the superiority of the proposed decoder over the GLRT and over the practically used training sequence approach.

Communications over a binary channel with an additive (modulo 2) individual noise sequence and a full causal feedback link is explored. A randomized sequential transmission scheme that adapts its rate to the individual noise realization is presented. The decoding rate is analyzed for a special case, and shown to asymptotically approach 1 - hb(pemp) with a vanishing probability of error w.r.t. the scheme's randomization, where hb(pemp) is the empirical entropy of the noise sequence. Therefore, while the classical capacity of this channel is zero, information may be reliably transmitted over the channel by not committing to a rate in advance, but rather decoding at a rate dictated by the realized noise sequence

We address the problem of universal decoding in unknown frequency-selective fading channels, using an orthogonal frequency-division multiplexing (OFDM) signaling scheme. A block-fading model is adopted, where the bands' fading coefficients are unknown yet assumed constant throughout the block. Given a codebook, we seek a decoder independent of the channel parameters whose worst case performance relative to a maximum-likelihood (ML) decoder that knows the channel is optimal. Specifically, the decoder is selected from a family of quadratic decoders, and the optimal decoder is referred to as a quadratic minimax (QMM) decoder for that family. As the QMM decoder is generally difficult to find, a suboptimal QMM decoder is derived instead. Despite its suboptimality, the proposed decoder is shown to outperform the generalized likelihood ratio test (GLRT), which is commonly used when the channel is unknown, while maintaining a comparable complexity. The QMM decoder is also derived for the practical case where the fading coefficients are not entirely independent but rather satisfy some general constraints. Simulations verify the superiority of the proposed QMM decoder over the GLRT and over the practically used training sequence approach.