A subset of the edges of a perfect matching in a graph is called a forcing set for it if no other perfect matching contains that subset. A complete forcing set of a graph is a subset of the edges such that the intersection of every perfect matching with the subset forms a forcing set for that perfect matching. The minimum size of the complete forcing sets of a graph is called the complete forcing number of the graph. In this paper, we determine the complete forcing number of the Cartesian product of two complete graphs, also known as Rook’s graphs, and present a minimum-sized complete forcing set for these graphs. For higher-dimensional Cartesian products of complete graphs, we use the result of the 2-fold Cartesian product case to present upper and lower bounds for the complete forcing number.

In this paper, we present a polynomial time algorithm for the problem of differentially private all pair shortest distances over the class of low tree-width graphs. Our result generalizes the result of Sealfon [10] for the case of trees to a much larger family of graphs. Furthermore, if we restrict to the class of low tree-width graphs, the additive error of our algorithm is significantly smaller than that of the best known algorithm for this problem, proposed by Chen et. al. in [3].

This paper is eligible for the Jack Keil Wolf ISIT Student Paper Award. We generalize a previous framework for designing utility-optimal differentially private (DP) mechanisms via graphs, where datasets are vertices in the graph and edges represent dataset neighborhood. The boundary set contains datasets where an individual’s response changes the binary-valued query compared to its neighbors. Previous work was limited to the homogeneous case where the privacy parameter ε across all datasets was the same and the mechanism at boundary datasets was identical. In our work, the mechanism can take different distributions at the boundary and the privacy parameter ε is a function of neighboring datasets, which recovers an earlier definition of personalized DP as special case. The problem is how to extend the mechanism, which is only defined at the boundary set, to other datasets in the graph in a computationally efficient and utility optimal manner. Using the concept of strongest induced DP condition we solve this problem efficiently in polynomial time (in the size of the graph).

Several fundamental problems that arise in optimization and computer science can be cast as follows: Given vectors v1, ..., vm∈ ℝdand a constraint family B ⊆ 2[m], find a set S ∈ B that maximizes the squared volume of the simplex spanned by the vectors in S. A motivating example is the ubiquitous data-summarization problem in machine learning and information retrieval where one is given a collection of feature vectors that represent data such as documents or images. The volume of a collection of vectors is used as a measure of their diversity, and partition or matroid constraints over [m] are imposed in order to ensure resource or fairness constraints. Even with a simple cardinality constraint (B = (r[m])), the r problem becomes NP-hard and has received much attention starting with a result by Khachiyan [1] who gave an rO(r)approximation algorithm for this problem. Recently, Nikolov and Singh [2] presented a convex program and showed how it can be used to estimate the value of the most diverse set when there are multiple cardinality constraints (i.e., when B corresponds to a partition matroid). Their proof of the integrality gap of the convex program relied on an inequality by Gurvits [3], and was recently extended to regular matroids [4], [5]. The question of whether these estimation algorithms can be converted into the more useful approximation algorithms - that also output a set - remained open. The main contribution of this paper is to give the first approximation algorithms for both partition and regular matroids. We present novel formulations for the subdeterminant maximization problem for these matroids; this reduces them to the problem of finding a point that maximizes the absolute value of a nonconvex function over a Cartesian product of probability simplices. The technical core of our results is a new anti-concentration inequality for dependent random variables that arise from these functions which allows us to relate the optimal value of these nonconvex functions to their value at a random point. Unlike prior work on the constrained subdeterminant maximization problem, our proofs do not rely on real-stability or convexity and could be of independent interest both in algorithms and complexity where anti-concentration phenomena has recently been deployed.

The capacity for multiterminal secret-key agreement inspires a natural generalization of Shannon's mutual information from two random variables to multiple random variables. Under a general source model without helpers, the capacity is shown to be equal to the normalized divergence from the joint distribution of the random sources to the product of marginal distributions minimized over partitions of the random sources. The mathematical underpinnings are the works on co-intersecting submodular functions and the principle lattices of partitions of the Dilworth truncation. We clarify the connection to these works and enrich them with information-theoretic interpretations and properties that are useful in solving other related problems in information theory as well as machine learning.

In [1], [2] it is shown that the minimum broadcast rate of a linear index code over a finite field Fqis equal to an algebraic invariant of the underlying digraph, called minrankq. In [3], it is proved that for F2and any positive integer k, minrankq(G) ≤ k if and only if there exists a homomorphism from the complement of the graph G to the complement of a particular undirected graph family called “graph family {Gk}”. As observed in [2], by combining these two results one can relate the linear index coding problem of undirected graphs to the graph homomorphism problem. In [4], a direct connection between linear index coding problem and graph homomorphism problem is introduced. In contrast to the former approach, the direct connection holds for digraphs as well and applies to any field size. More precisely, in [4], a graph family {Hkq} has been introduced and shown that whether or not the scalar linear index of a digraph G is less than or equal to k is equivalent to the existence of a graph homomorphism from the complement of G to the complement of Hkq. In this paper, we first study the structure of the digraphs Hkqdefined in [4]. Analogous to the result of [2] about undirected graphs, we prove that Hkqare vertex transitive digraphs. Using this, and by applying a lemma of Hell and Nesetril [5], we derive a class of necessary conditions for digraphs G to satisfy lindq(G) ≤ k. Particularly, we obtain new lower bounds on lindq(G). Our next result is about the computational complexity of scalar linear index of a digraph. It is known that deciding whether the scalar linear index of an undirected graph is equal to k or not is NP-complete for k ≥ 3 and is polynomially decidable for k = 1, 2 [3]. For digraphs, it is shown in [6] that for the binary alphabet, the decision problem for k = 2 is NP-complete. We use graph homomorphism framework to extend this result to arbitrary alphabet.

