The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [randomized-algorithms]

Questions about algorithms whose behaviour is determined not only by its input but also by a source of random numbers.

289 questions
Filter by
Sorted by
Tagged with
357 views

What is the approximation ratio of this randomized algorithm for finding matchings?

I would like to analyze the following algorithm in terms of its approximation ratio. Here is the algorithm: ...
1k views

What does the “principle of deferred decisions” formally mean

I have encountered the phrase "Principle of deferred decisions" in Mitzenmacher and Upfal's book on Randomized Algorithms and several other courses online. Isn't it just conditional probability? In my ...
101 views

min cut for multiple partitions

So I am familiar with the standard minimum cut problem in which the goal is to find the smallest possible set of edges in a graph such that, upon their removal, we have two nonempty, disjoint ...
489 views

Does hashing under the Simple Uniform Hashing Assumption battle worst-case adversaries the same way quick sort does?

One common way for algorithms to battle adversarial inputs is by acting randomly. One popular example is quicksort and choosing pivots randomly (this sort of notions is explained well in section 5.3 ...
96 views

44 views

Can one use the PCP theorem to prove correctness of deternimistic algorithms?

I am thinking of the equality "PCP(O(log(n)),0) = P" Say I have a deterministic polynomial time algorithm $A$ whose correctness I can't prove immediately. But say I create a probabilistic version of ...
141 views

Analysis of sorting Algorithm with probably wrong comparator? [duplicate]

It is an interesting question from an Interview, I failed it. An array has $n$ different elements $[A_1, A_2, \ldots, A_n]$ (random order). We have a comparator $C$, but it has a probability p to ...
62 views

80 views

Does randomness make exponential difference?

Schwartz–Zippel lemma can solve the polynomial identity testing in expected poly-time. As far as I know, there is no deterministic poly-time algorithm for the problem, but we do not know if the ...
A file is downloaded from a server and is represented as $a = \{0, 1\}^n$. The server has that file as $b = \{0, 1\}^n$. We want to ensure a degree of certainty that $a=b$, using a randomized ...