It is well known that feedback capacity is characterized using directed information which is a multi-letter expression. In this talk we aim to convert the multi-letter expression into a single-letter expression using a new idea of an auxiliary random variable that has a graphical structure. 

Auxiliary random variables (r.v.) play a fundamental role in characterizing the capacity of channels, especially in multi-user setting such as Gelfand-Pinsker or the degraded broadcast channel. In most cases, choosing a sequence of an i.i.d. auxiliary r.v. allows us to simplify a capacity expression and to have a computable, single-letter form. In this talk we will introduce a new kind of auxiliary r.v. that is not i.i.d. but has memory that is generated on a graphical structure. In particular, we show that the feedback capacity of the unifilar channel is upper bounded by a single-letter expression that is a function of the stationary distribution on the graph representing the memory of the auxiliary r.v..

In addition, we present a lower bound (LB) that uses auxiliary graphs that represent structured cooperation between the encoder and the decoder. Specifically, for a structured cooperation on a graph, the lower bound is given by an optimization problem that maximizes all input distributions on the particular graph. The resulting input distribution can be used to construct a posterior matching scheme (PMS) that achieves the LB.

We show concrete ways of computing the bounds. Furthermore, in all cases where the capacity is known, such as the trapdoor channel, Ising channel, Dicode channel, erasure channel with no repeated ones, the upper and lower bounds yield, with a small cardinality bound on the structured auxiliary r.v., a tight bounds on the feedback capacity.