Questions tagged [randomized-algorithms]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
369 views

Significance of parameters in Tiny Mersenne Twister algorithm

I am trying to implement and optimize the Tiny Mersenne Twister (TinyMT) algorithm as required by an API I am developing with my team at work. The algorithm utilizes a C structure with 32-bit unsigned ...
1
vote
1answer
2k views

Seeding the Mersenne Twister Random Number Generator

I am trying to understand how the Mersenne Twister random number generator works (in particular, the 32-bit TinyMT). I am still relatively new to the concept of RNG. As I read the source code, I ...
3
votes
1answer
159 views

Randomized convex hull

I've been recently studying Monte-Carlo and other randomized methods for a lot of applications, and one that popped into my mind was making an (approximate) convex hull by examining random points, and ...
3
votes
2answers
204 views

Randomized Algorithms Probability

I'm taking a grad level randomized algorithms course in the fall. The professor is known for being very detail oriented and mathematically rigorous, so I will be required to have an in-depth ...
5
votes
2answers
182 views

Random generator considerations in the design of randomized algorithms

It is well known that the efficiency of randomized algorithms (at least those in BPP and RP) depends on the quality of the random generator used. Perfect random sources are unavailable in practice. ...
4
votes
2answers
473 views

From Whence the Randomization in Randomized Quicksort

Cormen talks briefly about the advantages of picking a random pivot in quicksort. However as pointed out here(4th to the last paragraph): Using a random number generator to choose the positions is ...
6
votes
4answers
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 ...
9
votes
2answers
821 views

Is there a “sorting” algorithm which returns a random permutation when using a coin-flip comparator?

Inspired by this question in which the asker wants to know if the running time changes when the comparator used in a standard search algorithm is replaced by a fair coin-flip, and also Microsoft's ...
6
votes
1answer
163 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 ...
3
votes
2answers
417 views

Solve Integer Factoring in randomized polynomial time with an oracle for square root modulo $n$

I'm trying to solve exercise 6.5 on page 309 from Richard Crandall's "Prime numbers - A computational perspective". It basically asks for an algorithm to factor integers in randomized polynomial time ...
6
votes
1answer
393 views

The Power of Randomized Reduction

I try to figure out a redundant power of two-sided error randomized Karp - reduction. It's well known fact and it is relatively hard to show that BPP is reducible by a one-sided error randomized Karp-...
9
votes
3answers
2k views

Concrete understanding of difference between PP and BPP definitions

I am confused about how PP and BPP are defined. Let us assume $\chi$ is the characteristic function for a language $\mathcal{L}$. M be the probabilistic Turing Machine. Are the following definitions ...
5
votes
2answers
307 views

randomized algorithm for checking the satisfiability of s-formulas, that outputs the correct answer with probability at least $\frac{2}{3}$

I'm trying to practice myself with random algorithms. Lets call a CNF formula over n variables s-formula if it is either unsatisable or it has at least $\frac{2^n}{n^{10}}$ satisfying assignments. I ...
12
votes
3answers
1k views

Discrepancy between heads and tails

Consider a sequence of $n$ flips of an unbiased coin. Let $H_i$ denote the absolute value of the excess of the number of heads over tails seen in the first $i$ flips. Define $H=\text{max}_i H_i$. Show ...
17
votes
2answers
7k views

What is the advantage of Randomized Quicksort?

In their book Randomized Algorithms, Motwani and Raghavan open the introduction with a description of their RandQS function -- Randomized quicksort -- where the pivot, used for partitioning the set ...
6
votes
1answer
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 ...
8
votes
1answer
4k 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 ...
5
votes
2answers
549 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 ...
2
votes
2answers
254 views

Guessing the best choice to maximize returns

There are $N$ number of people and $X$ amount of objects with different values. Each person will choose an object and will obtain that objects value. If multiple people choose the same object then the ...
8
votes
2answers
258 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. ...
14
votes
2answers
903 views

Classfication of randomized algorithms

From Wikipedia about randomized algorithms One has to distinguish between algorithms that use the random input to reduce the expected running time or memory usage, but always terminate with a ...
4
votes
1answer
362 views

Choosing an element from a set satisfying a predicate uniformly at random in $O(1)$ space

We are given a set of objects, say integers, $S$. In addition, we are given a predicate $P$, for example $P(i): \Leftrightarrow i \geq 0$. We don't know in advance how many elements of $S$ satisfy the ...
19
votes
3answers
509 views

Problems in P with provably faster randomized algorithms

Are there any problems in $\mathsf{P}$ that have randomized algorithms beating lower bounds on deterministic algorithms? More concretely, do we know any $k$ for which $\mathsf{DTIME}(n^k) \subsetneq \...
21
votes
4answers
3k 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 ...
6
votes
1answer
146 views

Streaming algorithm and random access

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 ...
23
votes
1answer
5k 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 ...
4
votes
2answers
590 views

Online generation of uniform samples

A source provides a stream of items $x_1, x_2,\dots$ . At each step $n$ we want to save a random sample $S_n \subseteq \{ (x_i, i)|1 \le i \le n\}$ of size $k$, i.e. $S_n$ should be a uniformly chosen ...
3
votes
1answer
432 views

Deterministic and randomized communication complexity of set equality

Two processors $A, B$ with inputs $a \in \{0, 1\}^n$ (for $A$) and $b \in \{0, 1\}^n$ (for $B$) want to decide whether $a = b$. $A$ does not know $B$’s input and vice versa. A can send a message $m(...
3
votes
1answer
103 views

Making random sources uniformly distributed

How do I build a random source that outputs the bits 0 and 1 with $prob(0) = prob(1) = 0.5$. We have access to another random source $S$ that outputs $a$ or $b$ with independent probabilities $prob(a)$...
4
votes
1answer
581 views

Building ideal skip lists

I'm trying to find the best algorithm for converting an “ordinary” linked list into an “ideal" skip list. The definition of an “ideal skip list” is that in the first level we'll have all the ...
19
votes
1answer
471 views

Algorithm to chase a moving target

Suppose that we have a black-box $f$ which we can query and reset. When we reset $f$, the state $f_S$ of $f$ is set to an element chosen uniformly at random from the set $$\{0, 1, ..., n - 1\}$$ where ...
11
votes
1answer
155 views

Sharp concentration for selection via random partitioning?

The usual simple algorithm for finding the median element in an array $A$ of $n$ numbers is: Sample $n^{3/4}$ elements from $A$ with replacement into $B$ Sort $B$ and find the rank $|B|\pm \sqrt{n}$ ...
14
votes
1answer
6k views

Randomized Selection

The randomized selection algorithm is the following: Input: An array $A$ of $n$ (distinct, for simplicity) numbers and a number $k\in [n]$ Output: The the "rank $k$ element" of $A$ (i.e., the one in ...