Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

All Questions

3
votes
1answer
149 views

Existence of suitable pseudo-random number generators to derandomize BPP to P

I am struggling to understand how the known oracle, and conditional derandomization results connecting $BPP$ and $P$, relate to each other. My understanding is that if there is a suitably strong ...
1
vote
1answer
29 views

Hardness amplification of PRFs by increasing key length

I was reading the GGM construction for PRFs and wondering the relation between key length and hardness. GGM construction does not seem to yield any significant improvements. Are there any PRF ...
2
votes
1answer
81 views

What does it mean to fool a function?

In computer science papers, I see about the term 'fooling' a function. What does it mean to fool a function against a particular complexity class? Why is it important?