Central to many statistical inference problems is the computation of

some quantities defined over variables that can be fruitfully modeled

in terms of graphs. Examples of such quantities include marginal

distributions over graphical models and empirical average of

observations over sensor networks. For practical purposes, distributed

message-passing algorithms are well suited to deal with such

problems. In particular, the computation is broken down into pieces

and distributed among different nodes. Following some local

computations, the intermediate results are shared among neighboring

nodes via the so called messages. The process is repeated until the

desired quantity is obtained. These distributed inference algorithms

have two primary aspects: statistical properties, in which

characterize how mathematically sound an algorithm is, and

computational complexity that describes the efficiency of a particular

algorithm. In this thesis, we propose low-complexity (efficient),

message-passing algorithms as alternatives to some well known

inference problems while providing rigorous mathematical analysis of

their performances. These problems include the computation of the

marginal distribution via belief propagation for discrete as well as

continuous random variables, and the computation of the average of

distributed observations in a noisy sensor network via gossip-type

algorithms.