# Questions tagged [randomized-algorithms]

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

373 questions
Filter by
Sorted by
Tagged with
6k views

### How to prove correctness of a shuffle algorithm?

I have two ways of producing a list of items in a random order and would like to determine if they are equally fair (unbiased). The first method I use is to construct the entire list of elements and ...
9k views

### Can we generate random numbers using irrational numbers like π and e?

Irrational numbers like $\pi$, $e$ and $\sqrt{2}$ have a unique and non-repeating sequence after the decimal point. If we extract the $n$-th digit from such numbers (where $n$ is the number of times ...
4k views

### Sorting algorithms which accept a random comparator

Generic sorting algorithms generally take a set of data to sort and a comparator function which can compare two individual elements. If the comparator is an order relation¹, then the output of the ...
626 views

5k views

### Algorithm to find all 2-hop neighbors lists in a graph

Given a graph $G = (V,E)$, where $|V| = n$. What is a fast algorithm for generating the collection of all 2-hop neighborhood lists of all nodes in $V$. Naively, you can do that in $O(n^3)$. With ...
338 views

### Are randomized algorithms constructive?

From , the proofs by the probabilistic method are often said to be non-constructive. However, a proof by probabilistic method indeed designs a randomized algorithm and uses it for proving existence. ...
270 views

### Is it possible to simulate a fair coin with a finite number of tossing of a biased one?

It is a classic problem to simulate a fair coin with a biased one. According to Fair Coin (wiki), John von Neumann gave the following procedure: Toss the coin twice. If the results match, start over,...
489 views

### Isn't polynomial identity testing over arithmetic *expressions* trivial?

Polynomial identity testing is the standard example of a problem known to be in co-RP but not known to be in P. Over arithmetic circuits, it does indeed seem hard, since the degree of the polynomial ...
739 views

### Does a coin tossing algorithm terminate? [duplicate]

Suppose we have an algorithm like: n = 0 REPEAT c = randomInt(0,1) n = n + 1 UNTIL (c == 0) RETURN n (Assumuing the random number generator produces "good" ...
231 views

### Is there any efficient algorithm for primality testing for numbers that are of the form $4k+3$ using the square root function?

I was reading CLRS and it asked to show that if $p$ is a prime of the form $4k+3$ and $a$ was a quadratic residue, then $a^{k+1}$ is a square root (one can also easily show that $a^{-k}$ is a square ...
195 views

### Finding a maximal independent set in parallel

On a graph $G(V,E)$, we do the following process: Initially, all nodes in $V$ are uncolored. While there are uncolored nodes in $V$, each uncolored node does the following: Selects a random real ...
135 views

### Compute the expected size of an approximation of vertex cover

Consider the following randomized approximation algorithm of vertex cover: Input: A graph G = (V, E). Output: A set $C_G \subseteq V$ a vertex cover of $G$. The algorithm: Set $C_G := \emptyset$. ...
753 views

### How can you shuffle in $O(n)$ time if you need $\Omega(n \log n)$ random bits?

A shuffling algorithm is supposed to generate a random permutation of a given finite set. So, for a set of size $n$, a shuffling algorithm should return any of the $n!$ permutations of the set ...
247 views

### Why is randomness a problem? (i.e. why do we care about derandomization?)

I'm reading Aaronson's survey on P vs. NP, and I've come to understand that in CS theory, people really care about derandomization results like P vs. BPP etc. My question is, what's the problem with ...
708 views

### Random restarts for unsatisfiable instances

In the worst case, Boolean satisfiability (assuming P!=NP) takes exponential time. Nonetheless, modern SAT solvers using variants of DPLL, are able to solve enough instances to be useful in practice. ...
2k views

### Constructing a random Hamiltonian Cycle (Secret Santa)

I was programming a little Secret Santa tool for my extended family's gift exchange. We had a few constraints: No recipients within the immediate family Nobody should get who they got last year The ...
762 views

### Need a hint! Karger's algorithm versus Kruskal, spanning tree distribution

Let G = (V,E) be a unit-capacity graph with n vertices and m edges. Let T denote all the spanning trees in G. If we run Karger's algorithm, we will get a random spanning tree in T formed by the ...
2k 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 ...
204 views

### Sorting an unordered pile of items into drawers with minimal drawer movements

A while ago, I was doing my laundry late at night. When I brought my laundry back to my dorm, I started to put it away. My wardrobe is set up as follows: My drawers are categorized by the type of ...
182 views

### Why does PCP theorem imply that NP problems are hard to approximate?

What I only got currently from PCP theorem is that it needs at most $O(\log n)$ randomness and $O(1)$ query of proof to approximate. So how does this result relate to the fact that solution to NP ...
2k views

### The physical implementation of quantum annealing algorithm

From that question about differences between Quantum annealing and simulated annealing, we found (in commets to answer) that physical implementation of quantum annealing is exists (D-Wave quantum ...
1k views

### Relationship between Las Vegas algorithms and deterministic algorithms

I'm wondering why the following argument doesn't work for showing that the existence of a Las Vegas algorithm also implies the existence of a deterministic algorithm: Suppose that there is a Las ...
920 views

### Example for a non-trivial PCP verifier for an NP-complete problem

During my involvement in a course on dealing with NP-hard problems I have encountered the PCP theorem, stating $\qquad\displaystyle \mathsf{NP} = \mathsf{PCP}(\log n, 1)$. I understand the ...
694 views

### Randomized Rounding of Solutions to Linear Programs

Integer linear programming (ILP) is an incredibly powerful tool in combinatorial optimization. If we can formulate some problem as an instance of an ILP then solvers are guaranteed to find the global ...
282 views

### Why is the probability used in the definition of RP complexity classes, arbitrary?

I was looking at the following wikipedia article on the RP complexity class: https://en.wikipedia.org/wiki/RP_(complexity) In its definition it states: If the correct answer is NO then it always ...
1k views

### Correctness of Freivald algorithm for checking matrix multiplication, why is the probability of checking $AB \neq C$ at least 1/2?

I am going to consider Freivald's algorithm in the field mod 2. So in this algorithm we want to check wether $$AB = C$$ and be correct with high probability. The algorithm choose a random $r$ n-...
1k views

### Why does the Count-Min Sketch require pairwise independent hash functions?

The Count-Min Sketch is an awesome data structure for estimating the frequencies of different elements in a data stream. Intuitively, it works by picking a variety of hash functions, hashing each ...
112 views

### Completeness of formal definition of 'hardness on the average'

While reading a cryptography textbook, i find the definition of a function that is hard on the average.(More precisely, it is 'hard on the average but easy with auxiliary input', but i omit latter for ...
964 views

### Generate a random graph with geometrical degree distribution

I'm working on graph generation, trying to implement the RT-nested-Smallworld network model described in this paper. We are talking about generating an undirected graph in a slightly different way ...
Consider an array $X$ of $n$ cells, each containing a number from $\{1,..., n\}$. There is at least one duplicate number, i.e., a number that appears at least twice. I want output some duplicate ...