The network coding problem is a generalization of the maximum flow problem in which nodes can, in addition to forwarding messages, send encodings of combinations of incoming packets. This problem addresses the transmission of information, rather than physical goods, as information can be scrambled and unscrambled in ways that have no physical analogue. Network coding has been extremely successful in the setting of multicast. In this setting, network coding is an improvement over flow both because coding can send information at a higher rate and also because it can be computed efficiently. Much less is known about network coding in other settings, and this gap in knowledge is the focus of our work. Most significantly, we consider a problem called broadcasting with side information problem (BSIP): a problem that considers network coding on a restricted network structure but with arbitrary sending and receiving requests. The network structure is so simple that the problem is expressed only in terms of its senders and receivers. To go into more detail, the BSIP begins with a sender and sets of receivers and messages. Each receiver possesses a subset of the messages and desires an additional message from the set. The sender wishes to broadcast a message so that on receipt of the broadcast each user can compute her desired message. The objective is to find a minimum length broadcast that accomplishes this goal. The fundamental parameter of interest is [beta] , the average broadcast length for sufficiently long source messages. We obtain improved bounds on [beta] by strengthening and extending previously known bounds. Additionally, we introduce a new class of bounds based on an information-theoretic linear program. We show that many of these bounds behave nicely under various product and sum operations. Most notably, [beta] is sub-multiplicative, and the linear programming bounds are super-multiplicative under the same product operation. We use these new bounds and our understanding of them under products to obtain a multitude of results. We are the first to pinpoint [beta] precisely in nontrivial instances. We do this for many classes of symmetric instances including cycles and those derived from representable matroids. We find polynomial gaps between [beta] and its bounds in cases in which the largest previously known gaps were small constant factors or entirely unknown. We show a polynomial gap between [beta] and the linear coding rate and also between [beta] and its trivial lower bound. We construct a family of instances where [beta] is constant while its upper bound derived from the na¨ encoding scheme grows polynomially in the instance size. Finally, we give the ıve first nontrivial approximation algorithm for computing [beta] and we give a polynomial-time algorithm for recognizing instances with [beta] = 2. Apart from the BSIP, we consider the network coding variant of the maximum multicommodity flow problem in directed networks. We identify a class of networks on which the coding rate is equal to the size of the minimum multicut and show this class is closed under the strong graph product. We apply our result to strengthen the multicut bound for a famous construction of Saks et al.. We determine the exact value of the minimum multicut for their construction and give an optimal network coding solution with a matching rate.