Questions about (typically randomized) algorithms that can produce no or an incorrect answer with a certain probability.
4
votes
0answers
36 views
Signal-based Search
This is more of an open-ended information question, but to make it concrete, here's an example problem I have thought up:
Consider an $N\times N$ grid, $N$ odd, and consider that a single chunk of ...
1
vote
1answer
45 views
How to sample uniformly from a stream of elements, some of which are unsuited?
I get values $x_t$ in an online fashion and want to buy "good" ones, where "good" means that some measure $P(x_t) >T$. Consider the following simple algorithm.
...
1
vote
1answer
54 views
How to get expected running time of hash table?
If I have a hash table of 1000 slots, and I have an array of n numbers. I want to check if there are any repeats in the array of n numbers. The best way to do this that I can think of is storing it in ...
6
votes
2answers
98 views
Are probabilistic search data structures useful?
A SkipList provides the same $O(\log n)$ bounds for search as a balanced tree with the advantage that rebalancing isn't necessary. Since the SkipList is constructed using random coin flips, these ...
2
votes
0answers
39 views
Approximate target subset by intersecting other subsets
Let $S$ be a finite set of integers (this set contains about 200000 elements). Let $T \subset S$ be a particular subset of $S$ called target. $S$ keeps growing. So does $T$. Each new element of $S$ ...
1
vote
1answer
34 views
BPP clarification
I know that $\sf BPP[2/3,1/3]= BPP[\alpha,\beta]$ when $\alpha\lt\beta$, but I read something on Wikipedia which got me confused:
In practice, an error probability of $1/3$ might not be ...
7
votes
1answer
175 views
Prove or refute: BPP(0.90,0.95) = BPP
I'd really like your help with the proving or refuting the following claim: $BPP(0.90,0.95)=BPP$. In computational complexity theory, BPP, which stands for bounded-error probabilistic polynomial time ...
6
votes
1answer
97 views
BPP search: what does boosting correctness entail?
It is not really clear to me, how and if I can do boosting for correctness (or error reduction) on a BPP (bounded-error probabilistic polynomial-time) search problem. Can anyone of you explain me how ...
3
votes
1answer
56 views
What is known about coRL and RL?
Wondering about any known relations between $\mathsf{RL}$ complexity class (one sided error with logarithmic space) and its complementary class, $\mathsf{coRL}$.
Are they the same class?
What are ...
5
votes
2answers
93 views
An edge that connects more than two nodes in a graph?
Is there a way to create a single edge on a graph that connects 3 or more nodes? For example, let's say that the probability of Y occurring after X is 0.1, and the probability of Z occurring after Y ...
6
votes
1answer
111 views
Probabilistic poly-time machine always halts on all inputs?
In the usual definition of probabilistic poly-time machine it is said that the machine halts in polynomial time for all inputs.
Is the intention really to say that the machine halts for all inputs, ...
6
votes
1answer
118 views
Probabilistic test of matrix multiplication with one-sided error
Given three matrices $A, B,C \in \mathbb{Z}^{n \times n}$ we want to test whether $AB \neq C$. Assume that the arithmetic operations $+$ and $-$ take constant time when applied to numbers from ...
3
votes
1answer
106 views
Randomized String Searching
I need to detect whether a binary pattern $P$ of length $m$ occurs in a binary text $T$ of length $n$ where $m < n$.
I want to state an algorithm that runs in time $O(n)$ where we assume that ...
3
votes
2answers
112 views
Is the number of coin tosses of a probabilistic Turing machine a Blum complexity measure?
I read that the number of coin tosses of a probabilistic Turing machine (PTM) is not a Blum complexity measure. Why?
Clarification:
Note that since the execution of the machine is not deterministic, ...
