Computer Laboratory
Matthew Anderson
+ Home
+ Contact Info
+ CV
+ Research
+ Teaching


Matthew Anderson
Research Associate


Research Summary:
I am a complexity theorist—attempting to classify problems according to their resource requirements
such as time and space. At the heart of complexity lies the Quest to show that certain computational
problems inherently require a lot of resources to solve. The centrality and notorious difficulty of this
task has spawned a number of competing computational perspectives. Chief among them are Circuit
Complexity and Descriptive Complexity.
I have embarked on an extended methodical exploration of Circuit Complexity and
Descriptive Complexity with the aim of exploiting synergies between the
individual domains to advance the Quest. The list of publications below detail my exploration to date (8 Jan, 2014).
Publications:

On Symmetric Circuits and FixedPoint Logics.
M. Anderson, and A. Dawar.
In Proceedings of the 31st International Symposium on Theoretical
Aspects of Computer Science (STACS), to appear, 2014.
Any circuit family deciding a graph property must compute a value that is
invariant to any permutation of the graph's vertices. On the other hand, when a
graph property is expressed in a logic, it gives rise to a family of circuits
that are symmetric, i.e., their invariance is witnessed by automorphisms of
the circuit—a bijection from the circuit to itself that maps the inputs
according to the permutation of vertices and maps gates in a way that preserves
operations and wires. This begs the question:
Are invariant circuits are more powerful than symmetric circuits?
This question and related notions of symmetry were considered for constantdepth
circuits and infinite circuits, but not in the domain closest to P.
Our Results. We show that the graph properties computable by uniform
symmetric polynomialsize circuits with majority gates correspond to those
expressible by formulae of fixedpoint logic with counting. By noting that the inexpressibility result of
Cai, Furer, and Immerman implies that
graph properties computable by uniform polynomialsize circuits cannot be
captured by such a logic, we conclude that in this domain symmetric circuits are
strictly weaker than invariant circuits. In essence, we prove a lower bound by
establishing a correspondence between a circuit class and a logic, and then
translating an inexpressibility result through this correspondence.
Transforming symmetric circuits into logical formulae is the challenging
direction of our result and is accomplished, in part, by establishing an
algebraic structural property of symmetric circuits, which may be of independent
interest.
We study queries of relational structures defined by families of Boolean
circuits that are invariant to permutations of their inputs. In particular, we
study circuits that are symmetric, i.e., circuits whose invariance is witnessed
by automorphisms of the circuit induced by the permutation of their inputs. We
show that the queries defined on structures by uniform families of symmetric
Boolean circuits with majority gates are exactly those definable in fixedpoint
logic with counting.

Deterministic Polynomial Identity Tests for Multilinear BoundedRead
Formulae.
M. Anderson, D. van Melkebeek, and I. Volkovich.
Computational Complexity, accepted, in revision, 53 pages, 2013.
Polynomial identity testing is the fundamental problem of deciding
whether a given multivariate polynomial is identically zero, that is,
whether all monomial coefficients vanish. A simple and efficient
randomized identity test results from the following wellknown fact:
Evaluating a polynomial at a random point indicates, with high
probability, whether the polynomial is identically zero. Despite much
work over the course of thirty years no efficient deterministic
algorithm is known when the polynomial is given as an arithmetic
formula (i.e., a formula consisting of addition and multiplication
gates, variables, and constants).
Is there an efficient deterministic identity test
for arithmetic formulae?
The motivation for studying this question is threefold. The first,
and for me most important, reason is that identity testing is
fundamental to our understanding of circuit lower bounds: Efficiently
derandomizing identity testing implies elusive circuit lower
bounds. In fact, an efficient deterministic identity test for
depthfour arithmetic formulae implies a lower bound for general
arithmetic circuits. Second, identity testing is a natural candidate
problem to derandomize; arguably, it is the next natural candidate as
the previous candidate, primality testing, was recently derandomized
using a particular identity test. Finally, identity testing is
frequently used as a tool in theory of computing (e.g., in algorithms
for finding perfect matchings, and in the proof of the PCP theorem);
as such, derandomization could lead to new applications.
The powerful connections with circuit lower bounds have energized much
recent effort towards derandomizing identity testing, particularly for
restricted circuit models. A significant line of research focuses on
boundeddepth formulae. We study a different direction, namely one
which allows arbitrary depth, but requires that the number of times a
variable is accessed be bounded.
Our Results. We succeed in derandomizing
polynomial identity testing for the model of multilinear constantread
arithmetic formulae, that is, formulae where each variable may be
accessed only a constant number of times and each gate computes a
polynomial which has degree at most one in each individual
variable. For this class of formulae we give a polynomialtime
identity test. In addition, we are able to expand the model and our
identity test to encompass, unify and extend several (seemingly
different) recent works, both in the realm of boundedread and
boundeddepth identity testing. In a further extension, we give a
blackbox identity test for this class of formulae that runs
in n^{O(log n)} time. Blackbox
tests are more robust in that they only evaluate the formula and do
not access the representation of the formula. Our work has already
spurred further improvements in identity tests for the special case of
constantdepth formulae over large fields.
We present a polynomialtime deterministic algorithm for testing
whether constantread multilinear arithmetic formulae are identically
zero. In such a formula each variable occurs only a constant number of
times and each subformula computes a multilinear polynomial.
Our algorithm runs in time s^{O(1)}⋅ n^{
k O(k)}, where s denotes the size of the
formula, n denotes the number of variables, and k bounds
the number of occurrences of each variable. Before our work no
subexponentialtime deterministic algorithm was known for this class
of formulae. We also present a deterministic algorithm that works in
a blackbox fashion and runs in time n^{kO(k) + O(k
log n)} in general, and time n^{ k O(k2) + O(kD)} for depth D.
Finally, we extend our results and allow the inputs to be replaced
with sparse polynomials. Our results encompass recent deterministic
identity tests for sums of a constant number of readonce formulae,
and for multilinear depthfour formulae.

