Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 64 Issue 2, April 2017

Section: Design 8 Analysis of Algorithms and/or Randomness

Statistical Algorithms and a Lower Bound for Detecting Planted Cliques
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala, Ying Xiao
Article No.: 8
DOI: 10.1145/3046674

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

Arithmetic Cryptography
Benny Applebaum, Jonathan Avron, Chris Brzuska
Article No.: 10
DOI: 10.1145/3046675

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...