enter search term and/or author name
Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala, Ying Xiao
Article No.: 8
We introduce a framework for proving lower bounds on computational problems over distributions against algorithms that can be implemented using access to a statistical query oracle. For such algorithms, access to the input distribution is...
Section: Design 8 Analysis of Algorithms and/or Randomness
Benny Applebaum, Jonathan Avron, Chris Brzuska
Article No.: 10
We study the possibility of computing cryptographic primitives in a fully black-box arithmetic model over a finite field F. In this model, the input to a cryptographic primitive (e.g., encryption scheme) is given as a sequence of field...