Maximum Matching and Linear Programming in FixedPoint Logic with
Counting.
M. Anderson, A. Dawar, and B. Holm.
In Proceedings of the 28th Annual ACM/IEEE Symposium on Logic in
Computer Science (LICS), pages 173182, 2013.
A central enigma of Descriptive Complexity for the past thirty years has been
whether the semantic invariance of graph properties can be captured by the
syntax of logic. This question is of particular interest for properties in the
complexity class P, i.e., all languages that can be decided in deterministic
polynomial time, as this would give a logical analog of P.
Is there a logic capturing the graph properties computable in P?
At one point it was conjectured that FPC, i.e., the extension of firstorder
logic with a least fixedpoint operator and the ability to count the size of
expressible sets, sufficed to express all graph properties in P. This
conjecture was refuted by Cai, Furer, and Immerman. Since then a number of logics have been proposed
with greater expressive power, yet still contained in P and not known to be
distinct. One class of contenders introduced by Blass, Gurevich, and Shelah are
the extensions of ChoicelessP,
informally, a logic designed to capture as much of P as possible but prohibiting
the ability to make arbitrary algorithmic choices (a concrete example of such an
algorithmic choice is the selection of pivot when computing matrix rank via
Gaussian elimination). It was conjectured in that the problem of deciding
whether a graph has a perfect matching, i.e., there is a set of vertexdisjoint
edges incident to all vertices, is "unlikely" to be expressible in an extension
of ChoicelessP.
Our Results. We refute this conjecture by showing
that perfect matching, indeed the size of a maximum matching, can be determined
even in FPC. In the process of establishing this result we show, surprisingly,
that a host of fundamental combinatorial and geometric optimization problems can
also be expressed. In particular, we show that the blackbox nature of
Khachiyan's Ellipsoid Method for linear programming can be exploited to solve
linear programming problems within this logic. Our main result follows by
combining this with an analysis of canonical solutions to the classical maxflow
and mincut problems, and Padberg and Rao's framework for solving the maximum matching problem
via linear programming. In essence, we show many interesting
graph properties in P can be nontrivially captured by FPC.
We establish the expressibility in fixedpoint logic with counting (FPC)
of a number of natural polynomialtime problems. In particular, we show
that the size of a maximum matching in a graph is definable in FPC. This
settles an open problem first posed by Blass, Gurevich and Shelah, who
asked whether the existence of perfect matchings in general graphs could
be determined in the more powerful formalism of choice less polynomial
time with counting. Our result is established by noting that the
ellipsoid method for solving linear programs of full dimension can be
implemented in FPC. This allows us to prove that linear programs of full
dimension can be optimised in FPC if the corresponding separation oracle
problem can be defined in FPC. On the way to defining a suitable
separation oracle for the maximum matching problem, we provide FPC
formulas defining maximum flows and canonical minimum cuts in
capacitated graphs.
@inproceedings{10.1109/LICS.2013.23,
title={Maximum Matching and Linear Programming in FixedPoint Logic with
Counting},
author={Anderson, Matthew and Dawar, Anuj and Holm, Bjarki},
booktitle={Proceedings of the 28th Annual ACM/IEEE Symposium on Logic in
Computer Science (LICS)},
year={2013},
pages={173182}
}

