6 citations · 9 across the 4 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2019
Hard properties with (very) short PCPPs and their applications
Omri Ben-Eliezer, Eldar Fischer, Amit Levi +1
We show that there exist properties that are maximally hard for testing, while still admitting PCPPs with a proof size very close to linear. Specifically, for every fixed , w…
cs.CC2018
Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs
Amit Levi, Erik Waingarten
We introduce a new model for testing graph properties which we call the \emph{rejection sampling model}. We show that testing bipartiteness of -nodes graphs using rejection samp…