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
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+...
Mahyar's user avatar
  • 81
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 ...
sheesymcdeezy's user avatar
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? ...
Mason Rashford's user avatar
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 ...
CCStudent's user avatar
  • 111
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$, ...
Mason Rashford's user avatar
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 ...
Nathaniel's user avatar
  • 15.5k
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 ...
rus9384's user avatar
  • 1,632
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 $...
chausies's user avatar
  • 532
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 ...
Shisui's user avatar
  • 121
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 ...
user avatar
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 ...
Jungle's user avatar
  • 21
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 ...
Gabi G's user avatar
  • 325
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 ...
Theo's user avatar
  • 21
1 vote
1 answer
95 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,...
SlowerPhoton's user avatar
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.
jon doyle's user avatar
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 ...
Duc-Anh DO's user avatar
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 ...
asdf's user avatar
  • 237
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 ...
RT.'s user avatar
  • 101
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 ...
Helpful's user avatar
  • 103
1 vote
1 answer
59 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 ...
Angstrom's user avatar
  • 113
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-)...
proof-of-correctness's user avatar
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 ...
Jake's user avatar
  • 378
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 ...
ConScience's user avatar
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 $...
user13062187's user avatar
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 ...
Lightsong's user avatar
  • 239
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 ...
Carlo Moretti's user avatar
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 ...
Krish Singal's user avatar
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 ...
user avatar
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, ...
Keio203's user avatar
  • 257
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 ...
Alonso Montero's user avatar
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 ...
programonkey's user avatar
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 ...
Keio203's user avatar
  • 257
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 ...
joeren1020's user avatar
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_{\...
Rma's user avatar
  • 127
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 ...
wondering_wandering's user avatar
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 ...
Jerry's user avatar
  • 101
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 ...
I have a question's user avatar
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.
Jxb's user avatar
  • 318
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 ...
Aris Konstantinidis's user avatar
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 ...
kostger's user avatar
  • 37
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 ...
DenLilleMand's user avatar
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 ...
Azuresonance's user avatar
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 ...
Er7's user avatar
  • 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 ...
NiRvanA's user avatar
  • 159
1 vote
0 answers
24 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 ...
Gabriel Buendia's user avatar
0 votes
1 answer
24 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 ...
Daniel Donnelly's user avatar
0 votes
1 answer
47 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 ...
Chao Somnium's user avatar
0 votes
1 answer
92 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 ...
José Duarte de Azevedo e Cunha's user avatar
1 vote
1 answer
327 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 : ...
Nameless's user avatar
  • 173
0 votes
1 answer
64 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 ...
user918212's user avatar

1
2 3 4 5
9