4 citations · 10 across the 14 of their papers we have counts for
Showing 2017Show all
2 papers · 1 filter
cs.CC2017
Distributed PCP Theorems for Hardness of Approximation in P
Amir Abboud, Aviad Rubinstein, Ryan Williams
We present a new distributed model of probabilistically checkable proofs (PCP). A satisfying assignment to a CNF formula is shared between two parties, where…
cs.CC2017
Inapproximability of VC Dimension and Littlestone's Dimension
Pasin Manurangsi, Aviad Rubinstein
We study the complexity of computing the VC Dimension and Littlestone's Dimension. Given an explicit description of a finite universe and a concept class (a binary matrix whose $(x…