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
1 answer
93 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 ...
0 votes
0 answers
22 views

Randomized weighted majority with rational weights

Consider the RWM online algorithm as defined in this Wikipedia article; this version is with multiplicative update. Let us assume that we define our weights as a fraction; that is, $w_i^t = 1 / (M_i^t+...
3 votes
1 answer
432 views

Proof for boosting success probability of a random algorithm with binary output

There is a theorem stating that, given a random algorithm with a binary output that has a success probability $\geq 2/3$, you can always create the another algorithm that solves the same problem but ...
0 votes
1 answer
123 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 ...
4 votes
1 answer
123 views

Random paths from one point to another going through all the cells of a square grid

I am looking for a very specific algorithm, so I think it doesn't exist yet. I would be satisfied if anyone was able to give me some hints to develop it. My problem is about a square grid of size <...
1 vote
1 answer
50 views

Finding f(x) using a BPP algorithm (optimization problem to decision problem)

Say there is a function $f:\mathcal{X} \mapsto \{1, 2,...,n\}$. We want to solve a specific instance of $f(x)$. We have black box access to a BPP algorithm where it takes $T$ time to answer $\{YES, ...
2 votes
2 answers
179 views

Analysis of QuickSort Expected Time Complexity: Without Counting the Number of Comparisons

While reading CLRS (4th ed.) regarding the analysis of the expected time for QuickSort, I encountered an alternative approach. The analysis involves the following steps: Given an array of size $n$, ...
0 votes
2 answers
139 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
0 answers
33 views

A probabilistic data structure based on flipping bits with probability $\frac{1}{2^x}$ for counting

How does this data structure work and what is its application? ...
0 votes
1 answer
18 views

When does augmented indexing become easy?

Consider the following problem in 2-party communication complexity, where Alice sends a single message to Bob who must compute the output. Alice gets as input a bit vector $X=(x_1,...,x_N)$, for some ...
0 votes
1 answer
29 views

What is the largest "allowed" seed for a PRNG to not give any extra power to a deterministic machine?

Suppose a polynomial time machine that has an access to a polynomially long string of bits independent on the input. On average, it's impossible to compress this string to a subpolynomially long ...
2 votes
0 answers
62 views

Borůvka's step in linear time

I am trying to understand this Expected linear time MST algorithm, and I have a problem in the implementation of the Borůvka's step. My problem is with the removal of duplicate edges between merged ...
2 votes
0 answers
24 views

Windowed LogLog/HyperLogLog algorithm to get a count of the cardinality of the set of the last $k$ elements?

LogLog/HyperLogLog provides a great way for estimating the cardinality of the set of $n$ objects. At its simplest, you hash all $n$ objects into binary strings, find the largest number of leading 0's $...
1 vote
0 answers
27 views

Runtime of randomization algorithm to find majority element in an array?

This is for the leetcode problem 169. Majority Element. Given an array of numbers, where there is a guarantee that there is a number that exists in the array greater than floor(n/2), one can find such ...
0 votes
1 answer
33 views

Optimal randomized algorithm for set cover

This cstheory.SE post gives various randomized approximation algorithms for the set cover problem. Is there a randomized algorithm (which runs in $\mathrm{poly}(n)$ time) for the set cover problem ...
0 votes
2 answers
1k views

Algorithmic challenge: generate a list of random non overlapping squares [closed]

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
2 answers
1k 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 ...
2 votes
0 answers
64 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 ...
1 vote
1 answer
46 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 ...
2 votes
0 answers
30 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 ...
1 vote
1 answer
96 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,...
0 votes
1 answer
388 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.
1 vote
0 answers
33 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 ...
1 vote
0 answers
19 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 ...
0 votes
0 answers
15 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 ...
0 votes
1 answer
24 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 ...
1 vote
1 answer
60 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 ...
0 votes
2 answers
57 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-)...
1 vote
1 answer
76 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 ...
1 vote
1 answer
203 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 ...
3 votes
1 answer
105 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 $...
1 vote
0 answers
57 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 ...
1 vote
0 answers
21 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 ...
1 vote
0 answers
57 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 ...
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, ...
3 votes
0 answers
44 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 ...
3 votes
1 answer
754 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 ...
0 votes
0 answers
85 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 ...
0 votes
0 answers
42 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_{\...
1 vote
0 answers
63 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 ...
4 votes
2 answers
79 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 ...
0 votes
1 answer
35 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 ...
3 votes
0 answers
57 views

Assuming $\mathsf{P=BPP}$ would it be possible to derandomize the verifier in Interactive Proof systems?

By the definition, in an Interactive Proof system the verifier is allowed to generate random numbers, which allows the omniscient prover to not fool it in the vast majority of cases for every problem ...
1 vote
2 answers
100 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.
2 votes
1 answer
75 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
1 answer
67 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 ...
1 vote
0 answers
60 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 ...
2 votes
1 answer
121 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 ...
1 vote
0 answers
24 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 ...
2 votes
0 answers
892 views

How much better are conservative updates for count-min sketch?

I've been reading about count-min sketch and I'm interested in the performance of this data structure when doing conservative updates. To my understanding from the Wikipedia article, conservative ...

1
2 3 4 5
9