Zero-error coding for compression and computation with distributed sources

The study of rates of transmission for the three-person source coding problem, where two separate encoders wish to convey their correlated data to a receiver without any error (i.e., with zero-error), is initiated. The closely related three-person function evaluation problem, where the receiver is only interested in correctly evaluating a known function of the data, is also studied. These problems are motivated by emerging applications in the design of remote sensing networks and in distributed computing.; The first part of the thesis focuses on exactly calculating (where possible), or deriving bounds (otherwise) for the minimum asymptotic rates of transmission. The two-person restrictions of the problems, where the receiver is permitted direct access to one of the two sources, are already of interest, and have been previously studied in the literature. The main results of this part of the thesis are: (i) a characterization of the minimum rate for two-person source coding as the complementary graph entropy of an associated graph, (ii) a single-letter formula for the achievable rate pairs for three-person function evaluation, (iii) bounds for the achievable rate pairs for three-person source coding, and (iv) conditions for the tightness of these bounds.; The focus shifts in the second part of the thesis to design of coding systems, for the two-person problems. It is shown that the design of optimal codes is an NP-Hard problem. Thus optimal design for large problem instances may be computationally intensive, and fast, suboptimal algorithms acquire greater interest. Such algorithms, based on ideas from graph coloring, are proposed, and their performance guarantees are studied. An optimal design algorithm, with exponential worst-case complexity, is also derived.; Other topics considered in the thesis include bounds for non-asymptotic minimum rates, asymptotic bounds for fixed-length coding, and graph-theoretic properties of the complementary graph entropy.