Place holder headshot when no photo is available

Matthew Anderson

Job Title
Visiting Assistant Professor of Computer Science
Steinmetz Hall 231
Department/Program: Computer Science

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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.)

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.

Additional media

Areas of interest

Theory of computing; computational complexity; algorithms; logic; derandomization

Academic credentials

B.S., Carnegie Mellon University; M.S., University of Wisconsin-Madison; Ph.D., University of Wisconsin-Madison