Locality from Circuit Lower Bounds.
M. Anderson, D. van
Melkebeek, N. Schweikardt, and L. Seguofin.
SIAM Journal on Computing (SICOMP), volume 41, issue 6, pages 14811523, 2012.
Descriptive complexity provides a logicbased perspective on computational
complexity. In this context complexity classes are sets of logical formulae,
and the goal of proving lower bounds becomes showing inexpressibility results,
that is, results stating that a certain logical query is not expressible in a
particular logic.
One potent tool for proving inexpressibility results is the notion of
locality. Informally, a logical query is local if it can be answered
by only looking at small, localized parts of the input. Once a class
of formulae is known to be local, it is often easy to prove a
particular query cannot be expressed in this class by showing that the
query is not local. For example, each firstorder query over graphs
only depends on the neighborhoods of the arguments up to some constant
distance. On the other hand, checking whether two vertices are
connected cannot be done by considering only the neighborhoods up to
any constant distance. These two facts imply that connectivity is not
expressible in firstorder logic. This motivates the following
question:
To what extent are logics local?
Our Results. We show how to use circuit lower bounds to
establish upper bounds on the locality of logics. In particular, we
consider a logic that corresponds to the complexity class
AC^{0}, that is, all languages that can be decided by
nonuniform families of polynomialsize constantdepth circuits. We
exploit the known lower bounds for parity on constantdepth circuits
to obtain a tight upper bound for the locality of queries expressible
in that logic. Informally, our main result shows that inputs that look
the same up to a polylogarithmic distance cannot be distinguished by
a formula from this logic. This provides a simple and generic means of
proving inexpressibility results for this type of formulae, hence
extending the power of the original lower bound to a larger class of
queries. It also gives a simple and general way of showing that many
graph queries cannot be computed in AC^{0}. For example, it
gives a short proof that AC^{0}
cannot determine whether a
vertex is on a cycle, or whether two vertices are connected.
We study the locality of an extension of firstorder logic that
captures graph queries computable in AC^{0}, i.e., by families
of polynomialsize constantdepth circuits. The extension considers
firstorder formulas over relational structures which may use
arbitrary numerical predicates in such a way that their truth value is
independent of the particular interpretation of the numerical
predicates. We refer to such formulas as Arbinvariant
firstorder.
We consider the two standard notions of locality, Gaifman and Hanf
locality. Our main result gives a Gaifman locality theorem: An
Arbinvariant firstorder formula cannot distinguish between two
tuples that have the same neighborhood up to distance
(log n)^{c}, where n represents the number of
elements in the structure and c is a constant depending on the
formula. When restricting attention to string structures, we achieve
the same quantitative strength for Hanf locality. In both cases we
show that our bounds are tight. We also present an application of our
results to the study of regular languages. Our proof exploits the
close connection between firstorder formulas and the complexity class
AC^{0}, and hinges on the tight lower bounds for parity on
constantdepth circuits.
@article{doi:10.1137/110856873,
title={Locality from Circuit Lower Bounds},
author={Anderson, Matthew and van Melkebeek, Dieter and
Schweikardt, Nicole and Segoufin, Luc},
journal={SIAM Journal on Computing},
volume={41},
number={6},
pages={14811523},
doi={10.1137/110856873}
}

