Computer Science
Matthew Anderson
+ Home
+ Contact Info
+ CV
+ Research
+ Teaching
|
|
Matthew Anderson
Associate Professor |
 |
Undergraduate Projects
Below are several active projects that students at
Union can participate in. Send me an email or stop by
my office if you want to talk about participating on
these or other projects. I typically work with a
couple of students in practicums during term and over
the summer through the
Summer
Research Fellows program.
- Matrix Multiplication. Design
algorithms and implement software to search for more
efficient algorithms for matrix multiplication.
Past work involved developing parallel software for
Union's supercomputer. Depending on student
background the project can involve application of
modern algebra topics like group and field theory.
Knowledge of C/C++ and algorithm design are helpful,
but not necessary.
- Virtual Reality Robot Control. We are
developing a system using consumer-grade VR hardware
to control and visualize the world as a robot
traverses a new environment using visual SLAM
(simultaneous localization and mapping) algorithms.
Knowledge of ROS (Robot Operating System), and Unity
are helpful, but not necessary.
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 (Nov 29, 2018).
Publications
-
Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs.
M. Anderson, M. A. Forbes, R. Saptharishi, A. Shpilka, and B.L. Volk.
ACM Transactions on Computation Theory (TOCT), volume 10, issue 1, pages 3:1-28, 2018.
Read-k oblivious algebraic
branching programs are a natural
generalization of the well-studied model of
read-once oblivious algebraic branching
program (ROABPs). In this work, we give an
exponential lower bound of
exp(n/kO(k)) on the
width of any read-k oblivious ABP
computing some explicit multilinear
polynomial f that is computed by a
polynomial size depth-3 circuit. We also
study the polynomial identity testing (PIT)
problem for this model and obtain a
white-box subexponential-time PIT
algorithm. The algorithm runs in time
2O(n1-1/2k-1)
and needs white box access only to know the
order in which the variables appear in the
ABP.
@article{afssv18,
author = {Anderson, Matthew and Forbes, Michael A. and
Saptharishi, Ramprasad and Shpilka, Amir and Volk, Ben Lee},
title = {Identity Testing and Lower Bounds for Read-k
Oblivious Algebraic Branching Programs},
journal = {ACM Trans. Comput. Theory},
issue_date = {January 2018},
volume = {10},
number = {1},
month = jan,
year = {2018},
issn = {1942-3454},
pages = {3:1--3:30},
articleno = {3},
numpages = {30},
url = {http://doi.acm.org/10.1145/3170709},
doi = {10.1145/3170709},
acmid = {3170709},
publisher = {ACM},
address = {New York, NY, USA},
keywords = {Algebraic complexity theory, algebraic circuits,
lower bounds, polynomial identity testing},
}
-
On Symmetric Circuits and Fixed-Point Logics.
M. Anderson, and A. Dawar.
Theory of Computing Systems (TOCS), volume 60, issue 3, pages 521-551, 2017.
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.
article{ad17,
author = {Anderson, Matthew and Dawar, Anuj},
title = {On Symmetric Circuits and Fixed-Point Logics},
journal = {Theor. Comp. Sys.},
issue_date = {April 2017},
volume = {60},
number = {3},
month = apr,
year = {2017},
issn = {1432-4350},
pages = {521--551},
numpages = {31},
url = {https://doi.org/10.1007/s00224-016-9692-2},
doi = {10.1007/s00224-016-9692-2},
acmid = {3075528},
publisher = {Springer-Verlag New York, Inc.},
address = {Secaucus, NJ, USA},
keywords = {Counting, Fixed-point logic, Majority,
Symmetric circuit, Uniformity},
}
-
Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs.
M. Anderson, M. A. Forbes, R. Saptharishi, A. Shpilka, and B.L. Volk.
In Proceedings of the 31st Annual IEEE
Conference on Computational Complexity (CCC),
pages 30:1-30:25, 2016.
Read-k oblivious algebraic
branching programs are a natural
generalization of the well-studied model of
read-once oblivious algebraic branching
program (ROABPs). In this work, we give an
exponential lower bound of
exp(n/kO(k)) on the
width of any read-k oblivious ABP
computing some explicit multilinear
polynomial f that is computed by a
polynomial size depth-3 circuit. We also
study the polynomial identity testing (PIT)
problem for this model and obtain a
white-box subexponential-time PIT
algorithm. The algorithm runs in time
2O(n1-1/2k-1)
and needs white box access only to know the
order in which the variables appear in the
ABP.
@inproceedings{afssv16,
author = {Matthew Anderson and
Michael A. Forbes and
Ramprasad Saptharishi and
Amir Shpilka and
Ben Lee Volk},
title = {Identity Testing and Lower Bounds for Read-k
Oblivious Algebraic Branching Programs},
booktitle = {31st Conference on Computational Complexity,
{CCC} 2016, May 29 to June 1, 2016, Tokyo, Japan},
pages = {30:1--30:25},
year = {2016},
url = {https://doi.org/10.4230/LIPIcs.CCC.2016.30},
doi = {10.4230/LIPIcs.CCC.2016.30}
}
-
A Parallel Approach in Computing Correlation Immunity up to Six Variables.
C. Etherington, M. Anderson, E. Bach, J. Butler, and P. Stanica.
International Journal of Foundations of Computer Science
(IJFCS), volume 27, issue 4, pages 511-528, 2016
We show the use of a reconfigurable computer
in computing the correlation immunity of
Boolean functions of up to 6
variables. Boolean functions with high
correlation immunity (in addition to other
cryptographic properties) are desired in
cryptographic systems because they are
immune to correlation attacks. The SRC-6
reconfigurable computer was programmed in
Verilog to compute the correlation immunity
of functions. This computation is performed
at a rate that is 190 times faster than a
conventional computer. Our analysis of the
correlation immunity is across all
n-variable Boolean functions, for 1 < n < 7,
thus obtaining, for the first time, a
complete distribution of such functions. We
also compare correlation immunity with two
other cryptographic properties, nonlinearity
and degree.
@article{eabbs16,
author = {Carole J. Etherington and
Matthew W. Anderson and
Eric Bach and
Jon T. Butler and
Pantelimon Stanica},
title = {A Parallel Approach in Computing Correlation
Immunity up to Six Variables},
journal = {Int. J. Found. Comput. Sci.},
volume = {27},
number = {4},
pages = {511},
year = {2016},
url = {https://doi.org/10.1142/S0129054116500131},
doi = {10.1142/S0129054116500131}
}
-
Solving Linear Programs without Breaking Abstractions.
M. Anderson, A. Dawar, and B. Holm.
Journal of the ACM (JACM), volume 62, issue 6, pages 48:1-48:26, 2015.
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 show that the ellipsoid method for
solving linear programs can be implemented
in a way that respects the symmetry of the
program being solved. That is to say, there
is an algorithmic implementation of the
method that does not distinguish, or make
choices, between variables or constraints in
the program unless they are distinguished by
properties definable from the program. In
particular, we demonstrate that the
solvability of linear programs can be
expressed in fixed-point logic with counting
(FPC) as long as the program is given by a
separation oracle that is itself definable
in FPC. We use this to 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 [Blass
et al. 1999]. On the way to defining a
suitable separation oracle for the maximum
matching program, we provide FPC formulas
defining canonical maximum flows and minimum
cuts in undirected capacitated graphs.
@article{10.1145/2822890,
title={Solving Linear Programs without Breaking Abstractions},
author={Anderson, Matthew and Dawar, Anuj and Holm, Bjarki},
journal={Journal of the ACM},
volume={42},
number={6},
year={2015},
pages={48:1--48:26},
doi={10.1145/2822890}
}
-
Deterministic Polynomial Identity Tests for Multilinear Bounded-Read
Formulae.
M. Anderson, D. van Melkebeek, and I. Volkovich.
Computational Complexity, volume 24, issue 4, pages 695-776, 2015.
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.
@article{10.1007/s00037-015-0097-4,
year={2015},
journal={Computational Complexity},
volume={24},
number={4},
doi={10.1007/s00037-015-0097-4},
title={Deterministic polynomial identity tests for
multilinear bounded-read formulae},
author={Anderson, Matthew and van Melkebeek, Dieter and Volkovich, Ilya},
pages={695--776},
}
-
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), pages 41-52, 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.
@InProceedings{anderson_et_al:LIPIcs:2014:4445,
author ={Matthew Anderson and Anuj Dawar},
title ={On Symmetric Circuits and Fixed-Point Logics},
booktitle ={31st International Symposium on Theoretical Aspects
of Computer Science (STACS 2014)},
pages ={41--52},
year ={2014},
volume ={25},
doi ={http://dx.doi.org/10.4230/LIPIcs.STACS.2014.41},
}
-
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},
year={2012},
doi={10.1137/110856873}
}
-
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
qbounds. 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}
}
-
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}
}
Work in Preparation
-
Matrix Multiplication: Verifying Strong Uniquely-Solvable Puzzles.
M. Anderson, Z. Ji, and A. Yang. 20 pages.
-
Lower Bounds for Symmetric Circuits.
M. Anderson. 5 pages.
Work in Progress
-
Matrix Multiplication: Searching for Strong Uniquely-Solvable Puzzles.
M. Anderson and J. Kimber.
-
A Virtual Reality Interface for Robot Control.
M. Anderson and I. Scilipoti.
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.
|
|
