Assaf Ben-Yishai
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Assaf Ben-Yishai has a total of 4 co-authors. Here are the top co-authors by number of shared publications:
- Ofer Shayevitz
Tel Aviv University, Tel Aviv, Israel
10 shared publications - Young-Han Kim
Department of Electrical and Computer Engineering, University of California at San Diego, La Jolla, CA, USA
6 shared publications - Or Ordentlich
School of Computer Science and Engineering, Hebrew University of Jerusalem, Jerusalem, Israel
3 shared publications - Rotem Oshman
Department of Computer Science, Tel Aviv University, Tel Aviv 6997801, Israel
2 shared publications
Latest Publications
- 18 August 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (12) , 7639-7658
A Lower Bound on the Essential Interactive Capacity of Binary Memoryless Symmetric Channels
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.
- 18 August 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (12) , 7639-7658
A Lower Bound on the Essential Interactive Capacity of Binary Memoryless Symmetric Channels
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.
- Open Access
Constructing Multiclass Classifiers using Binary Classifiers Under Log-Loss
The construction of multiclass classifiers from binary elements is studied in this paper, and performance is quantified by the regret, defined with respect to the Bayes optimal log-loss. We discuss two known methods. The first is one vs. all (OVA), for which we prove that the multiclass regret is upper bounded by the sum of binary regrets of the constituent classifiers. The second is hierarchical classification, based on a binary tree. For this method we prove that the multiclass regret is exactly a weighted sum of constituent binary regrets where the weighing is determined by the tree structure. We also introduce a leverage-hierarchical classification method, which potentially yields smaller log-loss and regret. The advantages of these classification methods are demonstrated by simulation on both synthetic and real-life datasets.
Open AccessConstructing Multiclass Classifiers using Binary Classifiers Under Log-Loss
The construction of multiclass classifiers from binary elements is studied in this paper, and performance is quantified by the regret, defined with respect to the Bayes optimal log-loss. We discuss two known methods. The first is one vs. all (OVA), for which we prove that the multiclass regret is upper bounded by the sum of binary regrets of the constituent classifiers. The second is hierarchical classification, based on a binary tree. For this method we prove that the multiclass regret is exactly a weighted sum of constituent binary regrets where the weighing is determined by the tree structure. We also introduce a leverage-hierarchical classification method, which potentially yields smaller log-loss and regret. The advantages of these classification methods are demonstrated by simulation on both synthetic and real-life datasets.
- Open Access
A Lower Bound on the Essential Interactive Capacity of Binary Memoryless Symmetric Channels
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.Open AccessA Lower Bound on the Essential Interactive Capacity of Binary Memoryless Symmetric Channels
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. - Open Access
On the Interactive Capacity of Finite-State Protocols
The interactive capacity of a noisy channel is the highest possible rate at which arbitrary interactive protocols can be simulated reliably over the channel. Determining the interactive capacity is notoriously difficult, and the best known lower bounds are far below the associated Shannon capacity, which serves as a trivial (and also generally the best known) upper bound. This paper considers the more restricted setup of simulating finite-state protocols. It is shown that all two-state protocols, as well as rich families of arbitrary finite-state protocols, can be simulated at the Shannon capacity, establishing the interactive capacity for those families of protocols.
Open AccessOn the Interactive Capacity of Finite-State Protocols
The interactive capacity of a noisy channel is the highest possible rate at which arbitrary interactive protocols can be simulated reliably over the channel. Determining the interactive capacity is notoriously difficult, and the best known lower bounds are far below the associated Shannon capacity, which serves as a trivial (and also generally the best known) upper bound. This paper considers the more restricted setup of simulating finite-state protocols. It is shown that all two-state protocols, as well as rich families of arbitrary finite-state protocols, can be simulated at the Shannon capacity, establishing the interactive capacity for those families of protocols.
- Open Access
On the Interactive Capacity of Finite-State Protocols
The interactive capacity of a noisy channel is the highest possible rate at which arbitrary interactive protocols can be simulated reliably over the channel. Determining the interactive capacity is notoriously difficult, and the best known lower bounds are far below the associated Shannon capacity, which serves as a trivial (and also generally the best known) upper bound. This paper considers the more restricted setup of simulating finite-state protocols. It is shown that all two-state protocols, as well as rich families of arbitrary finite-state protocols, can be simulated at the Shannon capacity, establishing the interactive capacity for those families of protocols.
Open AccessOn the Interactive Capacity of Finite-State Protocols
The interactive capacity of a noisy channel is the highest possible rate at which arbitrary interactive protocols can be simulated reliably over the channel. Determining the interactive capacity is notoriously difficult, and the best known lower bounds are far below the associated Shannon capacity, which serves as a trivial (and also generally the best known) upper bound. This paper considers the more restricted setup of simulating finite-state protocols. It is shown that all two-state protocols, as well as rich families of arbitrary finite-state protocols, can be simulated at the Shannon capacity, establishing the interactive capacity for those families of protocols.
- Open Access
Shannon Capacity is Achievable for Binary Interactive First-Order Markovian Protocols
We address the problem of simulating an arbitrary binary interactive first-order Markovian protocol over a pair of binary symmetric channels with crossover probability $\varepsilon$. 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. Whereas for general interactive protocols the output of each party may depend on all previous outputs of its counterpart, in a (first-order) Markovian protocol this dependence is limited to the last observed output only. Previous works in the field discuss broader families of protocols but assess the achievable rates only at the limit where $\varepsilon\to0$. In this paper, we prove that the one-way Shannon capacity, $1-h(\varepsilon)$, can be achieved for any binary first-order Markovian protocol. This surprising result, is to the best of our knowledge, the first example in which non-trivial interactive protocol can be simulated in the Shannon capacity. We give two capacity achieving coding schemes, which both divide the protocol into independent blocks, and implement vertical block coding. The first scheme is based on a random separation into blocks with variable lengths. The second scheme is based on a deterministic separation into blocks, and efficiently predicting their last transmission. The prediction can be regarded as a binary pointer jumping game, for which we show that the final step can be calculated with $O(\log m)$ bits, where $m$ is the number of rounds in the game. We conclude the work by discussing possible extensions of the result to higher order models.Open AccessShannon Capacity is Achievable for Binary Interactive First-Order Markovian Protocols
We address the problem of simulating an arbitrary binary interactive first-order Markovian protocol over a pair of binary symmetric channels with crossover probability $\varepsilon$. 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. Whereas for general interactive protocols the output of each party may depend on all previous outputs of its counterpart, in a (first-order) Markovian protocol this dependence is limited to the last observed output only. Previous works in the field discuss broader families of protocols but assess the achievable rates only at the limit where $\varepsilon\to0$. In this paper, we prove that the one-way Shannon capacity, $1-h(\varepsilon)$, can be achieved for any binary first-order Markovian protocol. This surprising result, is to the best of our knowledge, the first example in which non-trivial interactive protocol can be simulated in the Shannon capacity. We give two capacity achieving coding schemes, which both divide the protocol into independent blocks, and implement vertical block coding. The first scheme is based on a random separation into blocks with variable lengths. The second scheme is based on a deterministic separation into blocks, and efficiently predicting their last transmission. The prediction can be regarded as a binary pointer jumping game, for which we show that the final step can be calculated with $O(\log m)$ bits, where $m$ is the number of rounds in the game. We conclude the work by discussing possible extensions of the result to higher order models. - Open Access
Interactive Coding for Markovian Protocols
We address the problem of simulating an arbitrary Markovian interactive protocol over binary symmetric channels with crossover probability $\varepsilon$. 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. Whereas for general interactive protocols the output of each party may depend on all previous outputs of its counterpart, in a (first order) Markovian protocol this dependence is limited to the last observed output only. In the special case where there is no dependence on previous outputs (no interaction), the maximal achievable rate is given by the (one-way) Shannon capacity $1-h(\varepsilon)$. For Markovian protocols, we first show that a rate of $\frac{2}{3}(1-h(\varepsilon))$ can be trivially achieved. We then describe a more involved coding scheme and provide a closed-form lower bound for its rate at any noise level $\varepsilon$. Specifically, we show that this scheme outperforms the trivial one for any $\varepsilon<0.044$, and achieves a rate higher than $\frac{1-h(\varepsilon)}{1+h(\varepsilon)+h\left(<\varepsilon(2-\varepsilon)>\right)}=1-\Theta(h(\varepsilon))$ as $\varepsilon\to 0$, which is order-wise the best possible. This should be juxtaposed with a result of Kol and Raz that shows the capacity for interactive protocols with alternating rounds is lower bounded by $1-O(\sqrt{h(\varepsilon)})$.Open AccessInteractive Coding for Markovian Protocols
We address the problem of simulating an arbitrary Markovian interactive protocol over binary symmetric channels with crossover probability $\varepsilon$. 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. Whereas for general interactive protocols the output of each party may depend on all previous outputs of its counterpart, in a (first order) Markovian protocol this dependence is limited to the last observed output only. In the special case where there is no dependence on previous outputs (no interaction), the maximal achievable rate is given by the (one-way) Shannon capacity $1-h(\varepsilon)$. For Markovian protocols, we first show that a rate of $\frac{2}{3}(1-h(\varepsilon))$ can be trivially achieved. We then describe a more involved coding scheme and provide a closed-form lower bound for its rate at any noise level $\varepsilon$. Specifically, we show that this scheme outperforms the trivial one for any $\varepsilon<0.044$, and achieves a rate higher than $\frac{1-h(\varepsilon)}{1+h(\varepsilon)+h\left(<\varepsilon(2-\varepsilon)>\right)}=1-\Theta(h(\varepsilon))$ as $\varepsilon\to 0$, which is order-wise the best possible. This should be juxtaposed with a result of Kol and Raz that shows the capacity for interactive protocols with alternating rounds is lower bounded by $1-O(\sqrt{h(\varepsilon)})$. - Open Access
Interactive Schemes for the AWGN Channel with Noisy Feedback
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 work, 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.
Open AccessInteractive Schemes for the AWGN Channel with Noisy Feedback
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 work, 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.
- Open Access
The AWGN BC with MAC Feedback: A Reduction to Noiseless Feedback via Interaction
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 increase the capacity region of the AWGN-BC.
Open AccessThe AWGN BC with MAC Feedback: A Reduction to Noiseless Feedback via Interaction
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 increase the capacity region of the AWGN-BC.
- Open Access
The Gaussian Channel with Noisy Feedback: Improving Reliability via Interaction
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.
Open AccessThe Gaussian Channel with Noisy Feedback: Improving Reliability via Interaction
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.