University of Cambridge



Matthew Anderson

Research Associate

Picture of
		                                    Matthew Anderson

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:

  1. 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.
    Context Abstract Paper Talk

  2. 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.
    Context Abstract Paper Talk

    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.


  3. 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.
    Context Abstract Paper Talk Bibtex
    @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}
    }	

  4. 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.
    Context Abstract Paper Bibtex

    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}
    }	

  5. 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.)
    Context Abstract Paper Talk Bibtex

    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}
    }	

  6. 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.
    Context Abstract Paper Talk Poster Bibtex

    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:

  1. On Symmetric Circuits and Fixed-Point Logics.

    M. Anderson, and A. Dawar.
    arXiv preprint 1401.1125. 22 pages, 2014.
    Context Abstract Paper

  2. 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.
    Context Abstract Paper

Works in Progress:

  1. Lower Bounds for Symmetric Circuits.

    M. Anderson.

  2. Tensor Rank Lower Bounds via Error-Correcting Codes.

    M. Anderson.
    Context

    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 nd/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.


  3. Analysis of Nondeterministic Pass Machines.

    M. Anderson.

Theses:

  1. Advancing Algebraic and Logical Approaches to Circuit Lower Bounds.

    M. Anderson.
    University of Wisconsin-Madison Ph.D. Thesis, 2012.

  2. QCNMR: Simulation of a Nuclear Magnetic Resonance Quantum Computer.

    M. Anderson.
    Carnegie Mellon University Senior Honors Thesis, 2004.