Locality of Queries Definable in Invariant FirstOrder Logic with
Arbitrary Builtin Predicates.
M. Anderson, D. van Melkebeek, N. Schweikardt, and L. Segoufin.
In Proceedings of the 38th International Colloquium on Automata,
Languages and Programming (ICALP), Part II, pages 368379,
2011. (Invited to the special issue.)
Descriptive complexity provides a logicbased perspective on computational
complexity. In this context complexity classes are sets of logical formulae,
and the goal of proving lower bounds becomes showing inexpressibility results,
that is, results stating that a certain logical query is not expressible in a
particular logic.
One potent tool for proving inexpressibility results is the notion of
locality. Informally, a logical query is local if it can be answered
by only looking at small, localized parts of the input. Once a class
of formulae is known to be local, it is often easy to prove a
particular query cannot be expressed in this class by showing that the
query is not local. For example, each firstorder query over graphs
only depends on the neighborhoods of the arguments up to some constant
distance. On the other hand, checking whether two vertices are
connected cannot be done by considering only the neighborhoods up to
any constant distance. These two facts imply that connectivity is not
expressible in firstorder logic. This motivates the following
question:
To what extent are logics local?
Our Results. We show how to use circuit lower bounds to
establish upper bounds on the locality of logics. In particular, we
consider a logic that corresponds to the complexity class
AC^{0}, that is, all languages that can be decided by
nonuniform families of polynomialsize constantdepth circuits. We
exploit the known lower bounds for parity on constantdepth circuits
to obtain a tight upper bound for the locality of queries expressible
in that logic. Informally, our main result shows that inputs that look
the same up to a polylogarithmic distance cannot be distinguished by
a formula from this logic. This provides a simple and generic means of
proving inexpressibility results for this type of formulae, hence
extending the power of the original lower bound to a larger class of
queries. It also gives a simple and general way of showing that many
graph queries cannot be computed in AC^{0}. For example, it
gives a short proof that AC^{0}
cannot determine whether a
vertex is on a cycle, or whether two vertices are connected.
We consider firstorder
formulas over relational structures which may use arbitrary numerical
predicates. We require that the validity of the formula is independent
of the particular interpretation of the numerical predicates and refer
to such formulas as Arbinvariant firstorder.
Our main result shows a
Gaifman locality theorem: two tuples of a structure with n
elements, having the same neighborhood up to distance (log
n)^{ω(1)}, cannot be distinguished by Arbinvariant
firstorder formulas. When restricting attention to word structures,
we can achieve the same quantitative strength for Hanf locality. In
both cases we show that our bounds are tight.
Our proof exploits the
close connection between Arbinvariant firstorder formulas and the
complexity class AC^{0}, and hinges on the tight lower bounds
for parity on constantdepth circuits.
@inproceedings{anderson2011locality,
title={Locality of Queries Definable in Invariant FirstOrder
Logic with Arbitrary Builtin Predicates},
author={Anderson, Matthew and van Melkebeek, Dieter and
Schweikardt, Nicole and Segoufin, Luc},
booktitle={Proceedings of the 38th International Colloquium on
Automata, Languages and Programming (ICALP)},
pages={368379},
year={2011}
}

