1 citations · 3 across the 4 of their papers we have counts for
5 papers
Efficiently-Verifiable Strong Uniquely Solvable Puzzles and Matrix Multiplication
Matthew Anderson, Vu Le
We advance the Cohn-Umans framework for developing fast matrix multiplication algorithms. We introduce, analyze, and search for a new subclass of strong uniquely solvable puzzles (…
Matrix Multiplication: Verifying Strong Uniquely Solvable Puzzles
Matthew Anderson, Zongliang Ji, Anthony Yang Xu
Cohn and Umans proposed a framework for developing fast matrix multiplication algorithms based on the embedding computation in certain groups algebras. In subsequent work with Klei…
Identity Testing and Lower Bounds for Read- Oblivious Algebraic Branching Programs
Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi +2
Read- 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…
On Symmetric Circuits and Fixed-Point Logics
Matthew Anderson, Anuj Dawar
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 perm…
Maximum Matching and Linear Programming in Fixed-Point Logic with Counting
Matthew Anderson, Anuj Dawar, Bjarki Holm
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…