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
2
votes
1answer
413 views

Can an algorithm be truly non-deterministic?

I read the term "non-deterministic algorithm" in many places but I don't see how an algorithm can be truly non-deterministic. Typically, there is some source of randomness in these algorithms. If the ...
1
vote
0answers
18 views

Representation of connected components in the $O(|E|)$ time/space variant of Karger's algorithm

I'm trying to understand the various optimizations given in the original 1992 paper on Karger's algorithm. Specifically, looking at section "3.1 Unweighted Graphs", I don't understand what ...
4
votes
1answer
173 views

Why does a polytime hitting set generator derandomize RP?

I am reading Goldreich, Vadhan, Wigderson: Simplified Derandomization of BPP Using a Hitting Set Generator and trying to understand the result that polytime hitting set generators (HSGs) would not ...
0
votes
1answer
95 views

What are the advantages of using PRNG over TRNG?

True random number generators use an unpredictable physical means to generate numbers, whereas pseudo-random numbers utilize mathematical formulas to produce a certain sequence of numbers that will ...
0
votes
1answer
31 views

Randomized algorithm for minimum cut

Given a simple undirected connected graph $G$, I want to find a min-cut of $G$ using a randomized algorithm. My attempt was to select a random edge in $G$ and reduce that edge to a single vertex. And ...
1
vote
0answers
10 views

How are randomized restarts in local search 4 times likely to give bad local minima?

I am reading section 9.3.3 Dealing with local optima in Algorithms by Dasgupta et al. and the authors mention that in randomized restarts, it is four times likely to end up with a bad solution. They, ...
1
vote
1answer
56 views

1-sparse recovery algorithm

In the reference below, a 1-sparse recovery algorithm over a vector $a \in R^n$ is defined as follows. My question is why do we need the modulus (i.e. $x \mod p$)? Algorithm: Keep track of $$ \...
1
vote
1answer
74 views

can a machine generate truly random numbers?

I know that for most programs pseudo-random numbers are sufficient, but there are ways that machines can generate truly random numbers! There are devices that generate unpredictable processes. However,...
-1
votes
0answers
43 views

An example of bad estimate in the CountMin sketch algorithm

Suppose the CountMin sketch algorithm use exactly one hash function that maps elements of the stream to $\{0,...,m-1\}$, where $m=10$. Assume elements of the stream are from set $[1..n]$ the hash ...
3
votes
1answer
38 views

Scott Aaronson's Proof of $\textbf{BPP} \subset \textbf{P/poly}$

The proof is in the image below, taken from "Quantum Computing Since Democritus": Here's what I don't totally get: my understanding of random algorithms is that randomization is not done ...
4
votes
2answers
58 views

Why is tabulated hashing 3-wise independent but not 4-wise independent?

Tabulated hashing uses tables of random numbers to compute hash values. Suppose $|\mathcal{U}| = 2^w \times 2^w$ and $m = 2^l$, so that the items being hashed are pairs $(x,y)$ where $x$ and $y$ are $...
2
votes
1answer
19 views

On efficiency analysis of randomized divide-and-conquer median find

I read following explanation from Dasgupta's Algorithms book for Median finding, this is the same philosophy applied in randomized quick-sort. Here as per book terminology $S$ denotes array of ...
3
votes
1answer
32 views

Karger's min cut and tips on bounding nonlinear recurrences

I was recently working on an old qualifying exam problem asking us to generalize Karger's randomized global min cut algorithm to that of a global min $k$-cut. I recalled the strategy of running a ...
4
votes
1answer
58 views

Las Vegas algorithm for finding 00000 in bit string

