An algorithm whose behaviour is determined by its input and a source of random numbers.
3
votes
1answer
34 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
46 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 ...
3
votes
2answers
45 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. ...
3
votes
2answers
92 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 ...
3
votes
4answers
187 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 ...
7
votes
2answers
158 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
65 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 ...
1
vote
1answer
55 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 ...
5
votes
0answers
55 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 ...
3
votes
3answers
115 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
166 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 ...
8
votes
2answers
180 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 ...
10
votes
2answers
271 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 ...
5
votes
1answer
229 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 ...
5
votes
1answer
189 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
120 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
107 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 ...
7
votes
2answers
130 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. ...
8
votes
1answer
111 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 ...
10
votes
4answers
1k views
Differences and relations between randomized and nondeterministic algorithms?
What differences and relations are between randomized algorithms and nondeterministic algorithms?
From Wikipedia
A randomized algorithm is an algorithm which employs a degree of
randomness as ...
2
votes
1answer
70 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 ...
10
votes
1answer
267 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 ...
6
votes
3answers
485 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
101 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 ...
11
votes
1answer
380 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
1answer
117 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 ...
2
votes
1answer
145 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 ...
3
votes
1answer
78 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 ...
4
votes
1answer
252 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 ...
16
votes
1answer
206 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 ...
10
votes
1answer
84 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}$ ...
7
votes
1answer
536 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 ...