Derandomizing Polynomial Identity Testing for Multilinear
ConstantRead Formulae.
M. Anderson, D. van Melkebeek and I. Volkovich.
In Proceedings of the 26th Annual IEEE Conference on Computational Complexity (CCC),
pages 273282, 2011.
Polynomial identity testing is the fundamental problem of deciding
whether a given multivariate polynomial is identically zero, that is,
whether all monomial coefficients vanish. A simple and efficient
randomized identity test results from the following wellknown fact:
Evaluating a polynomial at a random point indicates, with high
probability, whether the polynomial is identically zero. Despite much
work over the course of thirty years no efficient deterministic
algorithm is known when the polynomial is given as an arithmetic
formula (i.e., a formula consisting of addition and multiplication
gates, variables, and constants).
Is there an efficient deterministic identity test
for arithmetic formulae?
The motivation for studying this question is threefold. The first,
and for me most important, reason is that identity testing is
fundamental to our understanding of circuit lower bounds: Efficiently
derandomizing identity testing implies elusive circuit lower
bounds. In fact, an efficient deterministic identity test for
depthfour arithmetic formulae implies a lower bound for general
arithmetic circuits. Second, identity testing is a natural candidate
problem to derandomize; arguably, it is the next natural candidate as
the previous candidate, primality testing, was recently derandomized
using a particular identity test. Finally, identity testing is
frequently used as a tool in theory of computing (e.g., in algorithms
for finding perfect matchings, and in the proof of the PCP theorem);
as such, derandomization could lead to new applications.
The powerful connections with circuit lower bounds have energized much
recent effort towards derandomizing identity testing, particularly for
restricted circuit models. A significant line of research focuses on
boundeddepth formulae. We study a different direction, namely one
which allows arbitrary depth, but requires that the number of times a
variable is accessed be bounded.
Our Results. We succeed in derandomizing
polynomial identity testing for the model of multilinear constantread
arithmetic formulae, that is, formulae where each variable may be
accessed only a constant number of times and each gate computes a
polynomial which has degree at most one in each individual
variable. For this class of formulae we give a polynomialtime
identity test. In addition, we are able to expand the model and our
identity test to encompass, unify and extend several (seemingly
different) recent works, both in the realm of boundedread and
boundeddepth identity testing. In a further extension, we give a
blackbox identity test for this class of formulae that runs
in n^{O(log n)} time. Blackbox
tests are more robust in that they only evaluate the formula and do
not access the representation of the formula. Our work has already
spurred further improvements in identity tests for the special case of
constantdepth formulae over large fields.
We present a polynomialtime deterministic algorithm for testing
whether constantread multilinear arithmetic formulae are identically
zero. In such a formula each variable occurs only a constant number of
times and each subformula computes a multilinear polynomial. Before
our work no subexponentialtime deterministic algorithm was known for
this class of formulae. We also present a deterministic algorithm
that works in a blackbox fashion and runs in quasipolynomial time in
general, and polynomial time for constant depth. Finally, we extend
our results and allow the inputs to be replaced with sparse
polynomials. Our results encompass recent deterministic identity tests
for sums of a constant number of readonce formulae, and for
multilinear depthfour circuits.
@inproceedings{anderson2011derandomizing,
title={Derandomizing Polynomial Identity Testing for Multilinear
ConstantRead Formulae},
author={Anderson, Matthew and van Melkebeek, Dieter and
Volkovich, Ilya},
booktitle={Proceedings of the 26th Annual IEEE Conference on
Computational Complexity},
pages={273282},
year={2011}
}
Preprints:

On Symmetric Circuits and FixedPoint Logics.
M. Anderson, and A. Dawar.
arXiv preprint 1401.1125. 22 pages, 2014.
Any circuit family deciding a graph property must compute a value that is
invariant to any permutation of the graph's vertices. On the other hand, when a
graph property is expressed in a logic, it gives rise to a family of circuits
that are symmetric, i.e., their invariance is witnessed by automorphisms of
the circuit—a bijection from the circuit to itself that maps the inputs
according to the permutation of vertices and maps gates in a way that preserves
operations and wires. This begs the question:
Are invariant circuits are more powerful than symmetric circuits?
This question and related notions of symmetry were considered for constantdepth
circuits and infinite circuits, but not in the domain closest to P.
Our Results. We show that the graph properties computable by uniform
symmetric polynomialsize circuits with majority gates correspond to those
expressible by formulae of fixedpoint logic with counting. By noting that the inexpressibility result of
Cai, Furer, and Immerman implies that
graph properties computable by uniform polynomialsize circuits cannot be
captured by such a logic, we conclude that in this domain symmetric circuits are
strictly weaker than invariant circuits. In essence, we prove a lower bound by
establishing a correspondence between a circuit class and a logic, and then
translating an inexpressibility result through this correspondence.
Transforming symmetric circuits into logical formulae is the challenging
direction of our result and is accomplished, in part, by establishing an
algebraic structural property of symmetric circuits, which may be of independent
interest.
We study properties of relational structures such as graphs that are decided by families of Boolean circuits. Circuits that decide such properties are necessarily invariant
to permutations of the elements of the input structures. We focus on families of circuits that are symmetric, i.e., circuits whose invariance is witnessed by automorphisms of the circuit induced by the permutation of the input structure. We show that the expressive power of such families is closely tied to definability in logic. In particular, we
show that the queries defined on structures by uniform families of symmetric Boolean circuits with majority gates are exactly those definable in fixedpoint logic with counting. This shows that inexpressibility results in the latter logic lead to lower bounds against polynomialsize families of symmetric circuits.

