placeholder image

Matthew Anderson

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

Areas of interest

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

Publications

Publications

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

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

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

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

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

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

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

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

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

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

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

Work in Preparation

  1. Matrix Multiplication: Verifying Strong Uniquely-Solvable Puzzles.

    M. Anderson, Z. Ji, and A. Yang. 20 pages.

  2. Lower Bounds for Symmetric Circuits.

    M. Anderson. 5 pages.


  3.  

Work in Progress

  1. Matrix Multiplication: Searching for Strong Uniquely-Solvable Puzzles.

    M. Anderson and J. Kimber.

  2. A Virtual Reality Interface for Robot Control.

    M. Anderson and I. Scilipoti.


  3.  

Theses

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

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

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

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

Academic Credentials

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