6 citations · 9 across the 4 of their papers we have counts for
Showing 2016 · cs.CCShow all
2 papers · 2 filters
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.CC2016
Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation
Ryan Williams
We present an efficient proof system for Multipoint Arithmetic Circuit Evaluation: for every arithmetic circuit of size and degree over a field ${\mathb…