Questions tagged [randomized-algorithms]
Questions about algorithms whose behaviour is determined not only by its input but also by a source of random numbers.
421
questions
2
votes
0
answers
48
views
What is the depth distribution of a random binary tree with n nodes?
Assume I generate a random binary tree with a bounded height with $n$ nodes.
For a given key we measure the length of its path (the maximum can be $n-1$). So my Question is what is the distribution of ...
- 21
1
vote
1
answer
44
views
Showing that nearly regular graphs have a specific $(2,O(\log n))$ ruling set with high probability
An $(\alpha,\beta)$-ruling set is a set $S$ such that any two nodes in $S$ are at distance at least $\alpha$ from each other, and, for any node $v \notin S$, there exists a node $u \in S$ such that ...
- 305
2
votes
0
answers
27
views
Understanding the proof of a property of universal relation
In the paper Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems, the authors consider the universal relation problem in 2-party communication complexity, which is ...
- 21
0
votes
1
answer
47
views
How is P not trivially equal to ZPP?
The definition of ZPP seems to be
$$ZPP = RP \cap coRP.$$
I think ZPP should then be equivalent to P, because for any language L in ZPP, there is an algorithm A and B proving that it is in RP and coRP,...
- 169
0
votes
1
answer
127
views
Parallel Algorithm Pseudocode: Helman-JaJa Listrank
What would Helman-JaJa listrank pseudocode be like? I tried looking around but all I found were "prosecode" descriptions (eg pp. 18-19 here) which I find kinda hard to follow.
- 11
1
vote
0
answers
32
views
Random process on ternary string
Given a ternary string S of length N, do the following:
Find the first strictly decreasing pair of digits.
Randomly change one of the digits in the pair to another value.
The string is circular (i.e ...
- 11
1
vote
0
answers
17
views
Algorithm for finding relative estimate from absolute estimate
I am trying to find a textbook reference for an algorithm that gives you a relative estimate of a quantity $a$ (i.e. $|a-\overline{a}|\leq \epsilon_{rel} a$) from an algorithm that gives you an ...
- 237
0
votes
0
answers
13
views
Randomized function with a communication size restriction
I need to create a randomized function between two participants, 1 and 2. The two participants have both n bit sized strings, and they want to determine whatever they have the same strings.
1 and 2 ...
- 101
0
votes
1
answer
20
views
Balanced Directed Graph Realization
I have a list of integers: each integer represents a node in a directed graph, and the value of the integer is both the desired indegree and outdegree of said node.
Some research suggests that this is ...
- 103
1
vote
1
answer
53
views
Shuffling two related sets together
Given two sets of values $a_1, a_2, ... a_n$ and $b_1, b_2, ... b_n $ what would be a good way to shuffle them together while keeping $a_i$ and $b_i$ at least $gap$ spots apart?
For example, if we ...
- 113
0
votes
2
answers
51
views
Can a program that terminates have a running time of infinity? (Or not have an upper bound)
Can we have an algorithm that takes some input and does something random to it (in such a way that the algorithm does terminate) which does not have a worst-case running time upper-bound?
A (non-)...
- 359
1
vote
1
answer
52
views
Why can't we just compose PRGs to get better PRGs?
I'm learning about (complexity-theoretic) pseudorandom number generators, and I have a pretty basic question about them that I couldn't find an answer to.
Let's say we have a PRG for $P$ that can fool ...
- 378
1
vote
1
answer
125
views
Prove the expected size of the independence set got by a random algorithm is at least 1/d of the maximum size
I am doing an exercise related to maximizing Independent Set, I have $G = (V = \{v_1, . . . , v_n\}, E)$ as an undirected graph. This graph as $n!$ possible orderings for the vertices $V$.
If we pick ...
- 25
0
votes
0
answers
10
views
On the definition of multiple-passes random order streaming algorithms
Some problems have better streaming algorithms if we assume that the input arrives in a random order.
I am looking at a paper that discusses multiple-passes random order streaming algorithms and am ...
- 141
3
votes
1
answer
87
views
Algorithm to select a random bit string with constraints
Problem Description
Given $a, b, n \in \mathbb{N}$ with $a < b < n$.
Let $M$ be the set of all possible bit strings of length $n$ which begin and end with one and have at least $a$ and at most $...
- 41
1
vote
0
answers
48
views
Combine Las Vegas and Montecarlo probabilistic algorithms to improve chance of finding correct answer
Let's say that I have a Las Vegas algorithm for a given problem (whose answer is true/false for simplicity) with a chance of ...
- 239
1
vote
0
answers
19
views
Randomly Split a Bar Into Beats
So I'm writing a software that generates random MIDI tracks based on a given mode, tonal etc.
As for now the randomisation works on tones building sequences of equal duration.
What I'd like to do is ...
- 111
1
vote
0
answers
31
views
Random Self-Reducibility of the Discrete Logarithm Problem
Section 10.1.2 of Sanjeev Arora and Boaz Barak's Computational Complexity: A Modern Approach defines random self-reducibility and proves hardness of the discrete logarithm by reducing a worst case ...
- 76
1
vote
1
answer
77
views
What is the complexity of problems with randomized polynomial time verification?
Imagine a Problem $A$ with input size $n$ for which you can get a proof certificate (polynomial number of bits).
Next you try to use this string to verify if your problem is solved or not.
You know ...
user154939
0
votes
0
answers
68
views
What is the expected time complexity of this algorithm?
In the following algorithm $A[1..n]$ denotes an array $A$ of size $n$, of $n$ distinct integers. Func1() and Func2() are functions that run in $\mathcal O(\log n)$ and $\mathcal O(n)$ time, ...
- 257
0
votes
0
answers
34
views
Randomized-Select Problem
RANDOMIZED-SELECT
A = {12, 0, 4, 3, 5, 7, 9, 2, 8, 11}
RAND-SELECT(A, p, q, i) -> ith smallest of A[p.. q]
If p = q then return A[q]
r <- RAND-Partition (A, p, q)
k <- r-p+1 then return A[r] k= ...
- 101
3
votes
0
answers
42
views
Given a complexity class C for problems which can be solved using exponential time and an exponential number of random bits. C ⊆ NEXP?
There must be a complexity class C that includes exactly the problems that can be solved in exponential time and having access to a truly random coin (which in turns implies that you will be able to ...
- 145
3
votes
1
answer
707
views
Is it possible to randomly allocate items to bins such that each distinct allocation has equal probability?
I'm trying to randomly allocate N indistinguishable items over B indistinguishable bins with unlimited capacity. Each allocation should occur with equal probability. An allocation identifies the ...
- 161
0
votes
0
answers
82
views
Analysis of randomized algorithms
The expected running time, $T(n)$, of quicksort when the pivot is chosen uniformly at random satisfies $$ T(n) \leq \mathcal O(n) +\frac{1}{n}\sum^{n-1}_{i=0}(T(i) + T(n - i)),$$
which leads to the ...
- 257
0
votes
1
answer
110
views
Expected runtime of recursive algorithm with optional part
I have a randomized recursive algorithm which expected running time is $T(n)$. In particular, the recursion looks like this: $$ T(n) \leq \mathcal cn + R ,$$ where $R$ is a recursive term that depends ...
- 71
0
votes
0
answers
40
views
Runtime Analysis of Uniform Sampling via exact degree computation
Let $\mathcal{A} \subseteq \mathcal{B}$ given as a collection of arrays. The degree of an element $a \in \cup \mathcal{A}$, is the number of sets of $\mathcal{A}$ that it contains - that is, $d_{\...
- 123
1
vote
0
answers
42
views
Communication complexity of index problem with large domains
In the standard definition of the Index problem in one-way 2-party communication complexity, there are two players, Alice and Bob. Alice gets a binary input vector $x$ of length $n$ and Bob gets an ...
0
votes
1
answer
29
views
Is there an algorithm for mapping two ambiguous and unrelated data sets?
I was curious to see whether or not there was a common algorithm for mapping two unrelated data sets.
So for example let's say I wanted to give you a spirit animal based on your name, birthday, zodiac ...
- 101
2
votes
1
answer
61
views
The universal relation problem in communication complexity
In the universal relation $UR_n$ problem [1] of communication complexity, there are two players Alice and Bob. Alice gets a string $x \in \{0,1\}^n$, Bob gets a string $y \in \{0,1\}^n$ with the ...
1
vote
2
answers
88
views
Are there any freely available resources to study randomized algorithms?
I am a student want to study randomized algorithm. Someone recommend cs271 to me, but it's restricted now.
Can someone recomend a good resource to study randomized algorithm, thank you a lot.
- 176
1
vote
0
answers
49
views
Bloom filter creating different arrays from two input sets
Assume a bloom filter that is composed of $H = \{H_1, ..., H_k\}$ hash functions, and uniformly maps elements from an input set $X$ to an array $A$ of size $n$. Let $X_1, X_2$ (not same) be two input ...
1
vote
1
answer
64
views
Randomized Algorithm Lemma
Hello I am struggling with proving a lemma, it goes as follows:
Suppose we have a vector r = (r1....rn)^T where rj is either 0 or 1 which is selected uniformly at random with probability 1/2. Suppose ...
- 37
2
votes
1
answer
75
views
Question about what exponentially small probability of success means in randomized algorithms
I am reading the book Randomized Algorithms By Motwani and Raghavan, and one of their exercises gives a modification of Karger's Min-Cut algorithm(Both is Monte Carlo) which picks two vertices and ...
- 169
1
vote
0
answers
21
views
Algorithmic ideas to multiply two tall & skinny matrices into one large square matrix?
This problems comes from AI, and it looks something like this:
I am supposed to multiply two floating-point matrices A * B. A ...
- 11
4
votes
2
answers
77
views
How can we prove QuickShuffle uniformly permutes it input array?
I'm studying Algorithms
by Jeff Erickson. Consider this exercise from that textbook:
Prove that the following algorithm, modeled after quicksort, uniformly permutes its input array, meaning each of ...
- 53
0
votes
0
answers
28
views
Graph with constant edge connectivity that remains connected after edge removals
I have an undirected graph $(V, E)$ with constast edge connectivity $\lambda$. Each edge is sampled independently with probability $min\{1,\frac{c \ln n}{\lambda}\}$ for some $c > 0$. I need to ...
- 159
1
vote
0
answers
22
views
Counting number of copies of a given tree T in a graph G. Looking for a randomised algorithm which is an FPRAS
I'm looking for a randomised algorithm (specifically an epsilon-delta approximation) which takes as input a graph G, a subgraph T (which is a tree), and outputs an approximation to the total number of ...
0
votes
1
answer
23
views
Can we simply consider a pseudo random number generator to be a function $f: \Bbb{Z}_n \to \Bbb{Z}_n$ for ever-increasing $n$?
On modern architectures, random number generators get seeded by the current system time as a source of randomness, which is nice because it is kind of unpredictable when a process will switch to the ...
0
votes
1
answer
44
views
Are turing machines & equivalents with infinite sized random programs still turing machines?
Are turing machines with an infinite program tape that is completely random, or another example is a Game of Life simulation on an infinite randomly initialized grid, still turing machines, so to ...
0
votes
1
answer
81
views
Randomized Algorithm Log-Space Exp-Time
I'm looking for an example of a randomized algorithm that halts with probability 1 (halts almost surely), uses only logarithmic space (worst case) and whose expected run time is not polynomial in the ...
1
vote
1
answer
246
views
Check Welzl's algorithm time complexity
From the wiki this is the algorithm and we know that final complexity is O(n) but how we reached to this , is my problem :
...
- 163
0
votes
1
answer
60
views
Proving there exists no algorithm that can solve a basic problem
Consider the following basic problem, for which the statement is "obvious," but I can't seem to find totally convincing proof.
Problem: Let $S$ be a set of $n$ elements, where $n\geq 2$ is ...
- 271
2
votes
0
answers
57
views
Size of the maximum matching in arbitrary graph
I am asked to find a probabilistic algorithm to determine the size of the maximum matching of an arbitrary simple undirected graph $ G $.
My claim is that, it is equivalent to find a global min cut on ...
- 159
2
votes
0
answers
43
views
Fastest randomized algorithm for trace distance
Assume to have query access to the values $p(x)$, and $q(x)$ of two probability distributions over n elements $x \in X$, $|X|=n$.
That is, for a given $x\in X$ we pay constant time $O(1)$ to perform a ...
- 237
2
votes
0
answers
57
views
Decision problem solution monte carlo
I have a rather straightforward question for this community (that I am not able to solve). Assume there is a probability of Tom having a bag of candy. If Tom has a bag, he says the truth 4/5 times and ...
- 21
0
votes
1
answer
134
views
Bounding this probability in this Monte Carlo algorithm
Let $P$ be a YES-NO decision problem. Let $A$ be an algorithm for deciding on it such that it is correct with probability $4/5$, in both cases (YES an NO). Design an algorithm that is correct with ...
- 81
1
vote
1
answer
26
views
Modifying the probability of sucess of an algorithm
This is motivated from a homework question. Let $A$ be an algorithm with probability of success equal to $q$ for solving a given problem. Let $p \in (0, 1)$. Find an algorithm that has a probability ...
- 81
2
votes
0
answers
77
views
Independent Feedback Vertex Set
In Independent Feedback Vertex Set, we are given an undirected graph $G$, and an integer $k \in \mathbb{N}$.
The objective is to decide whether there exists a feedback vertex set S of G of size at ...
- 100
4
votes
1
answer
464
views
Is there some kind of expected error margin for my Monte Carlo algorithm?
My Monte Carlo algorithm starts by placing some circles in the plane with potential overlaps. I then place a large circle somewhere and compute the overlapping area of this larger circle with the ...
- 685
1
vote
1
answer
158
views
Expected linear-time algorithm for finding MST with probability for sampling an edge other than 1/2
I'm trying to understand this algorithm : https://en.m.wikipedia.org/wiki/Expected_linear_time_MST_algorithm
As described in the wiki article, it works in 5 steps to find the MSF for a graph $G = (V, ...
- 143