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

learn more… | top users | synonyms (1)

0
votes
1answer
52 views

What is a stateful computation?

I am reading about a specific field of probabilistic programming, and trying to understand what the term "stateful computation" means. See: ...
1
vote
0answers
13 views

What use does the predictor stage in a particle filter have?

Im a bit confused about the particle filter. I understand the generic particle filter algorithm but in some literature say particle filter has predictor stage which is not mentioned in the generic ...
-1
votes
0answers
38 views

Conditions on randomized reductions

Supposing we have a problem $\Pi$. Suppose $\Pi$ has a randomized reduction from $\mathsf{3SAT}$ but there is no deterministic reduction then it is clear $\mathsf{NP}\neq\mathsf{P}$. My query is ...
8
votes
3answers
271 views

Isn't polynomial identity testing over arithmetic *expressions* trivial?

Polynomial identity testing is the standard example of a problem known to be in co-RP but not known to be in P. Over arithmetic circuits, it does indeed seem hard, since the degree of the polynomial ...
2
votes
1answer
27 views

Methods for proving upper bound on a-approximiation algorithms? [closed]

I'm dealing with some simple randomized and on-line algorithms, both kind produce some lower/upper bound on quality of the output instance. For example, there's a simple randomized algorithm for the ...
6
votes
3answers
116 views

Is there a random shuffle algorithm using only true /false?

Is there a way to randomly shuffle an array using only a source of random boolean values? SO to clarify, shuffle using true /false only, and not integers or decimals. For this question, I'm ...
3
votes
2answers
75 views

Shuffling a file on disk using $O(\log n)$ memory

How do you shuffle the bytes in a file (bytes for simplicity) on disk with a small, $O(\log n)$, amount of memory and preferably in-place? If the file had size $2^m$, then we can first split the file ...
2
votes
2answers
90 views

What is the trick used in skip lists to minimize $k + \frac{n}{k}$?

