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
0
votes
2answers
49 views

A so-called random variable not being well-defined

Consider this algorithm: ...
1
vote
1answer
41 views

Some questions about `RANDOM(a, b)`

This is a question from CLRS: Describe an implementation of the procedure RANDOM(a, b) that only makes calls to RANDOM(0, 1). What is the expected running time of your procedure, as a function of $a$ ...
1
vote
1answer
65 views

Yao's min-max theorem: how can the set of deterministic algorithms be finite?

I'm read Randomized Algorithms book by Motwani, the part about Yao's min-max technique: Consider a problem where the number of distinct inputs of a fixed size is finite, as is the number of distinct (...
2
votes
2answers
34 views

Approximate duplicate sampling from a stream

The following question (in two parts) comes from a homework sheet of the fall 2019 semester cs170 course taught at UC Berkely taught by professors Vazerani and Tal. Design an algorithm that takes in ...
4
votes
0answers
300 views

FPT algorithm for a variant of Feedback Vertex Set

I am interested in a variant of the Feedback Vertex Set (FVS) problem. For an undirected graph $G$ and $k\in \mathbb{N}$ we need to decide if there is a subset $S \subseteq V(G)$ of size at most $k$ s....
2
votes
1answer
59 views

Deriving a lower bound on the conditional entropy, conditioned on an event

I came across Lemma 19 in Certifying Equality With Limited Interaction, which states the following for jointly distributed random variables $Z$, $W$, where $Z$ takes values in $\{0,1\}^n$, and some ...
1
vote
1answer
24 views

Number of unique values in array in $\theta(n)$ average expected time

My idea is to initialize a hash table (with chaining) with $n$ cells, having load factor $\alpha = 1$ hence having $\theta(1)$ expected number of values in each cell in the hash table, then go cell by ...
1
vote
2answers
38 views

Probability that two specific elements are in uniformly random sample

Consider the sampling algorithm as described here section 2.2 specifically Algorithm 2.4. Essentially we are given a stream of $N$ elements and wish to maintain a uniformly random sample, $S$, of size ...
2
votes
1answer
49 views

What is the advantage of probability algorithm?

What is the advantage of probability algorithm? e.g. Las Vegas. I would also like to know some applications of the randomized algorithms. Are there any recommendable courses or books?
0
votes
2answers
39 views

How to get the expected time complexity of while loop?

How to get the expected time complexity of while loop below? ...
12
votes
3answers
2k views

How can I quickly judge whether matrix A is the inverse matrix of B?

How can I quickly judge whether matrix A is the inverse matrix of B? This is an exercise for the course I take. This question is given in the section of randomized algorithms. So I think its solution ...
4
votes
1answer
147 views

Count Sketch probability bound

I have been reading up on the Count Sketch algorithm, and I stumpled upon the Count Sketh algorithm explained in section 5 of https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf. Then, I ...
2
votes
2answers
36 views

Quicksort: Probability of an element being compared to fewer than $k$ pivot elements

Assume we want to use quicksort on some array $s$ with length $n$ consisting of only $n$ distinct elements. Let $S_{(1)},S_{(2)},\dots,S_{(n)}$ be the sorted order of the elements in $S$. Furthermore, ...
0
votes
1answer
40 views

Finding lowest point in circles

Given n disks in the plane, i want to compute the lowest point in their intersection area, im looking for a simple randomized incremental algorithm. There are some circles in the plane, these circles ...
0
votes
2answers
31 views

Will random function ever hit a hard coded decimal number?

I'm not very sure how exactly a fractal number is stored nor how random function works in mordern programming languages. But I am curious, will random function ever hits a hard coded decimal number? I ...
2
votes
2answers
164 views

Describe a Monte Carlo algorithm for the Triangle Packing problem

Book: Parameterized Algorithms by Marek Cygan (free to download legally) Chapter about Multivariate polynomials on Page 353 (In the book not the pdf) Question 10.19: Describe a Monte Carlo $2^{3k}n^{O(...
1
vote
0answers
34 views

Concentration inequality of sum of geometric random variables taken to a power

Let $X_1, \cdots, X_n$ be $n$ independent geometric random variables with success probability parameter $p = 1/2$, where $X_i = j$ means it took $j$ trials to get the first success. Let $S_d = \sum_{i=...
1
vote
1answer
98 views

k disjoint triangles with graph splitting to two distinct groups

Please note that this question is different than this question. The $k$-disjoint triangles problem is as follows: Input: A graph $G=(V,E)$ and an integer $k\in \mathbb{N}$ Output: Are there $k$ ...
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 ...
5
votes
1answer
188 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
40 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
14 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, ...
0
votes
1answer
134 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 ...
1
vote
1answer
82 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,...
3
votes
1answer
40 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
67 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 $...
3
votes
1answer
37 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
67 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
32 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
25 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 ...
2
votes
1answer
28 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 ...
1
vote
0answers
56 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^\...
2
votes
1answer
68 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 ...
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 ...
0
votes
1answer
147 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$ (...
2
votes
1answer
56 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$) ...
1
vote
1answer
35 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)$...
1
vote
1answer
29 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 ...
2
votes
1answer
47 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}^...
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 ...
1
vote
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
2answers
73 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 ...
0
votes
1answer
45 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
80 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 ...
2
votes
1answer
38 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
43 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)$ ...
1
vote
2answers
52 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
233 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
27 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., ...

1
2 3 4 5
8