Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA near-optimal direct-sum theorem for communication complexity
51
0
0.0
(
0
)
Added by
Rahul Jain
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Authors
Rahul Jain
Ask ChatGPT about the research
No Arabic abstract
We show a near optimal direct-sum theorem for the two-party randomized communication complexity. Let $fsubseteq X times Ytimes Z$ be a relation, $varepsilon> 0$ and $k$ be an integer. We show, $$mathrm{R}^{mathrm{pub}}_varepsilon(f^k) cdot log(mathrm{R}^{mathrm{pub}}_varepsilon(f^k)) ge Omega(k cdot mathrm{R}^{mathrm{pub}}_varepsilon(f)) enspace,$$ where $f^k= f times ldots times f$ ($k$-times) and $mathrm{R}^{mathrm{pub}}_varepsilon(cdot)$ represents the public-coin randomized communication complexity with worst-case error $varepsilon$. Given a protocol $mathcal{P}$ for $f^k$ with communication cost $c cdot k$ and worst-case error $varepsilon$, we exhibit a protocol $mathcal{Q}$ for $f$ with external-information-cost $O(c)$ and worst-error $varepsilon$. We then use a message compression protocol due to Barak, Braverman, Chen and Rao [2013] for simulating $mathcal{Q}$ with communication $O(c cdot log(ccdot k))$ to arrive at our result. To show this reduction we show some new chain-rules for capacity, the maximum information that can be transmitted by a communication channel. We use the powerful concept of Nash-Equilibrium in game-theory, and its existence in suitably defined games, to arrive at the chain-rules for capacity. These chain-rules are of independent interest.
rate research
Read More
Linear precoding techniques can achieve near- optimal capacity due to the special channel property in down- link massive MIMO systems, but involve high complexity since complicated matrix inversion of large size is required. In this paper, we propose a low-complexity linear precoding scheme based on the Gauss-Seidel (GS) method. The proposed scheme can achieve the capacity-approaching performance of the classical linear precoding schemes in an iterative way without complicated matrix inversion, which can reduce the overall complexity by one order of magnitude. The performance guarantee of the proposed GS-based precoding is analyzed from the following three aspects. At first, we prove that GS-based precoding satisfies the transmit power constraint. Then, we prove that GS-based precoding enjoys a faster convergence rate than the recently proposed Neumann-based precoding. At last, the convergence rate achieved by GS-based precoding is quantified, which reveals that GS-based precoding converges faster with the increasing number of BS antennas. To further accelerate the convergence rate and reduce the complexity, we propose a zone-based initial solution to GS-based precoding, which is much closer to the final solution than the traditional initial solution. Simulation results demonstrate that the proposed scheme outperforms Neumann- based precoding, and achieves the exact capacity-approaching performance of the classical linear precoding schemes with only a small number of iterations both in Rayleigh fading channels and spatially correlated channels.
We consider an energy-harvesting communication system where a transmitter powered by an exogenous energy arrival process and equipped with a finite battery of size $B_{max}$ communicates over a discrete-time AWGN channel. We first concentrate on a simple Bernoulli energy arrival process where at each time step, either an energy packet of size $E$ is harvested with probability $p$, or no energy is harvested at all, independent of the other time steps. We provide a near optimal energy control policy and a simple approximation to the information-theoretic capacity of this channel. Our approximations for both problems are universal in all the system parameters involved ($p$, $E$ and $B_{max}$), i.e. we bound the approximation gaps by a constant independent of the parameter values. Our results suggest that a battery size $B_{max}geq E$ is (approximately) sufficient to extract the infinite battery capacity of this channel. We then extend our results to general i.i.d. energy arrival processes. Our approximate capacity characterizations provide important insights for the optimal design of energy harvesting communication systems in the regime where both the battery size and the average energy arrival rate are large.
This paper studies the transmit beamforming in a downlink integrated sensing and communication (ISAC) system, where a base station (BS) equipped with a uniform linear array (ULA) sends combined information-bearing and dedicated radar signals to simultaneously perform downlink multiuser communication and radar target sensing. Under this setup, we maximize the radar sensing performance (in terms of minimizing the beampattern matching errors or maximizing the minimum beampattern gains), subject to the communication users minimum signal-to-interference-plus-noise ratio (SINR) requirements and the BSs transmit power constraints. In particular, we consider two types of communication receivers, namely Type-I and Type-II receivers, which do not have and do have the capability of cancelling the interference from the {emph{a-priori}} known dedicated radar signals, respectively. Under both Type-I and Type-II receivers, the beampattern matching and minimum beampattern gain maximization problems are globally optimally solved via applying the semidefinite relaxation (SDR) technique together with the rigorous proof of the tightness of SDR for both Type-I and Type-II receivers under the two design criteria. It is shown that at the optimality, dedicated radar signals are not required with Type-I receivers under some specific conditions, while dedicated radar signals are always needed to enhance the performance with Type-II receivers. Numerical results show that the minimum beampattern gain maximization leads to significantly higher beampattern gains at the worst-case sensing angles with a much lower computational complexity than the beampattern matching design. It is also shown that by exploiting the capability of canceling the interference caused by the radar signals, the case with Type-II receivers results in better sensing performance than that with Type-I receivers and other conventional designs.
We give a direct product theorem for the entanglement-assisted interactive quantum communication complexity of an $l$-player predicate $mathsf{V}$. In particular we show that for a distribution $p$ that is product across the input sets of the $l$ players, the success probability of any entanglement-assisted quantum communication protocol for computing $n$ copies of $mathsf{V}$, whose communication is $o(log(mathrm{eff}^*(mathsf{V},p))cdot n)$, goes down exponentially in $n$. Here $mathrm{eff}^*(mathsf{V}, p)$ is a distributional version of the quantum efficiency or partition bound introduced by Laplante, Lerays and Roland (2014), which is a lower bound on the distributional quantum communication complexity of computing a single copy of $mathsf{V}$ with respect to $p$. As an application of our result, we show that it is possible to do device-independent quantum key distribution (DIQKD) without the assumption that devices do not leak any information after inputs are provided to them. We analyze the DIQKD protocol given by Jain, Miller and Shi (2017), and show that when the protocol is carried out with devices that are compatible with $n$ copies of the Magic Square game, it is possible to extract $Omega(n)$ bits of key from it, even in the presence of $O(n)$ bits of leakage. Our security proof is parallel, i.e., the honest parties can enter all their inputs into their devices at once, and works for a leakage model that is arbitrarily interactive, i.e., the devices of the honest parties Alice and Bob can exchange information with each other and with the eavesdropper Eve in any number of rounds, as long as the total number of bits or qubits communicated is bounded.
Integrating unmanned aerial vehicles (UAVs) into the cellular network as new aerial users is a promising solution to meet their ever-increasing communication demands in a plethora of applications. Due to the high UAV altitude, the channels between UAVs and the ground base stations (GBSs) are dominated by the strong line-of-sight (LoS) links, thus severe interference may be generated to/from the GBSs in the uplink/downlink, which renders the interference management with coexisting terrestrial and aerial users a more challenging problem to solve. In this paper, we study the uplink communication from a multi-antenna UAV to a set of GBSs in its signal coverage region. Among these GBSs, we denote available GBSs as the ones that do not serve any terrestrial users at the assigned resource block (RB) of the UAV, and occupied GBSs as the rest that are serving their respectively associated terrestrial users in the same RB. We propose a new cooperative interference cancellation strategy for the multi-beam UAV uplink communication, which aims to eliminate the co-channel interference at each of the occupied GBSs and in the meanwhile maximize the sum-rate to the available GBSs. Specifically, the multi-antenna UAV sends multiple data streams to selected available GBSs, which in turn forward their decoded data streams to their backhaul-connected occupied GBSs for interference cancellation. To draw useful insights, the maximum degrees-of-freedom (DoF) achievable by the multi-beam UAV communication for sum-rate maximization in the high signal-to-noise ratio (SNR) regime is first characterized, subject to the stringent constraint that all the occupied GBSs do not suffer from any interference in the UAVs uplink transmission. Then, based on the DoF-optimal design, the achievable sum-rate at finite SNR is maximized, subject to given maximum allowable interference power constraints at each occupied GBS.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