Problem 1: Consider the following problem: given a binary string $w=a_1a_2\cdots a_n \in\{0,1\}^*$, decide whether $w$ contains 00000 as a substring (i.e., where $w$ contains five consecutive 0's). ...
0
votes
0answers
31 views

Is there any proof that says “For each problem in NP there is a randomized algorithm that solves that problem in expected polynomial time.”

Is it known that "For each problem in NP there is a randomized algorithm that solves it in polynomial time"? If not true then is there any proof of that. Or does it belongs to the unknown ...
1
vote
1answer
23 views

Creation of skip list: Las Vegas or Monte Carlo?

I have come across this video on skip lists: https://www.youtube.com/watch?v=UGaOXaXAM5M Clearly, the creation of skip-list from a sorted singly linked list is a randomized algorithm. But I am ...
0
votes
0answers
32 views

kth smallest element using Randomized select

I have recently started studying Randomized algorithms on my own. I am refering to Rajiv motwani - randomized algorithms book. Objective - find kth smallest element using radomized select in $O(n^\...
0
votes
1answer
116 views

Algorithmic challenge: generate a list of random non overlapping squares

For an undisclosed reason, I need a list of $n$ squares in a two dimensions space where each square does not overlap. So the challenge is simply: given a two dimensional area $a$ (...
0
votes
2answers
67 views

About the properties of the coresets in k-median clustering

I have seen two observations from the paper by Har-Peled but I do not know how to prove them (i) If $C1$ and $C2$ are the $(k, ε)$-coresets for disjoint sets P1 and P2 respectively, then $C1 ∪ C2$ is ...
1
vote
1answer
31 views

Question in coreset construction fro K-median clustering

I was reading Ke chen's paper about coreset construction for K-median clustering. In this paper, he assumed that $A$ is an $[α, β]$-bicriteria approximation for K-median clustering for some $α, β=O(1)$...
2
votes
1answer
57 views

Question on an Algorithm for Longest Increasing Subsequence

I have been reading this paper: https://arxiv.org/abs/2011.10874 This paper presented an exact randomized algorithm with update time $\tilde{O}(n^{0.8})$. I will quickly talk about the overall idea of ...
3
votes
1answer
6k views

Understanding Expected Running Time of Randomized Algorithms

I want to understand the expected running time and the worse-case expected running time. I got confused when I saw this figure (source), where $I$ is the input and $S$ is the sequence of random ...
0
votes
0answers
21 views

Proving an algorithm satisfies $\epsilon$-DP

I am trying to prove/disprove that an algorithm satisfies $\epsilon$-DP. I proved some of them but there are 3 more which I could not decide on. Here they are: Algorithm A takes as input a dataset D ...
23
votes
7answers
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 ...
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 ...
4
votes
1answer
101 views

Pseudo-random role assignment

I have a number of players, ranging from [0..N]. Each round every player is assigned a specific role, either 1, 2 or 3. ...
2
votes
1answer
39 views

2-Approximation algorithm for for messages across a cyclic network

Question There are $n$ computers arranged in a cycle ($1,2,3..,n,1$), with undirected edges between adjacent computers. There are $m$ messages that need to be delivered. Message $i$ ($1 \le i \le m$) ...
2
votes
1answer
44 views

Algorithm for cyclic $n$-string Hamming distance with constant sized language $\Sigma$

Suppose we are given a language $\Sigma$ where, suppose, $|\Sigma| = O(1)$. Consider two fixed strings $A, B \in \Sigma^n$. Define the Hamming metric between these strings as $$d_{H}(A,B) = \sum_{i=1}^...
1
vote
1answer
27 views

Definition of BPP

We know that BPP is described as $\{L\mid \exists \text{ TM }M, \text{ s.t. }\Pr[M(x)=L(x)]\geq2/3\}$. I saw a proof which uses Chernoff bound to prove that any probability larger than $1/2$ can be ...
0
votes
0answers
21 views

The observation of the coreset in K-median clustering problems [duplicate]

I have seen two observations from the paper by Har-Peled but I do not know how to prove them (i) If $C1$ and $C2$ are the $(k, ε)$-coresets for disjoint sets P1 and P2 respectively, then $C1 ∪ C2$ is ...
0
votes
0answers
31 views

Let M be a k × n random matrix with iid entries such that

$M$ is a $k × n$ random matrix with iid entries such that $P(m_{i,j} = +1) = P(m_{i,j} = −1) = 0.5.$ Let $k = O({1\over \epsilon^l})$ for some constant $l$. $v ∈ R_n$ is a fixed vector. Does a ...
0
votes
1answer
43 views

Existence of Pseudorandom Generator

How to show that for $\epsilon>0$, there exists a function $G:\{0,1\}^n->\{0,1\}^{2^{\epsilon n}}$ that is a $2^{\epsilon n}$-prg, without the condition that is is computable in $2^{O(n)}$ time. ...
1
vote
1answer
69 views

derandomize a BPP algorithm

Suppose we have a BPP algorithm $A$ s.t. its running time is random and is $O(n^2)$ in expectation. How do we create a new BPP algorithm $B$ to solve the same problem s.t. it has deterministic running ...
1
vote
2answers
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 ...
2
votes
1answer
80 views

Flip-based algorithm for Delaunay triangulation in expected or average-case O(nlogn)

Focusing on the 2D plane: Lawson's Flip Algorithm works in worst-case $O(n^2)$ flips. I have seen it mentioned that (other?) flip-based algorithms work in expected $O(nlogn)$ time for two dimensions. ...
2
votes
1answer
37 views

Generate a uniform random numbers in $O(1)$

Suppose you have access to a random number generator $G()$ that generates uniform random numbers in $\{0,\cdots,n-1\}$. (Here, $n$ is given and cannot be changed.) How do we generate a uniform random ...
2
votes
0answers
42 views

Randomized Assignment Problem

Given $x_1,...,x_n,y_1,...,y_n\in \mathbb{R}^d$ find a permutation matrix $P\in\mathbb{S}_d$ that minimizes $\sum_{ij}P_{ij}|x_i-y_j|$. This is an assignment problem and can be solved in $O(n^3+n^2d)$ ...
0
votes
2answers
42 views

Maximization problem

I work at a company and i got to a seminar we're they told us to solve this problem below in the picture Is there an algorithm that can help me solve this question. I thought about a randomized ...
0
votes
1answer
22 views

Randomly generating graph based off number of connections on each node

I'm trying to generate a graph based off some data I have. This graph should have N nodes where the number of edges each node has is equal to a random number ...
1
vote
1answer
123 views

Efficiently selecting a random subset of size $m$ from a set of size $n$

This is a cross post of my question here on math.se. I have a list of $n$ items and would like to randomly select an $m$ set from it efficiently (in terms of time complexity). Also, I want all ...
1
vote
0answers
25 views

Distributional error probability of deterministic algorithm implies error probability of randomized algorithm?

Consider some problem $P$ and let's assume we sample the problem instance u.a.r. from some set $I$. Let $p$ be a lower bound on the distributional error of a deterministic algorithm on $I$, i.e., ...
3
votes
1answer
240 views

How do I do a biased shuffling of a deck of cards?

I currently have a deck of cards (in fact this deck is an array of sorted elements in descending order as indicated by the picture above), that I want to shuffle. However, the caveat is that I want ...
1
vote
1answer
30 views

Median of distribution with memory constraint

Task I want to approximate the median of a given distribution $D$ that I can sample from. A simple algorithm for this, using $n$ samples, is: ...
3
votes
1answer
191 views

Weighted Online Matching - randomized algorithms

Let's consider the edge weighted online matching problem. The Vertices arrive online and reveal all their current edges and edge-weights $w_e>0$. The goal is to maximize the matchings weight. An ...
3
votes
3answers
226 views

Book recommendations on the analysis of randomized algorithms

I would like to read some books (or any other material) that cover the design of randomized algorithms with a particular focus on the analysis. My main goal is to develop the rigour needed to ...
0
votes
0answers
22 views

Analyzing a counting triangles streaming algorithm which uses $\ell_0$ sampling

I'm trying to analyze the following streaming algorithm for counting triangles (see below). It supposedly works also for dynamic graphs (i.e. "turnstile model", where edge deletions are ...
2
votes
1answer
118 views

Is any randomized Algorithm a probability distribution over the set of deterministic Algorithms?

If there is a finite set of Instances of size n and the set of (reasonable) deterministic algorithms is finit. Can any randomized Algorithm be seen as a probability distribution over the set of ...
1
vote
1answer
140 views

Randomized Algorithms: High-Probability vs. Expectation

Hopefully this question isn't too general, but I was wondering what the relationship is between randomized algorithms that perform well with high-probability and those that perform well in expectation....
1
vote
1answer
1k views

Hiring problem from CLRS

Hiring problem is discussed in section 5.1 and 5.2 of the CLRS and I'm referring this for exercise solutions. However, for Exercise question 5.2-2 my solution deviates from the one given in the ...
1
vote
0answers
24 views

Space complexity of using a pairwise independent hash family

I'm trying to analyze the space complexity of using the coloring function $f$ which appears in "Colorful Triangle Counting and a MapReduce Implementation", Pagh and Tsourakakis, 2011, https:...

1
2 3 4 5
8