Pseudorandom Functions: Three Decades Later

63 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Fairness Through Computationally-Bounded Awareness (2018, background): “The connection between learning and pseudorandom functions [23, 11] is well-established; under stronger cryptographic assumptions as in [2], the reduction implies that a running time of ⌦(|C|) is necessary for some constant ↵ > 0.”
Calibration for the (Computationally-Identifiable) Masses (2017, background): “In particular, under cryptographic assumptions [Val84, GGM84, BR17], this result implies that there is some constant t > 0, such that any algorithm that learns an α -multicalibrated predictor requires Ω( |C| t ) time.”
Multicalibration: Calibration for the (Computationally-Identifiable) Masses (2018, background): “In particular, under cryptographic assumptions (Valiant, 1984; Goldreich et al., 1984; Bogdanov & Rosen, 2017), this result implies that there is some constant t > 0, such that any algorithm that learns a (C, α)-multicalibrated predictor requires Ω(|C|t) time for arbitrary C.”