In this work, we study the problem of index coding from graph homomorphism perspective. We show that the minimum broadcast rate of an index coding problem for different variations of the problem such as non-linear, scalar, and vector index code, can be upper bounded by the minimum broadcast rate of another index coding problem when there exists a homomorphism from the complement of the side information graph of the first problem to that of the second problem. As a result, we show that several upper bounds on scalar and vector index code problem are special cases of one of our main theorems. For the linear scalar index coding problem, it has been shown in [1] that the binary linear index of a graph is equal to a graph theoretical parameter called minrank of the graph. For undirected graphs, in [2] it is shown that minrank(G) = k if and only if there exists a homomorphism from G to a predefined graph Gk. Combining these two results, it follows that for undirected graphs, all the digraphs with linear index of at most k coincide with the graphs G for which there exists a homomorphism from G to Gk. In this paper, we give a direct proof to this result that works for digraphs as well. We show how to use this classification result to generate lower bounds on scalar and vector index. In particular, we provide a lower bound for the scalar index of a digraph in terms of the chromatic number of its complement. Using our framework, we show that by changing the field size, linear index of a digraph can be at most increased by a factor that is independent from the number of the nodes.

It is well known that transfer polynomials play an important role in the network code design problem. In this paper we provide a graph theoretical description of the terms of such polynomials. We consider acyclic networks with arbitrary number of receivers and min-cut h between each source-receiver pair. We show that the associated polynomial can be described in terms of certain subgraphs of the network.

A long-standing open question in information theory is to characterize the unicast capacity of a wireless relay network. The difficulty arises due to the complex signal interactions induced in the network, since the wireless channel inherently broadcasts the signals and there is interference among transmissions. Recently, Avestimehr et al. [2007b] proposed a linear deterministic model that takes into account the shared nature of wireless channels, focusing on the signal interactions rather than the background noise. They generalized the min-cut max-flow theorem for graphs to networks of deterministic channels and proved that the capacity can be achieved using information theoretical tools. They showed that the value of the minimum cut is in this case the minimum rank of all the adjacency matrices describing source-destination cuts. In this article, we develop a polynomial-time algorithm that discovers the relay encoding strategy to achieve the min-cut value in linear deterministic (wireless) networks, for the case of a unicast connection. Our algorithm crucially uses a notion of linear independence between channels to calculate the capacity in polynomial time. Moreover, we can achieve the capacity by using very simple one-symbol processing at the intermediate nodes, thereby constructively yielding finite-length strategies that achieve the unicast capacity of the linear deterministic (wireless) relay network.

We consider the N-relay Gaussian diamond network when the source and the destination have ns≥ 2 and nd≥ 2 antennas respectively. We show that when ns= nd= 2 and when the individual MISO channels from the source to each relay and the SIMO channels from each relay to the destination have the same capacity, there exists a two relay sub-network that achieves approximately all the capacity of the network. To prove this result, we establish a simple relation between the joint entropies of three Gaussian random variables, which is not implied by standard Shannon-type entropy inequalities.

We develop new algebraic algorithms for scalar and vector network coding. In vector network coding, the source multicasts information by transmitting vectors of length L, while intermediate nodes process and combine their incoming packets by multiplying them with L × L coding matrices that play a similar role as coding coefficients in scalar coding. We start our work by extending the algebraic framework developed for multicasting over graphs by Koetter and Medard to include operations over matrices; we build on this generalized framework, to provide a new approach for both scalar and vector code design which attempts to minimize the employed field size and employed vector length, while selecting the coding operations. Our algorithms also lead as a special case to network code designs that employ structured matrices.

We develop new algebraic algorithms for scalar and vector network coding. In vector network coding, the source multicasts information by transmitting vectors of length L, while intermediate nodes process and combine their incoming packets by multiplying them with L × L coding matrices that play a similar role as coding coefficients in scalar coding. Our algorithms for scalar network jointly optimize the employed field size while selecting the coding coefficients. Similarly, for vector coding, our algorithms optimize the length L while designing the coding matrices. These algorithms apply both for regular network graphs as well as linear deterministic networks.

The unit distance graph $\mathcal{R}$ is the graph with vertex set $\mathbb{R}^2$ in which two vertices (points in the plane) are adjacent if and only if they are at Euclidean distance 1. We prove that the circular chromatic number of $\mathcal{R}$ is at least 4, thus improving the known lower bound of $32/9$ obtained from the fractional chromatic number of $\mathcal{R}$.