1 citations · 1 across the 8 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2018
Spanoids - an abstraction of spanning structures, and a barrier for LCCs
Zeev Dvir, Sivakanth Gopi, Yuzhou Gu +1
We introduce a simple logical inference structure we call a (generalizing the notion of a matroid), which captures well-studied problems in several areas. These…
cs.CC2017
Matrix rigidity and the Croot-Lev-Pach lemma
Zeev Dvir, Benjamin Edelman
Matrix rigidity is a notion put forth by Valiant as a means for proving arithmetic circuit lower bounds. A matrix is rigid if it is far, in Hamming distance, from any low rank matr…