Matthew Anderson

Research Associate

Research Summary:

I work in theory of computing and attempt to understand the relative power of computational resources. In particular, I study Boolean and arithmetic circuits as models of computation.

My long-term research goal is to prove circuit lower bounds. My approach consists of investigating related algebraic and logical questions. On the algebraic front, I search for an efficient deterministic algorithm for polynomial identity testing, as the existence of such an algorithm implies long-sought circuit lower bounds. Towards this end, I gave an efficient deterministic identity test that encompasses and significantly extends several prior works. On the logical front, I explored the notion of locality, a potential means of separating low-complexity circuit classes.

Publications:

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 Talk 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 are 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⁰, 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 AC⁰. For example, it gives a short proof that AC⁰ 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 AC⁰, 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.
Context Abstract Talk Poster Paper 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 n^{O(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}
}  
```

Under Submission:

Locality from Circuit Lower Bounds.
M. Anderson, D. van Melkebeek, N. Schweikardt, and L. Segoufin.
Submitted to the SIAM Journal on Computing, 48 pages, 2011. (To be accepted.)

Abstract Paper

We study the locality of an extension of first-order logic that captures graph queries computable in AC⁰, 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 AC⁰, and hinges on the tight lower bounds for parity on constant-depth circuits.

Deterministic Polynomial Identity Tests for Multilinear Bounded-Read Formulae.
M. Anderson. D. van Melkebeek and I. Volkovich.
Submitted to the SIAM Journal on Computing, 54 pages, 2011.

Abstract Talk Paper

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 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 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 n^{k^O(k) + O(k
log n)} in general, and time n^{k ^O(k²) + 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.

Works in Progress:

Tensor Rank Lower Bounds from Error-Correcting Code Bounds.
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 n^d-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.

Compressibility and the Oracle Derandomization Hypothesis.
M. Anderson.

Sets that Realize Lines.
M. Anderson.

Theses:

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

Paper

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

Paper

Matthew Anderson

Research Associate

Research Summary:

Publications:

Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates.

Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae.

Under Submission:

Locality from Circuit Lower Bounds.

Deterministic Polynomial Identity Tests for Multilinear Bounded-Read Formulae.

Works in Progress:

Tensor Rank Lower Bounds from Error-Correcting Code Bounds.

Analysis of Nondeterministic Pass Machines.

Compressibility and the Oracle Derandomization Hypothesis.

Sets that Realize Lines.

Theses:

Advancing Algebraic and Logical Approaches to Circuit Lower Bounds.

QCNMR: Simulation of a Nuclear Magnetic Resonance Quantum Computer.