### Abstract

We define a concept class F to be time-space hard (or memory-samples hard) if any learning algorithm for F requires either a memory of size super-linear in n or a number of samples super-polynomial in n, where n is the length of one sample. A recent work shows that the class of all parity functions is time-space hard [Raz, FOCS'16]. Building on [Raz, FOCS'16], we show that the class of all sparse parities of Hamming weight l is time-space hard, as long as l ≥ ω(log n/log log n). Consequently, linear-size DNF Formulas, linear-size Decision Trees and logarithmic-size Juntas are all time-space hard. Our result is more general and provides time-space lower bounds for learning any concept class of parity functions. We give applications of our results in the field of bounded-storage cryptography. For example, for every ω(log n) ≤ k ≤ n, we obtain an encryption scheme that requires a private key of length k, and time complexity of n per encryption/decryption of each bit, and is provably and unconditionally secure as long as the attacker uses at most o(nk) memory bits and the scheme is used at most 2^{o(k)} times. Previously, this was known only for k = n [Raz, FOCS'16].

Original language | English (US) |
---|---|

Title of host publication | STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing |

Editors | Pierre McKenzie, Valerie King, Hamed Hatami |

Publisher | Association for Computing Machinery |

Pages | 1067-1080 |

Number of pages | 14 |

ISBN (Electronic) | 9781450345286 |

DOIs | |

State | Published - Jun 19 2017 |

Event | 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 - Montreal, Canada Duration: Jun 19 2017 → Jun 23 2017 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

Volume | Part F128415 |

ISSN (Print) | 0737-8017 |

### Other

Other | 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 |
---|---|

Country | Canada |

City | Montreal |

Period | 6/19/17 → 6/23/17 |

### All Science Journal Classification (ASJC) codes

- Software

## Fingerprint Dive into the research topics of 'Time-space hardness of learning sparse parities'. Together they form a unique fingerprint.

## Cite this

*STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing*(pp. 1067-1080). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. Part F128415). Association for Computing Machinery. https://doi.org/10.1145/3055399.3055430