93 citations · 174 across the 42 of their papers we have counts for
Showing 2016Show all
2 papers · 1 filter
cs.CC2016★ 1 cited
Probabilistic Rank and Matrix Rigidity
Josh Alman, Ryan Williams
We consider a notion of probabilistic rank and probabilistic sign-rank of a matrix, which measures the extent to which a matrix can be probabilistically represented by low-rank mat…
cs.DS2016
Polynomial Representations of Threshold Functions and Algorithmic Applications
Josh Alman, Timothy M. Chan, Ryan Williams
We design new polynomials for representing threshold functions in three different regimes: probabilistic polynomials of low degree, which need far less randomness than previous con…