# Questions tagged [randomized-algorithms]

Questions about algorithms whose behaviour is determined not only by its input but also by a source of random numbers.

429 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
22 views

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$, ...
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 ...
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? ...
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 ...
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 ...
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 ...
24 views

1 vote
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
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
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 ...
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, ...
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 ...
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 ...
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 ...
42 views

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