Bruce Hajek
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Bruce Hajek has a total of 13 co-authors. Here are the top co-authors by number of shared publications:
- Amos Lapidoth
ETH Zurich, Zurich, Switzerland
2 shared publications - Juan Alvarez
Department of Mathematics and Statistics, University of Saskatchewan, 142 McLean Hall, 106 Wiggins Road, Saskatoon, Saskatchewan, S7N 5E6, Canada
2 shared publications - Ligong Wang
Signal and Information Processing Laboratory ETH Zurich Switzerland
2 shared publications - Vignesh Sethuraman
Qualcomm, Inc., Campbell, California
2 shared publications - Andrey Turlikov1 shared publication
- Guy Bresler
Dept. of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA
1 shared publication
Latest Publications
- Open Access
Stability of a Random Multiple Access Channel with "Success-Failure" Feedback
We consider a model of a decentralized multiple access system with a non-standard binary feedback where the empty and collision situations cannot be distinguished. We show that, like in the case of a ternary feedback, for any input rate \lambda < 1/e, there exists a "doubly randomized" adaptive transmission protocol which stabilizes the behavior of the system. We discuss also a number of related problems and formulate some hypotheses.
Open AccessStability of a Random Multiple Access Channel with "Success-Failure" Feedback
We consider a model of a decentralized multiple access system with a non-standard binary feedback where the empty and collision situations cannot be distinguished. We show that, like in the case of a ternary feedback, for any input rate \lambda < 1/e, there exists a "doubly randomized" adaptive transmission protocol which stabilizes the behavior of the system. We discuss also a number of related problems and formulate some hypotheses.
- Open Access
Single Video Performance Analysis for Video-on-Demand Systems
We study the content placement problem for cache delivery video-on-demand systems under static random network topologies with fixed heavy-tailed video demand. The performance measure is the amount of server load; we wish to minimize the total download rate for all users from the server and maximize the rate from caches. Our approach reduces the analysis for multiple videos to consideration of decoupled systems with a single video each. For each placement policy, insights gained from the single video analysis carry back to the original multiple video content placement problem. Finally, we propose a hybrid placement technique that achieves near optimal performance with low complexity.
Open AccessSingle Video Performance Analysis for Video-on-Demand Systems
We study the content placement problem for cache delivery video-on-demand systems under static random network topologies with fixed heavy-tailed video demand. The performance measure is the amount of server load; we wish to minimize the total download rate for all users from the server and maximize the rate from caches. Our approach reduces the analysis for multiple videos to consideration of decoupled systems with a single video each. For each placement policy, insights gained from the single video analysis carry back to the original multiple video content placement problem. Finally, we propose a hybrid placement technique that achieves near optimal performance with low complexity.
- 1 June 2007
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 516-520
Low SNR Capacity of Fading Channels -MIMO and Delay Spread
Discrete-time Rayleigh fading multiple-input multiple-output (MIMO) channels are considered, with no channel state information at the transmitter and receiver. The fading is assumed to be correlated in time and independent from antenna to antenna. Peak and average transmit power constraints are imposed, either on the sum over antennas, or on each individual antenna. In both cases, an upper bound and an asymptotic lower bound, as the signal-to-noise ratio approaches zero, on the channel capacity are presented. The limit of normalized capacity is identified under the sum power constraints, and, for a subclass of channels, for individual power constraints. These results carry over to a SISO channel with delay spread (i.e. frequency selective fading).
- 1 June 2007
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 516-520
Low SNR Capacity of Fading Channels -MIMO and Delay Spread
Discrete-time Rayleigh fading multiple-input multiple-output (MIMO) channels are considered, with no channel state information at the transmitter and receiver. The fading is assumed to be correlated in time and independent from antenna to antenna. Peak and average transmit power constraints are imposed, either on the sum over antennas, or on each individual antenna. In both cases, an upper bound and an asymptotic lower bound, as the signal-to-noise ratio approaches zero, on the channel capacity are presented. The limit of normalized capacity is identified under the sum power constraints, and, for a subclass of channels, for individual power constraints. These results carry over to a SISO channel with delay spread (i.e. frequency selective fading).
- Open Access
Low SNR Capacity of Fading Channels -- MIMO and Delay Spread
Discrete-time Rayleigh fading multiple-input multiple-output (MIMO) channels are considered, with no channel state information at the transmitter and receiver. The fading is assumed to be correlated in time and independent from antenna to antenna. Peak and average transmit power constraints are imposed, either on the sum over antennas, or on each individual antenna. In both cases, an upper bound and an asymptotic lower bound, as the signal-to-noise ratio approaches zero, on the channel capacity are presented. The limit of normalized capacity is identified under the sum power constraints, and, for a subclass of channels, for individual power constraints. These results carry over to a SISO channel with delay spread (i.e. frequency selective fading).
Open AccessLow SNR Capacity of Fading Channels -- MIMO and Delay Spread
Discrete-time Rayleigh fading multiple-input multiple-output (MIMO) channels are considered, with no channel state information at the transmitter and receiver. The fading is assumed to be correlated in time and independent from antenna to antenna. Peak and average transmit power constraints are imposed, either on the sum over antennas, or on each individual antenna. In both cases, an upper bound and an asymptotic lower bound, as the signal-to-noise ratio approaches zero, on the channel capacity are presented. The limit of normalized capacity is identified under the sum power constraints, and, for a subclass of channels, for individual power constraints. These results carry over to a SISO channel with delay spread (i.e. frequency selective fading).
- Open Access
Gossiping with Multiple Messages
This paper investigates the dissemination of multiple pieces of information in large networks where users contact each other in a random uncoordinated manner, and users upload one piece per unit time. The underlying motivation is the design and analysis of piece selection protocols for peer-to-peer networks which disseminate files by dividing them into pieces. We first investigate one-sided protocols, where piece selection is based on the states of either the transmitter or the receiver. We show that any such protocol relying only on pushes, or alternatively only on pulls, is inefficient in disseminating all pieces to all users. We propose a hybrid one-sided piece selection protocol -- INTERLEAVE -- and show that by using both pushes and pulls it disseminates $k$ pieces from a single source to $n$ users in $10(k+\log n)$ time, while obeying the constraint that each user can upload at most one piece in one unit of time, with high probability for large $n$. An optimal, unrealistic centralized protocol would take $k+\log_2 n$ time in this setting. Moreover, efficient dissemination is also possible if the source implements forward erasure coding, and users push the latest-released coded pieces (but do not pull). We also investigate two-sided protocols where piece selection is based on the states of both the transmitter and the receiver. We show that it is possible to disseminate $n$ pieces to $n$ users in $n+O(\log n)$ time, starting from an initial state where each user has a unique piece.Open AccessGossiping with Multiple Messages
This paper investigates the dissemination of multiple pieces of information in large networks where users contact each other in a random uncoordinated manner, and users upload one piece per unit time. The underlying motivation is the design and analysis of piece selection protocols for peer-to-peer networks which disseminate files by dividing them into pieces. We first investigate one-sided protocols, where piece selection is based on the states of either the transmitter or the receiver. We show that any such protocol relying only on pushes, or alternatively only on pulls, is inefficient in disseminating all pieces to all users. We propose a hybrid one-sided piece selection protocol -- INTERLEAVE -- and show that by using both pushes and pulls it disseminates $k$ pieces from a single source to $n$ users in $10(k+\log n)$ time, while obeying the constraint that each user can upload at most one piece in one unit of time, with high probability for large $n$. An optimal, unrealistic centralized protocol would take $k+\log_2 n$ time in this setting. Moreover, efficient dissemination is also possible if the source implements forward erasure coding, and users push the latest-released coded pieces (but do not pull). We also investigate two-sided protocols where piece selection is based on the states of both the transmitter and the receiver. We show that it is possible to disseminate $n$ pieces to $n$ users in $n+O(\log n)$ time, starting from an initial state where each user has a unique piece. - 24 October 2006
- Published by AIP Publishing in The Journal of Chemical Physics
- Vol. 125 (16) , 164703
Kernel representations for flux and concentration in ion channel models with time-varying concentrations
This paper explores stochastic models for the study of ion transport in biological cells. It considers one-dimensional models with time-varying concentrations at the boundaries. The average concentration and flux in the channel are obtained as kernel representations, where the kernel functions have a probabilistic interpretation which contributes to a better understanding of the models. In particular, the kernel representation is given for the flux at a boundary point, providing a correct version of a representation found in the literature. This requires special attention because one of the kernel functions exhibits a singularity. This kernel representation is feasible due to the linearity of the system that arises from the assumed independence between ions.
- 24 October 2006
- Published by AIP Publishing in The Journal of Chemical Physics
- Vol. 125 (16) , 164703
Kernel representations for flux and concentration in ion channel models with time-varying concentrations
This paper explores stochastic models for the study of ion transport in biological cells. It considers one-dimensional models with time-varying concentrations at the boundaries. The average concentration and flux in the channel are obtained as kernel representations, where the kernel functions have a probabilistic interpretation which contributes to a better understanding of the models. In particular, the kernel representation is given for the flux at a boundary point, providing a correct version of a representation found in the literature. This requires special attention because one of the kernel functions exhibits a singularity. This kernel representation is feasible due to the linearity of the system that arises from the assumed independence between ions.
- 1 July 2006
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 21578095,p. 689-693
Low SNR Capacity of Fading Channels with Peak and Average Power Constraints
Flat-fading channels that are correlated in time are considered under peak and average power constraints. For discrete-time channels, a new upper bound on the capacity per unit time is derived. A low SNR analysis of a full-scattering vector channel is used to derive a complimentary lower bound. Together, these bounds allow us to identify the exact scaling of channel capacity for a fixed peak to average ratio, as the average power converges to zero. The upper bound is also asymptotically tight as the average power converges to zero for a fixed peak power. For a continuous time infinite bandwidth channel, Viterbi identified the capacity for M-FSK modulation. Recently, Zhang and Laneman showed that the capacity can be achieved with non-bursty signaling (QPSK). An additional contribution of this paper is to obtain similar results under peak and average power constraints
- 1 July 2006
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 21578095,p. 689-693
Low SNR Capacity of Fading Channels with Peak and Average Power Constraints
Flat-fading channels that are correlated in time are considered under peak and average power constraints. For discrete-time channels, a new upper bound on the capacity per unit time is derived. A low SNR analysis of a full-scattering vector channel is used to derive a complimentary lower bound. Together, these bounds allow us to identify the exact scaling of channel capacity for a fixed peak to average ratio, as the average power converges to zero. The upper bound is also asymptotically tight as the average power converges to zero for a fixed peak power. For a continuous time infinite bandwidth channel, Viterbi identified the capacity for M-FSK modulation. Recently, Zhang and Laneman showed that the capacity can be achieved with non-bursty signaling (QPSK). An additional contribution of this paper is to obtain similar results under peak and average power constraints
- 1 July 2006
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1315-1318
Note On Mutual Information and Orthogonal Space-Time Codes
Bit-error probability and mutual information rate have both been used as performance criteria for space-time codes for wireless communication. We use mutual information as the performance criterion because it determines the possible rate of communication when using an outer code. In this context, linear dispersion codes, first proposed by Hassibi and Hochwald, are appealing because of the high mutual information they provide, as well as their simplicity. Because complexity increases with the number of symbols, it may be sensible in some settings to fix the number of symbols sent per data bit. In the dissertation of Y. Jiang, it was conjectured that among linear dispersion codes with independent, binary symbols, orthogonal space-time codes are optimal in the following sense: they maximize mutual information subject to an average power constraint on each symbol. We prove the conjecture for a fixed number of real symbols with arbitrary distributions
- 1 July 2006
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1315-1318
Note On Mutual Information and Orthogonal Space-Time Codes
Bit-error probability and mutual information rate have both been used as performance criteria for space-time codes for wireless communication. We use mutual information as the performance criterion because it determines the possible rate of communication when using an outer code. In this context, linear dispersion codes, first proposed by Hassibi and Hochwald, are appealing because of the high mutual information they provide, as well as their simplicity. Because complexity increases with the number of symbols, it may be sensible in some settings to fix the number of symbols sent per data bit. In the dissertation of Y. Jiang, it was conjectured that among linear dispersion codes with independent, binary symbols, orthogonal space-time codes are optimal in the following sense: they maximize mutual information subject to an average power constraint on each symbol. We prove the conjecture for a fixed number of real symbols with arbitrary distributions
- 21 April 2006
- Published by American Physical Society (APS) in Physical Review E
- Vol. 73 (4) , 046126
Equivalence oftranspaths in ion channels
We explore stochastic models for the study of ion transport in biological cells. Analysis of these models explains and explores an interesting feature of ion transport observed by biophysicists. Namely, the average time it takes ions to cross certain ion channels is the same in either direction, even if there is an electric potential difference across the channels. It is shown for simple single ion models that the distribution of a path (i.e., the history of location versus time) of an ion crossing the channel in one direction has the same distribution as the time-reversed path of an ion crossing the channel in the reverse direction. Therefore, not only is the mean duration of these paths equal, but other measures, such as the variance of passage time or the mean time a path spends within a specified section of the channel, are also the same for both directions of traversal. The feature is also explored for channels with interacting ions. If a system of interacting ions is in reversible equilibrium (net flux is zero), then the equivalence of the left-to-right trans paths with the time-reversed right-to-left trans paths still holds. However, if the system is in equilibrium, but not reversible equilibrium, then such equivalence need not hold.
- 21 April 2006
- Published by American Physical Society (APS) in Physical Review E
- Vol. 73 (4) , 046126
Equivalence oftranspaths in ion channels
We explore stochastic models for the study of ion transport in biological cells. Analysis of these models explains and explores an interesting feature of ion transport observed by biophysicists. Namely, the average time it takes ions to cross certain ion channels is the same in either direction, even if there is an electric potential difference across the channels. It is shown for simple single ion models that the distribution of a path (i.e., the history of location versus time) of an ion crossing the channel in one direction has the same distribution as the time-reversed path of an ion crossing the channel in the reverse direction. Therefore, not only is the mean duration of these paths equal, but other measures, such as the variance of passage time or the mean time a path spends within a specified section of the channel, are also the same for both directions of traversal. The feature is also explored for channels with interacting ions. If a system of interacting ions is in reversible equilibrium (net flux is zero), then the equivalence of the left-to-right trans paths with the time-reversed right-to-left trans paths still holds. However, if the system is in equilibrium, but not reversible equilibrium, then such equivalence need not hold.
- 1 March 2006
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1391-1396
VCG-Kelly Mechanisms for Allocation of Divisible Goods: Adapting VCG Mechanisms to One-Dimensional Signals
The well known Vickrey-Clark-Groves (VCG) mechanism provides socially optimal solutions for many allocation problems with strategic buyers, but for divisible goods the bids are infinite dimensional. F.P. Kelly and his co-workers developed an allocation mechanism based on one dimensional bids, which is socially optimal if the buyers are price-takers. The idea is that the one-dimensional bid from a buyer specifies a surrogate valuation function. We propose the VCG-Kelly mechanism, which is obtained by composing the one-dimensional signaling idea of Kelly with the VCG mechanism, providing socially optimal allocation for strategic buyers at the Nash equilibrium point. The VCG-Kelly mechanism is studied in the case of a network rate allocation problem, and it applies to several others. It is shown how the revenue to the seller can be maximized or minimized using a particular one-dimensional family of functions. The Nash equilibrium point of the mechanism is shown to be globally stable.
- 1 March 2006
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1391-1396
VCG-Kelly Mechanisms for Allocation of Divisible Goods: Adapting VCG Mechanisms to One-Dimensional Signals
The well known Vickrey-Clark-Groves (VCG) mechanism provides socially optimal solutions for many allocation problems with strategic buyers, but for divisible goods the bids are infinite dimensional. F.P. Kelly and his co-workers developed an allocation mechanism based on one dimensional bids, which is socially optimal if the buyers are price-takers. The idea is that the one-dimensional bid from a buyer specifies a surrogate valuation function. We propose the VCG-Kelly mechanism, which is obtained by composing the one-dimensional signaling idea of Kelly with the VCG mechanism, providing socially optimal allocation for strategic buyers at the Nash equilibrium point. The VCG-Kelly mechanism is studied in the case of a network rate allocation problem, and it applies to several others. It is shown how the revenue to the seller can be maximized or minimized using a particular one-dimensional family of functions. The Nash equilibrium point of the mechanism is shown to be globally stable.