Organizing
Committee:
 Misha Chertkov
LANL (T13)
 Anders Hansson
LANL (CCS3)
 Allon Percus
LANL (CCS3)

Program
Speaker: Dimitris Achlioptas, UCSC
Title: Random Constraint Satisfaction Problems: From Physics to Algorithms
For a number of random constraint satisfaction problems, such as
random kSAT and random graph coloring, we now have excellent
estimates of the largest constraintstovariables ratio for which
they have solutions. These estimates imply that all known polynomial
time algorithms stop finding solutions much before solutions cease to
exist. To understand the origin of this phenomenon we study the
evolution of the structure of the space of solutions in random CSPs
as constraints are added. In particular, we will survey both what
physicists hypothesize happens in this evolution, and what has been
rigorously proven so far. We will see that the rigorous results are
both in agreement with the physics predictions and help demystify
Survey Propagation, an extremely successful heuristic proposed by
physicists for random CSPs.


Speaker: Chen Avin, Ben Gurion U
Title: Random Walks Techniques in Networking
In recent years randomwalkbased algorithms have
been proposed for a variety of networking tasks.
These proposals include searching, routing,
selfstabilization, and query processing in
wireless networks, peertopeer networks and
other distributed systems. This approach is
gaining popularity since random walks present
locality, simplicity, lowoverhead and inherent
robustness to structural changes. Two properties of the random walk on graphs are
essential to determine the efficiency of this
approach: cover time (the expected time to visit
all nodes) and mixing time (the time to sample a
node uniformly). In this talk I will present some
of my work on the topic, including: 1.) The cover
time and mixing time of a simple model of random
wireless network (i.e random geometric graphs).
2.) Enhancing random walk efficiency by
implementing the power of 2 choice into the walk.
3.) Some inprogress work (to be announced later).