I was reviewing skip lists and the first step is to have two lists, the bottom one ($L_0$) of length n and the top one ($L_1$) of size k. Usually one traverses the "express line" (i.e. the top lane ...
1
vote
2answers
61 views

Is shuffling a set of items after popping an item meaningfully more random than doing it once, before starting?

I'm working on a thing to randomly assign people into a shift. There's mostly 2 sets of people, "free" and "assigned". Is shuffling the "free" set after assigning an employee meaningfully more random ...
7
votes
2answers
123 views

Is there any efficient algorithm for primality testing for numbers that are of the form $4k+3$ using the square root function?

I was reading CLRS and it asked to show that if $p$ is a prime of the form $4k+3$ and $a$ was a quadratic residue, then $a^{k+1}$ is a square root (one can also easily show that $a^{-k}$ is a square ...
3
votes
1answer
49 views

Optimal pivot selection for quick-sort

The actual runtime of applying quick-sort to an integer array heavily relies on the choice of pivots. It is well known that picking a random pivot does not work as good as taking the median of three, ...
3
votes
1answer
24 views

Deamortizing a Las-Vegas randomized algorithm

Deamortization refers to the process of converting an algorithm with an amortized bound into one with a worst-case bound. For example, assuming you need to find the median of an array once every $n$ ...
4
votes
0answers
150 views

Data structures for ordering noisy data

In a certain robotics application, I encountered a problem in which we need to determine the order of positions of several robots on $\mathbb{R}$. Each measurement that we take of robot positions is ...
0
votes
0answers
13 views

constant step-size assumption in non-asymptotic analysis of stochastic gradient descent

I have come across some non-asymptotic analysis of stochastic gradient descent algorithm (works of FRancis Bach https://hal.archives-ouvertes.fr/file/index/docid/831977/filename/newsto_hal.pdf) most ...
6
votes
2answers
71 views

Correctness of Freivald algorithm for checking matrix multiplication, why is the probability of checking $AB \neq C$ at least 1/2?

I am going to consider Freivald's algorithm in the field mod 2. So in this algorithm we want to check wether $$AB = C$$ and be correct with high probability. The algorithm choose a random $r$ ...
1
vote
1answer
64 views

How does one compute the probability of a false-based Monte Carlo algorithm being correct rigorously?

Recall that a false-biased Monte Carlo (MC) algorithm is always correct when it returns false for some decision problem i.e. it has a one sided error and its always correct on NO instances. Assume ...
4
votes
1answer
168 views

Choosing a random bit from a bitmap

Since, I don't have strong algorithmic background my question may sound a litlle odd. Please correct me, if so. I have quite a large bitmap (~100 Million bits) (e.g. ...
6
votes
1answer
101 views

Sorting an unordered pile of items into drawers with minimal drawer movements

A while ago, I was doing my laundry late at night. When I brought my laundry back to my dorm, I started to put it away. My wardrobe is set up as follows: My drawers are categorized by the type of ...
0
votes
1answer
128 views

Showing that Karger's contraction algorithm has exponentially small probability of finding an optimum

I'm stuck with one of my homework exercises: Consider the following variant of Karger’s algorithm for finding a minimum s-t cut, i.e., a minimum cut separating two specific given nodes s and t: ...
2
votes
0answers
44 views

Using the random forest algorithm to predict vectors [duplicate]

I know this might sound like a newbie question, but bear with me. I have read a paper where researchers use a random forest to predict species distribution, but in their study, they only predict a ...
1
vote
1answer
40 views

Proving simple bound on coupon collector

I came across this paper which gives bounds on coupon colloector problem. Page 451 contains a table where reference to U1 is given as 'folklore'. I presume this is trivial to follow from the ...
6
votes
1answer
63 views

Why is the probability used in the definition of RP complexity classes, arbitrary?

I was looking at the following wikipedia article on the RP complexity class: https://en.wikipedia.org/wiki/RP_(complexity) In its definition it states: If the correct answer is NO then it always ...
1
vote
1answer
44 views

Finding the kth smallest element of an array using DAC [closed]

I'm trying to find the $k^{th}$ smallest element of an array by using Randomized Quicksort, But below code giving erroneous result can anybody help. ...
0
votes
0answers
8 views

Find all pairs of matching elements in two arrays [duplicate]

I have two arrays A & B, each with an element from one that corresponds to the other (for each a in A there is a b in B it corresponds to). And I don't want to brute-force check them all in ...
0
votes
1answer
43 views

How to “properly” handle incorrect values in a random walk?

I'm performing a simple one dimensional walk to create sample interest rates. Whilst I know there are lots of options for encouraging values to oscillate around a mean etc. I'm yet to find a simple ...
1
vote
1answer
56 views

How to simulate this randomized “finite” sum? [closed]

Consider the the Geometric Brownian motion $\qquad dX_t=\mu X_t dt+\sigma X_t dW_t$, with $X_0=1$, $\mu=0.2$, and $\sigma=0.30$. for each $n=1,2,3,..$ let $h_n=1/n$, and let $X^n_n$ be the final ...
1
vote
1answer
69 views

How would you implement truly random hash functions in practice?

Suppose that $[U] = [0,...,U-1]$ is the universe from which all elements will be taken, and $A$ a hash table of size $m$. A hash function $h:[U]\rightarrow[m]$ is truly random if For any set of ...
4
votes
2answers
168 views

Minimal number of attempts at a multiple choice exam needed in order to pass, without any prior knowledge

A test is consisted of $N$ multiple choice questions, each has $k$ possible answers. A test solution is the sequence of answers $S\in[k]^N$. Given is a black box which receives a solution as input ...
0
votes
1answer
70 views

Random uniform sampling of position restricted permutations

Is there any efficient algorithm which is able to generate nearly uniform samples of permutations in case of position restrictions? Consider $N \times N$ restriction matrices $R$, that is matrices ...
3
votes
1answer
55 views

How to cluster similar objects into fixed size groups?

I have $n$ people each of which can meet on certain days of the week. I want to group them into $\frac{n}{k}$ groups of size $k$ such that all people in a group can meet on a day. eg - Suppose there ...
2
votes
1answer
52 views

Can a relatively small subset of random numbers be permuted and reused and still guarantee good expected running time for an algorithm like quicksort?

So this is sort of a general question but I'll limit the discussion to randomized quicksort to make it clear. Suppose generating "true" random bits is hard, e.g. because it requires measuring ...
0
votes
0answers
10 views

Removing the acceptance error from AM

Typically the AM class is defined with error upper bound of 1/3 for deciding both the situations of the membership question being true or false. But curiously enough for the situations when the ...
2
votes
1answer
51 views

How does derandomization of 3SAT work via conditional expectations?

Given a single SAT clause with its 3 literals coming from 3 different variables it is obvious that a random assignment of values will satisfy it with probability 7/8 But I do not understand how ...
3
votes
1answer
57 views

What is the rigorous definition of an efficient algorithm that $\epsilon-refutes$ random 3CNF formulas

I recently asked a similar What does "refuting random 3CNF" formulas mean?, however, I'd like to address it in a more mathematically precise setting. In that paper, on page 5, it talks ...
5
votes
1answer
136 views

Generate a random graph with geometrical degree distribution

I'm working on graph generation, trying to implement the RT-nested-Smallworld network model described in this paper. We are talking about generating an undirected graph in a slightly different way ...
2
votes
1answer
30 views

How does one change the probability bounds in probabilistic complexity classes without changing the class?

I see this theorem whose proof is not clear to me : "Let $L \subseteq \{0,1\}^*$ be a language and suppose that there exists a polynomial time PTM M such that for every $x \in \{0,1\}^*$ and $Pr[ ...
2
votes
1answer
30 views

Can one use the PCP theorem to prove correctness of deternimistic algorithms?

I am thinking of the equality "PCP(O(log(n)),0) = P" Say I have a deterministic polynomial time algorithm $A$ whose correctness I can't prove immediately. But say I create a probabilistic version of ...
3
votes
1answer
79 views

Analysis of sorting Algorithm with probably wrong comparator? [duplicate]

It is an interesting question from an Interview, I failed it. An array has $n$ different elements $[A_1, A_2, \ldots, A_n]$ (random order). We have a comparator $C$, but it has a probability p to ...
0
votes
1answer
31 views

Approximating the set of witnesses of a BPP algorithm

Let $\mathcal{A}$ be a randomized algorithm that decides a language $\mathcal{L}$. For each input $x\in\mathcal{L}$, we define the set of witnesses of $x$ as $W(\mathcal{A},x) = ...
4
votes
1answer
122 views

Amplifying the correctness of $\mathsf{RP}$ algorithms using expander graphs

A graph $G = (V, E)$ is called an $(n, d, \varepsilon)$-expander if the graph has $n$ vertices, maximum degree $d$, and satisfies the following expansion property: for every subset $W\subset V$ such ...
1
vote
2answers
92 views

About being able to sample a permutation of a finite set uniformly at random [closed]

I was looking at this question. So if I understand the above discussion right then it concludes that if say one had access to an oracle which can uniformly at random sample from a finite set then ...
0
votes
1answer
30 views

Complexity bound on $RP^{RP}$

This is a homework question, I'm wondering if anyone could help. Recall $RP$ is the set of languages recognized by randomized algorithms in polynomial time. The question is given an algorithm in ...
7
votes
1answer
101 views

Finding a maximal independent set in parallel

On a graph $G(V,E)$, we do the following process: Initially, all nodes in $V$ are uncolored. While there are uncolored nodes in $V$, each uncolored node does the following: Selects a random real ...
2
votes
0answers
99 views

Marking nodes of a complete binary tree

Suppose that I have a binary tree with $N = 2^h - 1$ nodes, initially all nodes are unmarked Over time via this process nodes became marked. Suppose that nodes have unique identifiers in range of ...
2
votes
1answer
36 views

Does randomness makes exponential difference?

Schwartz–Zippel lemma can solve the polynomial identity testing in expected poly-time. As far as I know, there is no deterministic poly-time algorithm for the problem, but we do not know if the ...
-1
votes
1answer
108 views

Understanding polynomial equality testing using randomized algorithms

A file is downloaded from a server and is represented as $a = \{0, 1\}^n$. The server has that file as $b = \{0, 1\}^n$. We want to ensure a degree of certainty that $a=b$, using a randomized ...
14
votes
1answer
298 views

Lost in a “one directional” concert

You and a friend lost each other on the line to a concert, and neither is sure which of you is further ahead. Formally, each is at some integer coordinate and may only walk towards a higher coordinate ...
2
votes
1answer
28 views

Using all the entropy in an biased bit

Suppose we have $n$ bits of random-looking data, and we want to encode it in such a way that instead of 1/2 the bits being 1's, we have (say) 3/4 the bits being 1's. The entropy of each bit in the new ...
1
vote
0answers
81 views

Proof of Randomized Self-Adjusting Binary Search Tree

I developed a randomized self-adjusting binary search tree years ago, which I called a shuffle tree, but was unable to ever have it published because my proofs were rejected (with little explanation). ...
2
votes
1answer
176 views

Turn biased random number generator into uniform

I'm looking at a problem in the book Introduction to Algorithms by Cormen et al. It says that if we are given a random number generator rand() which satisfies the distribution: $P(X = 0) = ...