Maximum Matching and Linear Programming in FixedPoint Logic with
Counting.
M. Anderson, A. Dawar, and B. Holm
arXiv preprint 1304.6870. 34 pages, 2013.
A central enigma of Descriptive Complexity for the past thirty years has been
whether the semantic invariance of graph properties can be captured by the
syntax of logic. This question is of particular interest for properties in the
complexity class P, i.e., all languages that can be decided in deterministic
polynomial time, as this would give a logical analog of P.
Is there a logic capturing the graph properties computable in P?
At one point it was conjectured that FPC, i.e., the extension of firstorder
logic with a least fixedpoint operator and the ability to count the size of
expressible sets, sufficed to express all graph properties in P. This
conjecture was refuted by Cai, Furer, and Immerman. Since then a number of logics have been proposed
with greater expressive power, yet still contained in P and not known to be
distinct. One class of contenders introduced by Blass, Gurevich, and Shelah are
the extensions of ChoicelessP,
informally, a logic designed to capture as much of P as possible but prohibiting
the ability to make arbitrary algorithmic choices (a concrete example of such an
algorithmic choice is the selection of pivot when computing matrix rank via
Gaussian elimination). It was conjectured in that the problem of deciding
whether a graph has a perfect matching, i.e., there is a set of vertexdisjoint
edges incident to all vertices, is "unlikely" to be expressible in an extension
of ChoicelessP.
Our Results. We refute this conjecture by showing
that perfect matching, indeed the size of a maximum matching, can be determined
even in FPC. In the process of establishing this result we show, surprisingly,
that a host of fundamental combinatorial and geometric optimization problems can
also be expressed. In particular, we show that the blackbox nature of
Khachiyan's Ellipsoid Method for linear programming can be exploited to solve
linear programming problems within this logic. Our main result follows by
combining this with an analysis of canonical solutions to the classical maxflow
and mincut problems, and Padberg and Rao's framework for solving the maximum matching problem
via linear programming. In essence, we show many interesting
graph properties in P can be nontrivially captured by FPC.
We establish the expressibility in fixedpoint logic with counting (FPC)
of a number of natural polynomialtime problems. In particular, we show that the
size of a maximum matching in a graph is definable in FPC. This settles an open
problem first posed by Blass, Gurevich and Shelah, who asked whether the
existence of perfect matchings in general graphs could be determined in the more
powerful formalism of choiceless polynomial time with counting. Our result is
established by showing that the ellipsoid method for solving linear programs can
be implemented in FPC. This allows us to prove that linear programs can be
optimised in FPC if the corresponding separation oracle problem can be defined
in FPC. On the way to defining a suitable separation oracle for the maximum
matching problem, we provide FPC formulas defining maximum flows and canonical
minimum cuts in capacitated graphs.
Works in Progress:

Lower Bounds for Symmetric Circuits.
M. Anderson.

Tensor Rank Lower Bounds via ErrorCorrecting Codes.
M. Anderson.
Another algebraic avenue for proving circuit lower bounds is via the
study of tensor rank. The classical results by Baur and Strassen and a
recent result by Raz suggest such an approach. Namely, if one can
prove a strong enough lower bound on the rank of some explicit tensor,
arithmetic circuit lower bounds follow. This immediately raises the
question:
Is there an explicit tensor with high
rank?
A tensor is a generalization of a matrix to higher dimensions, and
coincides with matrices at dimension two. A simple tensor of dimension
d is the outer product of d vectors. The rank of a tensor is
the minimum number r such that the tensor is a linear combination
of r simple tensors. For dimension two this coincides exactly
with the notion of matrix rank. However, the intuition that matrix
rank provides is limited at best. For dimension three is it known that
computing the rank of a tensor is NPhard. In fact, not much is known
about tensor rank for dimensions higher than two. There is a fairly
simple counting argument that shows (nonexplicit) tensors of rank
n^{d1}/d exist, and a folklore result that says
explicit tensors of rank n^{⌊d/2⌋}
exist. One line of research has established small constant factor
improvements to this folklore result (for the moment this small factor
is 3). I have some preliminary results that indicate this factor can
be strengthened via a novel application of error correcting code
bounds.

Analysis of Nondeterministic Pass
Machines.
M. Anderson.
Theses:

Advancing Algebraic and Logical Approaches to Circuit Lower Bounds.
M. Anderson.
University of WisconsinMadison
Ph.D. Thesis, 2012.

QCNMR: Simulation of a Nuclear Magnetic Resonance Quantum
Computer.
M. Anderson.
Carnegie Mellon University Senior Honors
Thesis, 2004.

