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 Fixed-Point 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 constant-depth
circuits and infinite circuits, but not in the domain closest to P.
Our Results. We show that the graph properties computable by uniform
symmetric polynomial-size circuits with majority gates correspond to those
expressible by formulae of fixed-point logic with counting. By noting that the inexpressibility result of
Cai, Furer, and Immerman implies that
graph properties computable by uniform polynomial-size 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 fixed-point
logic with counting.
-
Deterministic Polynomial Identity Tests for Multilinear Bounded-Read
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 well-known 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 three-fold. 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
depth-four 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
bounded-depth 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 constant-read
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 polynomial-time
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 bounded-read and
bounded-depth identity testing. In a further extension, we give a
black-box identity test for this class of formulae that runs
in nO(log n) time. Black-box
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
constant-depth formulae over large fields.
We present a polynomial-time deterministic algorithm for testing
whether constant-read 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 sO(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
subexponential-time 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 nkO(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 read-once formulae,
and for multilinear depth-four formulae.
-
Maximum Matching and Linear Programming in Fixed-Point 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 173-182, 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 first-order
logic with a least fixed-point 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 Choiceless-P,
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 vertex-disjoint
edges incident to all vertices, is "unlikely" to be expressible in an extension
of Choiceless-P.
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 max-flow
and min-cut 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 fixed-point logic with counting (FPC)
of a number of natural polynomial-time 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 Fixed-Point 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={173-182}
}
-
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 1481-1523, 2012.
Descriptive complexity provides a logic-based 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 first-order 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 first-order 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
AC0, that is, all languages that can be decided by
nonuniform families of polynomial-size constant-depth circuits. We
exploit the known lower bounds for parity on constant-depth 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 poly-logarithmic 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 AC0. For example, it
gives a short proof that AC0
cannot determine whether a
vertex is on a cycle, or whether two vertices are connected.
We study the locality of an extension of first-order logic that
captures graph queries computable in AC0, i.e., by families
of polynomial-size constant-depth circuits. The extension considers
first-order 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 Arb-invariant
first-order.
We consider the two standard notions of locality, Gaifman and Hanf
locality. Our main result gives a Gaifman locality theorem: An
Arb-invariant first-order 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 first-order formulas and the complexity class
AC0, and hinges on the tight lower bounds for parity on
constant-depth 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={1481-1523},
doi={10.1137/110856873}
}
-
Locality of Queries Definable in Invariant First-Order Logic with
Arbitrary Built-in 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 368-379,
2011. (Invited to the special issue.)
Descriptive complexity provides a logic-based 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 first-order 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 first-order 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
AC0, that is, all languages that can be decided by
nonuniform families of polynomial-size constant-depth circuits. We
exploit the known lower bounds for parity on constant-depth 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 poly-logarithmic 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 AC0. For example, it
gives a short proof that AC0
cannot determine whether a
vertex is on a cycle, or whether two vertices are connected.
We consider first-order
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 Arb-invariant first-order.
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 Arb-invariant
first-order 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 Arb-invariant first-order formulas and the
complexity class AC0, and hinges on the tight lower bounds
for parity on constant-depth circuits.
@inproceedings{anderson2011locality,
title={Locality of Queries Definable in Invariant First-Order
Logic with Arbitrary Built-in 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={368-379},
year={2011}
}
-
Derandomizing Polynomial Identity Testing for Multilinear
Constant-Read Formulae.
M. Anderson, D. van Melkebeek and I. Volkovich.
In Proceedings of the 26th Annual IEEE Conference on Computational Complexity (CCC),
pages 273-282, 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 well-known 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 three-fold. 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
depth-four 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
bounded-depth 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 constant-read
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 polynomial-time
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 bounded-read and
bounded-depth identity testing. In a further extension, we give a
black-box identity test for this class of formulae that runs
in nO(log n) time. Black-box
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
constant-depth formulae over large fields.
We present a polynomial-time deterministic algorithm for testing
whether constant-read 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 subexponential-time deterministic algorithm was known for
this class of formulae. We also present a deterministic algorithm
that works in a blackbox fashion and runs in quasi-polynomial 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 read-once formulae, and for
multilinear depth-four circuits.
@inproceedings{anderson2011derandomizing,
title={Derandomizing Polynomial Identity Testing for Multilinear
Constant-Read Formulae},
author={Anderson, Matthew and van Melkebeek, Dieter and
Volkovich, Ilya},
booktitle={Proceedings of the 26th Annual IEEE Conference on
Computational Complexity},
pages={273-282},
year={2011}
}
Preprints:
-
On Symmetric Circuits and Fixed-Point 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 constant-depth
circuits and infinite circuits, but not in the domain closest to P.
Our Results. We show that the graph properties computable by uniform
symmetric polynomial-size circuits with majority gates correspond to those
expressible by formulae of fixed-point logic with counting. By noting that the inexpressibility result of
Cai, Furer, and Immerman implies that
graph properties computable by uniform polynomial-size 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 fixed-point logic with counting. This shows that inexpressibility results in the latter logic lead to lower bounds against polynomial-size families of symmetric circuits.
-
Maximum Matching and Linear Programming in Fixed-Point 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 first-order
logic with a least fixed-point 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 Choiceless-P,
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 vertex-disjoint
edges incident to all vertices, is "unlikely" to be expressible in an extension
of Choiceless-P.
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 max-flow
and min-cut 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 fixed-point logic with counting (FPC)
of a number of natural polynomial-time 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 Error-Correcting 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 NP-hard. In fact, not much is known
about tensor rank for dimensions higher than two. There is a fairly
simple counting argument that shows (non-explicit) tensors of rank
nd-1/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 Wisconsin-Madison
Ph.D. Thesis, 2012.
-
QCNMR: Simulation of a Nuclear Magnetic Resonance Quantum
Computer.
M. Anderson.
Carnegie Mellon University Senior Honors
Thesis, 2004.
|
|