New answers tagged

1 vote
Accepted

What is the largest "allowed" seed for a PRNG to not give any extra power to a deterministic machine?

I think there must be some confusion in the problem setting. Given an input of $n$ bits chosen uniformly at random, there is no algorithm to compress it to something whose length is on average ...
D.W.'s user avatar
  • 156k
1 vote

Optimal randomized algorithm for set cover

Approximation ratio of 1 means that it outputs an exact solution (so it is not an approximation algorithm but rather an exact algorithm). Set cover is known to be NP-hard, so there is no such ...
D.W.'s user avatar
  • 156k

Top 50 recent answers are included