1 citations · 1 across the 4 of their papers we have counts for
6 papers
On the computational equivalence of co-NP refutations of a matrix being a P-matrix
Spencer Gordon, Kevin Shu
A P-matrix is a square matrix such that all principal submatrices of have positive determinant. Such matrices appear naturally in instances of the linear complementarity pr…
Hadamard Extensions and the Identification of Mixtures of Product Distributions
Spencer L. Gordon, Leonard J. Schulman
The Hadamard Extension of a matrix is the matrix consisting of all Hadamard products of subsets of its rows. This construction arises in the context of identifying a mixture of pro…
Source Identification for Mixtures of Product Distributions
Spencer L. Gordon, Bijan Mazaheri, Yuval Rabani +1
We give an algorithm for source identification of a mixture of product distributions on bits. This is a fundamental problem in machine learning with many applications. Our…
The Sparse Hausdorff Moment Problem, with Application to Topic Models
Spencer Gordon, Bijan Mazaheri, Leonard J. Schulman +1
We consider the problem of identifying, from its first noisy moments, a probability distribution on of support . This is equivalent to the problem of learning…
Unique End of Potential Line
John Fearnley, Spencer Gordon, Ruta Mehta +1
This paper studies the complexity of problems in PPAD PLS that have unique solutions. Three well-known examples of such problems are the problem of finding a fixpoint of a c…
End of Potential Line
John Fearnley, Spencer Gordon, Ruta Mehta +1
We introduce the problem EndOfPotentialLine and the corresponding complexity class EOPL of all problems that can be reduced to it in polynomial time. This class captures problems t…