Speaker: Vladimir Chernyak, Wyane State
Title: Loop Calculus and Belief Propagation for qary Alphabet: Loop Tower
Loop Calculus introduced in [Chertkov, Chernyak '06] constitutes
a new theoretical tool that explicitly expresses the symbol
Maximum A Posteriori (MAP) solution of a general statistical
inference problem via a solution of the Belief Propagation (BP) equations.
This finding brought a new significance to the BP concept, which
in the past was thought of as just a loopfree approximation.
In this talk we continue a discussion of the Loop Calculus.
We introduce an invariant formulation which helps to generalize
the Loop Calculus approach to a qare alphabet.


Speaker: Aaron Clauset, Santa Fe Institute
Title: Seeing Past the Hype: Making PowerLaw Distributions Useful Again
Powerlaw distributed quantities are
ubiquitous in the physics of complex systems,
being at the heart of many quite general
mechanisms. And yet, the statistical methods used
in physics to infer or estimate powerlaw behavior
from actual data are ad hoc, subjective, and often
highly biased. Further, such powerlaw models are
rarely validated in any strong sense of the word.
In this talk, I first discuss the problems with
current methods for fitting and testing powerlaw
models of distributions. Then, I summarize a new
inference framework for dealing with heavytailed
data that is principled, objective, and accurate.
In closing, I briefly reconsider, using these new
tools, 25 data sets and their previously
conjectured powerlaw distributions. And, far
from being the end of the modeling phase, I show
that a careful comparison with a powerlaw model
can generate useful new hypotheses for future
investigation.


Speaker: Ashish Goel, Stanford
Title: Sampling, aggregation, and phase transitions in sensor networks
Unlike data networks, the connectivity of sensor networks is largely
dictated by spatial proximity. This makes grids and random geometric
graphs good idealized models for sensor networks, and often results
in simpler algorithms and stronger properties. We will explore three
problems along this general theme.
(a) Phase transitions: We show that all monotone graph properties
undergo sharp phase transitions in geometric random graphs as the
radius of communication increases. This settles a conjecture of
Krishnamachari et al and McColm. The phase transitions in geometric
random graphs are both much sharper and much stronger than for
Bernoulli random graphs.
(b) Aggregating spatially correlated data: We present a simple
randomized process for aggregating spatially correlated data (in an N
x N grid) as it travels to a central collection agent. The
aggregation tree we construct is within a constant factor of the
optimum, regardless of the scale of correlation.
(c) Multiscale sampling: We present a scheme whereby any sensor node
(in an N x N grid) can approximately answer moment and quantile
queries about any rectangular region which contains the node. No
communication is required at querytime. During the preprocessing
phase, each node essentially draws K independent samples from all
surrounding rectangular regions while performing only O(K log^2 N)
transmissions.Part (a) represents joint work with Rai and Krishnamachari. Part (b)
represents joint work with Enachescu, Govindan, and Motwani.


Speaker: Vicenç Gómez, U of Pompeu Fabra
Title: Truncating the Loop Series Expansion for Belief Propagation
Recently, M. Chertkov and V.Y. Chernyak derived an
exact expression for the partition sum
(normalization constant) corresponding to a
graphical model, which is an expansion around the
Belief Propagation solution. By adding correction
terms to the BP free energy, one for each
"generalized loop" in the factor graph, the
exact partition sum is obtained. However, the
usually enormous number of generalized loops
generally prohibits summation over all correction
terms. In this article we introduce Truncated Loop
Series BP (TLSBP), a particular way of truncating
the loop series of M. Chertkov and V.Y. Chernyak
by considering generalized loops as compositions
of simple loops. We analyze the performance of
TLSBP in different scenarios, including the Ising
model, regular random graphs and on Promedas, a
large probabilistic medical diagnostic system. We
show that TLSBP often improves upon the accuracy
of the BP solution, at the expense of increased
computation time. We also show that the
performance of TLSBP strongly depends on the
degree of interaction between the variables. For
weak interactions, truncating the series leads to
significant improvements, whereas for strong
interactions it can be ineffective, even if a
high number of terms is considered.


Speaker: Hasan Guclu, LANL
Title: TaskBased Synchronization in Complex Noisy Networks
We study the statistics and scaling of
fluctuations in noisy taskcompletion landscapes, such as those
emerging in synchronized distributedcomputing networks, or generic
causallyconstrained queuing networks. For smallworld and scalefree
networks the average size of the fluctuations becomes finite
(synchronized state) and the extreme fluctuations typically diverge at most
logarithmically in the large systemsize limit ensuring synchronization
in a practical sense. Provided that local fluctuations in the network
are shorttailed, the statistics of the extremes are governed by
the Gumbel distribution.


Speaker: Thomas Halford, USC
Title: Improving Belief Propagation via Graphical Model Transformation
It is now wellknown that belief propagation (BP)
results in exact inference algorithms on
cyclefree graphical models and inexact, yet
often substantially less complex, inference
algorithms on graphical models with cycles. A
number of approaches have been taken to improving
the performance of BP for the latter case.
Yedidia et al. considered generalizations of BP
acting on regions of the original graph.
Motivated by statistical physics, Chernyak and
Chertkov introduced the loop calculus approach.
Both of these methodologies can be viewed as
applying a nonstandard BP algorithm to a
standard graphical model. In this talk, an alternative approach is
described in the context of graphical models for
codes. Specifically, we consider the application
of the standard BP algorithm to nonstandard
models. In order to derive such nonstandard
models, we introduce a set of graphical model
transformations which is shown to span the space
of all models for a given fixed code. These
transformations thus enable the search for
nonstandard models to be formalized in the
language of combinatorial optimization. The
efficacy of this approach is demonstrated via
simulation. We conclude with a discussion of the
relationships between model transformation,
generalizations of BP, and the loop calculus.


Speaker: Matthew Hastings, LANL
Title: Community Detection and Clustering as Inference Problems
Community detection is a wellstudied problem with applications to biological,
social, and other networks. Remarkably, however, there is no good definition of
this problem. In this talk, we show that one of the standard tests of community
detection algorithms, the "four groups" test due to Newman and Girvan, provides
a precise definition of community detection as a problem in Bayesian inference.
We then apply techniques used for other Bayesian inference problems, in particular
the belief propagation algorithm developed for decoding errorcorrecting codes
in communication over a noisy channel, to develop a very accurate and fast
community detection algorithm. We then apply related techniques to similar
problems such as data clustering.


Speaker: Ralf Koetter, TU München
Title: Random Network Coding for Errors and Erasures
We consider the problem of organizing multicast and unicast connections in a network.
Random network coding is by now a well understood formalism for this task.
We address the problem of erroneous, undetected errors and erasures. We show
how coding schemes in the Grassmannian graph are a natural approach to address
the arising problems.


Speaker: Bhaskar Krishnamachari, USC
Title: Querying Sensor Networks
Wireless ad hoc sensor networks can be viewed as distributed
databases where information about significant events are stored within
the network and retrieved through queries. We present a few case studies
concerning the design and analysis of structured and unstructured
querying techniques for these networks. These include fundamental
scaling laws for querying, comparison of different pushpull schemes,
and some interesting enhancements of the simple random walk for
efficient querying.


Speaker: Lukas Kroc, Cornell
Title: Empirical validation of the relationship between Survey Propagation
and covers in random 3SAT
It was recently shown that Survey
Propagation (SP) can be viewed as a form of
belief propagation, computing marginal
probabilities over certain objects called covers
of a formula. However, the existence of these
objects in random 3SAT formulas has not been
proved yet, and initial empirical evidence has
suggested that covers may not even exist in large
such formulas. In this work, we perform a detailed
empirical study of covers in random 3SAT,
obtaining evidence suggesting that such covers do
exist even for large formulas, albeit they are
hard to find using traditional SAT techniques.
Moreover, despite the loopiness of the formulas,
SP is surprisingly accurate at computing
marginals over these covers. This reopens the
possibility that SP\'s remarkable success on
random 3SAT can be attributed to effects
analogous to those in random kSAT for higher
values of k, where the situation is much better
understood (namely, in terms of covers).


Speaker: Muriel Médard, MIT
Title: Some Interesting Directions in Network Coding
Network coding has been shown to be beneficial in terms of throughput
for networks. However, the interplay between theory and practice
depends not only on improved throughput performance but also on ease
of algorithmic implementation, impact on other performance measures
and interaction with existing systems. In this talk, we overview some
of the algorithmic issues concerning network coding, such as
distributed optimization in multicast systems and choice of network
codes in nonmulticast scenarios. We also address issues of delay and
robustness in network coded systems. We propose some new algorithmic
directions for network coding and discuss their potential impact on
performance.


Speaker: Marc Mezard, CNRS & Universite Paris Sud
Title: Information Broadcast on a Tree: The Reconstruction Problem
Consider a tree network whose links correspond to noisy
communication channels. An information source generates a symbol at
the root of the tree and broadcasts it through the network. The
reconstruction problem asks whether the information received at the
leaves allows to reconstruct the symbol which was transmitted. In
the large system limit, there is a phase transition: reconstruction
is possible only when the channel noise is smaller than a threshold.
This talk shows that the reconstruction threshold coincides
with the dynamical glass transition for an associated statistical
physics problem. This correspondence allows to derive a number of
new results for reconstruction. It also sheds some new light
on glass transitions.


Speakers: Sanjoy Mitter, MIT and Nigel Newton, U of Essex & MIT
Title: A Variational View of Statistical Inference and Channel Coding
In the 60 or so years since Shannon's noisy channel coding theorem a number of papers have
been published on its connections with statistical mechanics. A common feature of these
is that the phenomenon of channel capacity is viewed as a type of phase transition.
The talk will develop these ideas, but in the framework of Bayesian inference.
This admits a variational form, in which the posterior distribution minimises an
information quantity we call the 'apparent information'. The variational formulation
can be extended to infinite systems, where it shares many of the properties of
the Gibbs variational principle. We shall consider a number of estimation problems
associated with the noisy channel coding theorem, and show that connections between
the specific apparent information quantities in the different layers of the communication
architecture are at its heart. The specific apparent information quantities for these
problems exhibit a variety of phase transitions. We give preliminary results on the
existence and nature of 'Gibbs' measures in this context. Standard results on their
existence and uniqueness, requiring translation invariance, are not applicable here.
The broader conceptual goal of our research is to understand statistical mechanics
where observations are explicitly modeled, and to view statistical inference of the
'state' given 'observations' as a problem of interactive statistical mechanics.
We believe that there are nontrivial connections between recent work on nonequilibrium
statistical mechanics (Gallavotti, Ruelle, Lebowitz) and statistical inference.
We have shown that these connections are quite precise in the context of observed
diffusion processes. Generalizations of work on decay of correlations and correlation
inequalities (for example, GKS inequalities) to the context of statistical inference
are challenging problems whose investigation would lead to a deeper connection between
statistical physics and statistical inference.


Speaker: Andrea Montanari, Stanford
Title: Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
An instance of a random constraint satisfaction problem defines a random
subset S (the set of solutions) of a large product space (the set of
assignments). I will consider two prototypical problem ensembles (random
ksatisfiability and qcoloring of random regular graphs), and study the
uniform measure with support on S. As the number of constraints per
variable increases, this measure first decomposes into an exponential
number of pure states ("clusters"), and subsequently condensates over the
largest such states.
I will discuss the nature and location of these phase transitions,
as well as their algorithmic implications.


Speaker: Cristopher Moore, University of New Mexico & Santa Fe Institute
Title: Inferring Hierarchical Structure and Predicting Missing Links
Many realworld networks appear to have a hierarchical structure,
containing communities and subcommunities at many different scales.
These could correspond to interest groups on the Web, functional
units in a metabolism, or ecological communities in a food web. We
present a mathematically principled way to infer these structures
from realworld network data; specifically, we use a Markov chain
Monte Carlo algorithm to sample hierarchical structures with
probability proportional to the likelihood with which they would
generate the observed connections. Our method does much more than
simply clustering the network: instead, it automatically detects both
assortative and disassortative behavior at all scales of
organization. Moreover, it allows us to rate how "surprising" a
given connection is, and it performs far better than chance if we use
it to predict connections that have not yet been observed. It may
therefore be useful to experimenters for whom observing connections
is costly. While this work is primarily experimental, it presents a
number of interesting questions for theorists: how quickly does this
Markov chain mix on different kinds of graphs? What can we say about
network structure in a model where connections must be queried,
rather than being observed all at once? Finally, what is it about
realworld networks that makes these structures so important?


Speaker: Elchanan Mossel, UC Berkeley
Title: Convergence of message passing algorithms on planted models: how and why?
I will discuss the planted model for sat and recent results showing that
message passing algorithms are effective for finding SAT assignments for
such models. I will also address the problem of why this is interesting.


Speaker: Muthu Muthukrishnan, Rutgers & Google
Title: Algorithmic Aspects of Sparse Approximation Problems
The sparse approximation problem is to find the best linear combination
of at most B vectors from a prespecified dictionary of N dimensional
vectors for a given input vector V, also of N dimensions. The classical
versions arise from late 1700's with orthonormal dictionaries; the
modern versions have richer dictionaries, weighted norms or study
compressed sensing. This talk will focus on algorithmic results for
such problems.


Speaker: Eli BenNaim, LANL
Title: How to Chose a Champion
League competition is investigated using random processes and scaling
techniques. In our model, a weak team can upset a strong team with a
fixed probability. Teams play an equal number of headtohead matches
and the team with the largest number of wins is declared to be the
champion. The total number of games needed for the best team to win
the championship with high certainty, T, grows as the cube of the
number of teams, N, i.e., T ~ N^3. This number can be substantially
reduced using preliminary rounds where teams play a small number of
games and subsequently, only the top teams advance to the next
round. When there are k rounds, the total number of games needed for
the best team to emerge as champion, T_k, scales as follows, T_k
~N^(\gamma_k) with gamma_k=1/[1(2/3)^(k+1)]. For example,
gamma_k=9/5,27/19,81/65 for k=1,2,3. These results suggest an
algorithm for how to infer the best team using a schedule that is
linear in N. We conclude that league format is an ineffective method
of determining the best team, and that sequential elimination from the
bottom up is fair and efficient.


Speaker: Nandakishore Santhi, LANL
Title: The Secant Method Decoder
Several efficient near optimal decoding methods have been proposed in recent times for low density parity check codes.
Most of these decoding methods are related to the beliefpropagation technique on graphs with loops, pioneered by Gallager in the 1950s.
These decoders can also be understood in terms of linear programming. In this paper we discuss a completely different decoder based on
an iterative nonlinear minimization technique also from the 1950s.
We consider the recovery of binary coded messages corrupted by noise on a BSC channel.
We form a system of nonlinear equations whose solution is the desired codeword estimate.
This system is then solved using a modified multidimensional secant method which can be shown
to have a local rate of convergence equal to the goldenratio. We will present experimental results for typical binary codes.


Speaker: Devavrat Shah, MIT
Title: Maxproduct for Maximum Weight Independent Set
Given a graph G=(V,E), an independent set I is a subset
of V such that no two vertexes in I are connected in G.
When vertexes of G are assigned weights, the weight of
I is the sum of weights of vertexes in it. The question of
finding an independent set with the maximum weight arises in
communication networks, distributed databases, parallel
computation, etc. In these applications, algorithms
are required to be distributed for architectural reasons.
The maxproduct heuristic is by design distributed and iterative.
The algorithm applied for max wt independent set is known
to find a correct solution when G is a tree or "treelike"
with random (exponential) weights. However, it is not clear
what happens when underlying graph has short cycles.
In this talk, I will discuss the correctness and convergence
of (a slightly modified asynchronous) maxproduct to find
max. wt. independent set for any bipartite graph with arbitrary
nonnegative weights. These properties will be established
by relating the maxproduct with an appropriate coordinate
descent algorithm for the dual relaxation of integral
linear program corresponding to the max. wt. independent set.


Speaker: Misha Stepanov, UofA Tucson
Title: Dynamical stuctures in iterative decoding
Standard iterative decoding of a graph based code does not guarantee
convergence. For some codes decoded iteratively, as for the model
[155,64,20] code considered, cycling of iterations is observed for
lower weight configuration of the noise dominating the error floor
asymptotic. The behavior of the iterative decoding near this
special configuration is chaotic. As shown in [Stepanov,
Chertkov'06] the iterative scheme can be improved to enforce the
iteration convergence. We discuss in this talk how the decoding
improvement affects the dangerous cycling configuration.


Speaker: Mohammad Hossein Taghavi, UCSD
Title: GraphBased Decoding in the Presence of ISI
We present some recent results on a
technique for approximating the
maximumlikelihood (ML) detection in ISI channels
based on linear programming (LP) or message
passing (MP). In this method, we convert the
detection problem into a binary decoding problem,
which can be easily combined with LDPC decoding.
We analyze the performance of LPbased detection
in the absence of coding, and classify the ISI
channels based on how LP detection performs on
them. In particular, for a certain class of
channels, uncoded LP detection provides the exact
ML solution without an exponential complexity in
the size of the channel memory, while for some
other channels, this method has a nondiminishing
probability of failure as SNR increases. We
further present some simulation results, showing
that while uncoded LP and MP detection methods
have a similar behavior, in the presence of
coding, MP significantly outperforms LP.


Speaker: Sekhar Tatikonda, Yale
Title: Mixing and Clustering in MessagePassing Schemes
The belief propagation algorithm and its variants have recently
been shown to work quite well on hard constraint satisfaction
problems. Survey propagation is one such algorithm that has been
developed for solving the kSAT problem. This algorithm is based
on two hypotheses deriving from the replica symmetry breaking
theory developed for the statistical mechanics of spin glasses.
The first is that the solutions of constraint satisfaction
problems near threshold organize into disjoint clusters. The
second is that within each cluster there is spatial mixing. In
this talk we show that both hypotheses hold for a large class of
constraint satisfaction problems.


Speaker: David Tse, Wireless Foundations & UC Berkeley
Title: Hierarchical Cooperation Achieves Optimal Capacity Scaling in Ad Hoc Networks
n source and destination pairs randomly located in an area want to
communicate with each other. Signals transmitted from one user to
another at distance r apart is subject to a power attenuation of
r^{\alpha} as well as a random phase. We identify exactly the scaling laws
of the information theoretic capacity of the network. In the case of
dense networks, where the
area is fixed and the density of nodes increasing, we show that the
total capacity of the network scales linearly with n. In the
case of extended networks, where the density of nodes is fixed and
the area increasing linearly with n, we show that the sum capacity
scales as n^{2\alpha/2} for \alpha <3 and \sqrt{n} for
\alpha > 3. Thus, much better scaling than multihop can be
achieved in dense networks, as well as in extended networks with low
attenuation. The performance gain is achieved by intelligent node
cooperation and distributed MIMO communication. The key ingredient
is a hierarchical and digital architecture for nodal
exchange of information for realizing the cooperation.


Speaker: Ruediger Urbanke, EPFL
Title: How to Compute Scaling Parameters for Sparse
Graph Codes Under MessagePassing Decoding with
a Finite Message Alphabet
Most new standards in communications contain iteratively
decoded sparse graph codes to accomplish the error correction.
To date there is a bewildering (and daily growing) list of candidate
codes and an equally large list of decoders to choose from. How do
we pick a good code from this list?
For transmission over the binary erasure channel a scaling approach
is known to lead to very good predictions on the error probability of
codes
for already moderate blocklengths. Such a scaling approach can therefore
lead to efficient optimization techniques and can help in finding the
best candidates.
I will first discuss how to extend the scaling idea to general channels
and general messagepassing decoders with a finite message
alphabet. This approach can be used in principle for any size
of the message alphabet but its computational complexity
grows like the sixth power. I will then briefly survey the steps that
remain to be
accomplished to convert this idea into a practical and efficient
optimization tool.
[This is joint work with J. Ezri, EPFL, and A. Montanari, Stanford.]


Speaker: Martin Wainwright, UC Berkeley
Title: Probabilistic Analysis of LP Decoding
We describe some recent results on the probabilistic analysis of
linear programming (LP) decoding of lowdensity paritycheck (LDPC) codes.
Specifically, we show that for a random LDPC code ensemble, the linear
programming decoder of Feldman et al. succeeds in correcting a constant
fraction of errors with high probability. The fraction of correctable
errors guaranteed by our analysis surpasses all prior nonasymptotic
results for LDPC codes, and in particular exceeds the best previous
finitelength result on LP decoding by a factor greater than ten. This
improvement stems in part from our analysis of probabilistic bitflipping
channels, as opposed to adversarial channels. At the core of our analysis
is a novel combinatorial characterization of LP decoding success, based on
the notion of a generalized matching. An interesting byproduct of our
analysis is to establish the existence of ``almost expansion'' in random
bipartite graphs, in which one requires only that almost every (as opposed
to every) set of a certain size expands, with expansion coefficients
larger than the classical worstcase setting.


Speaker: Yair Weiss, HU Jerusalem
Title: Linear Programming and Belief Propagation  Theory and Experiments
I will briefly survey the surprising connection between maxproduct belief
propagation and linear programming relaxations. In particular, I will show that this
connection holds for a large number of belief propagation variants.
I will then show how we have used this connection to solve hard problems in computer
vision and computational biology.


Speaker: Dror Weitz, TelAviv
Title: Counting independent sets up to the tree threshold
We present an exact tree representation for the marginal distribution at a vertex in binaryspin systems on general graphs.
Our tree consists of the tree of selfavoiding walks starting at the relevant vertex together with an appropriate boundary condition imposed on a subset of the leaves.
This novel representation allows us to identify the regular tree as the worstcase graph (among graphs with the same maximum degree)
for Strong Spatial Mixing (a certain notion for decay of correlations with distance in the stationary distribution).
In addition, if the spin system on the regular tree of degree D exhibits SSM (Strong Spatial Mixing), then using our tree representation
we obtain a simple deterministic fullypolynomial approximation scheme for calculating the partition function of the spin system on all graphs of maximum degree D.
Applying the above to the hardcore gas model (independent
sets) with activity \lambda, and by establishing that this model on the regular tree of degree D exhibits SSM all the way up to the critical activity
for uniqueness of the Gibbs measure (denoted \\lambda_c (D) ), we obtain the following two results:
a) For all graphs $G$ of maximum degree D and for all \lambda < \lambda_c (D), the Gibbs measure of the hardcore model on G with activity \lambda is unique.
This proves a conjecture posed by Alan Sokal, and extends the proven regime of uniqueness for many interesting graphs, including the square integer lattice Z^2.
b) For any fixed D and for all \lambda < \lambda_c (D) there is a fully polynomial approximation scheme for the partition function of the hardcore model
with activity \lambda on any graph of maximum degree D. This extends the regime of \lambda (as a function of D) for which an efficient approximation scheme is known to exist, and includes the interesting case of \\lambda=1 (all independent sets are equally weighted) and maximum degree D=5.
If time permits, I will also mention some recent evidence suggesting that \lambda_c(D) is in fact the threshold for the algorithmic problem as well
(i.e., that the latter bound for efficient approximation is tight).


Speaker: Jonathan Yedidia, Mitsubishi Research
Title: Multicellular Logic Circuits
I present a simple model of the underlying logic of multicellular organisms, and exploit the model to design multicellular logic circuits.
In this model, an organism or circuit consists of a set of cells containing identical logic units. The logic units compute an output signal
that is a fixed function of their input signals. Three kinds of signals are used: "factor" signals which target logic units in the same cell,
"intercellular" signals which target logic units in neighboring cells, and "developmental" signals which either trigger developmental events
like cell division, or are used to mark the results of developmental events.
In the model, a logic circuit is always initialized as a single cell, and undergoes a developmental phase (to be simulated in software)
until it reaches a fixed "adult" configuration, which can be implemented in hardware.
The adult logic circuit consists of many identical cells, differing only in their history and neighbors, and should compute a desired
input output function. I give an example of the overall design strategy by presenting a multicellular logic circuit for a randomaccess memory.


