Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn Optimization Approach to the Langberg-Medard Multiple Unicast Conjecture
57
0
0.0
(
0
)
Added by
Guangyue Han
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The Langberg-Medard multiple unicast conjecture claims that for any strongly reachable $k$-pair network, there exists a multi-flow with rate $(1,1,dots,1)$. In a previous work, through combining and concatenating the so-called elementary flows, we have constructed a multi-flow with rate at least $(frac{8}{9}, frac{8}{9}, dots, frac{8}{9})$ for any $k$. In this paper, we examine an optimization problem arising from this construction framework. We first show that our previous construction yields a sequence of asymptotically optimal solutions to the aforementioned optimization problem. And furthermore, based on this solution sequence, we propose a perturbation framework, which not only promises a better solution for any $k mod 4 eq 2$ but also solves the optimization problem for the cases $k=3, 4, dots, 10$, accordingly yielding multi-flows with the largest rate to date.
rate research
Read More
The Langberg-M{e}dard multiple unicast conjecture claims that for a strongly reachable $k$-pair network, there exists a multi-flow with rate $(1,1,dots,1)$. In this paper, we show that the conjecture holds true for {em stable} $3$-pair networks.
This paper studies the problem of information theoretic secure communication when a source has private messages to transmit to $m$ destinations, in the presence of a passive adversary who eavesdrops an unknown set of $k$ edges. The information theoretic secure capacity is derived over unit-edge capacity separable networks, for the cases when $k=1$ and $m$ is arbitrary, or $m=3$ and $k$ is arbitrary. This is achieved by first showing that there exists a secure polynomial-time code construction that matches an outer bound over two-layer networks, followed by a deterministic mapping between two-layer and arbitrary separable networks.
Given two random variables $X$ and $Y$, an operational approach is undertaken to quantify the ``leakage of information from $X$ to $Y$. The resulting measure $mathcal{L}(X !! to !! Y)$ is called emph{maximal leakage}, and is defined as the multiplicative increase, upon observing $Y$, of the probability of correctly guessing a randomized function of $X$, maximized over all such randomized functions. A closed-form expression for $mathcal{L}(X !! to !! Y)$ is given for discrete $X$ and $Y$, and it is subsequently generalized to handle a large class of random variables. The resulting properties are shown to be consistent with an axiomatic view of a leakage measure, and the definition is shown to be robust to variations in the setup. Moreover, a variant of the Shannon cipher system is studied, in which performance of an encryption scheme is measured using maximal leakage. A single-letter characterization of the optimal limit of (normalized) maximal leakage is derived and asymptotically-optimal encryption schemes are demonstrated. Furthermore, the sample complexity of estimating maximal leakage from data is characterized up to subpolynomial factors. Finally, the emph{guessing} framework used to define maximal leakage is used to give operational interpretations of commonly used leakage measures, such as Shannon capacity, maximal correlation, and local differential privacy.
We consider the problem of network coding across three unicast sessions over a directed acyclic graph, where each sender and the receiver is connected to the network via a single edge of unit capacity. We consider a network model in which the middle of the network only performs random linear network coding, and restrict our approaches to precoding-based linear schemes, where the senders use precoding matrices to encode source symbols. We adapt a precoding-based interference alignment technique, originally developed for the wireless interference channel, to construct a precoding-based linear scheme, which we refer to as as a {em precoding-based network alignment scheme (PBNA)}. A primary difference between this setting and the wireless interference channel is that the network topology can introduce dependencies between elements of the transfer matrix, which we refer to as coupling relations, and can potentially affect the achievable rate of PBNA. We identify all possible such coupling relations, and interpret these coupling relations in terms of network topology and present polynomial-time algorithms to check the presence of these coupling relations. Finally, we show that, depending on the coupling relations present in the network, the optimal symmetric rate achieved by precoding-based linear scheme can take only three possible values, all of which can be achieved by PBNA.
A communication setup is considered where a transmitter wishes to convey a message to a receiver and simultaneously estimate the state of that receiver through a common waveform. The state is estimated at the transmitter by means of generalized feedback, i.e., a strictly causal channel output, and the known waveform. The scenario at hand is motivated by joint radar and communication, which aims to co-design radar sensing and communication over shared spectrum and hardware. For the case of memoryless single receiver channels with i.i.d. time-varying state sequences, we fully characterize the capacity-distortion tradeoff, defined as the largest achievable rate below which a message can be conveyed reliably while satisfying some distortion constraints on state sensing. We propose a numerical method to compute the optimal input that achieves the capacity-distortion tradeoff. Then, we address memoryless state-dependent broadcast channels (BCs). For physically degraded BCs with i.i.d. time-varying state sequences, we characterize the capacity-distortion tradeoff region as a rather straightforward extension of single receiver channels. For general BCs, we provide inner and outer bounds on the capacity-distortion region, as well as a sufficient condition when this capacity-distortion region is equal to the product of the capacity region and the set of achievable distortions. A number of illustrative examples demonstrates that the optimal co-design schemes outperform conventional schemes that split the resources between sensing and communication.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
