Questions about (typically randomized) algorithms that can produce no or an incorrect answer with a certain probability.

learn more… | top users | synonyms

2
votes
1answer
31 views

Probabilistic algorithm with two-sided error

I am currently studying probabilistic algorithms and came across three major complexity classes: BPP: worst-case polynomial time, two-sided error RP: worst-case polynomial time, one-sided error ZPP: ...
2
votes
0answers
6 views

What is the meaning of the output weights of a Conditional Random Field (CRF) model?

Problem When train my linear chain CRF with annotated observations, I feed it with a number of sequences containing observation values and a "ground-truth" label for each observation. I'm currently ...
0
votes
3answers
54 views

Need for random bits in final PCP theorem statement

PCP theorem states that $$PCP(O(\log n),O(1))=NP.$$ Could we not run through $O(\log n)$ bits deterministically? Does PCP theorem statement mean any set of $O(\log n)$ random bits out of $2^{O(\log ...
3
votes
1answer
61 views

What do we know about $NP \cap co-NP$?

What do we need about the intersection of $NP$ and $co-NP$ apart from the fact that $P$ is a subset of it? (beyond what these answers here say, What do we know about NP ∩ co-NP and its relation to ...
2
votes
1answer
45 views

Can a probabilistic Turing Machine compute an uncomputable number?

Can a probabilistic Turing Machine compute an uncomputable number? My question probably does not make sense, but, that being the case, is there a reasonably simple formal explanation for it. I should ...
1
vote
0answers
23 views

What does ∇log mean in the Robbins-Montro algorithm?

The Robbins/Monro Algorithm is a type of stochastic optimization algorithm of the following form: (as mentioned in wikipedia) $$x_{n+1} - x_n = a_n(\alpha - N(x_n))$$ where $M(x) = \alpha$ is a ...
1
vote
1answer
33 views

Probability of having a log(n) length monotone subsequence in a random permutation of {1,…,n}

How can I compute the probability of having a $\log(n)$ length monotone consecutive subsequence in a random permutation of $\{1,...,n\}$. I wish to upperbound it with $1/n$.
2
votes
1answer
45 views

How do I prove a certain upper bound on the runtime of a probabilistic 2-SAT solver?

As a homework we had to prove a set of upper bounds on a given probabilistic algorithm to find a satisfying assignment for a satisfiable 2-CNF formula. The problem is reproduced below. I'm sorry for ...
-1
votes
1answer
66 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 ...
1
vote
1answer
72 views

Anagrams solver based on transitions probability

I have an English dictionary (text file) and the frequency of 2-grams, 3-grams and 4-grams as the beginning of each word. I need to write an algorithm that, with a given word, calculates the possible ...
1
vote
1answer
151 views

3/2 - Approximation probabilistic algorithm for MAX-3-COLOR

I have a textbook question here regarding Max-3-Coloring and need some assistance with it. I have searched for any type of information regarding it but haven't found anything substantial. Here is the ...
0
votes
1answer
32 views

How does these Probing time occurs for hash tables

I am having a hard time understanding the numbers of probing which might occur due to using different collision prevention method such as separate chaining, Linear Probing, double probing, which is ...
3
votes
1answer
76 views

What is With High Probability on Probabilistic Algorithms?

I watched lecture from MIT about Skip List. Overall, I understand the material, but one thing. What is "with-high-probability"? I really don't get it at all. I've seen the lecture notes but still ...
1
vote
0answers
30 views

Using “incremental algorithms” to find the $k^{th}$ smallest number

This is what I vaguely understand of what an "incremental algorithm" is - say one such for calculating the $k^{th}$ smallest number for a given sequence of elements $x_1, x_2,...,x_n$ then after the ...
2
votes
2answers
50 views

About sorting numbers in linear time

If one is given $n$ numbers picked uniformly at random from the interval $[0,1]$ then is it possible to sort them in linear time? It seems to me that some such method exists which uses binary ...
4
votes
1answer
62 views

Understanding the Sipser-Gacs-Lautemann theorem

The class $BPP$ contains all the languages decided by a probabilistic Turing machine in polynomial time with probability of success more that 2/3 for every input. The class $\Sigma^p_2$ contains all ...
5
votes
2answers
128 views

Choosing error rates for probabilistic algorithms

Probabilistic algorithms often have a parameter that allows one to tune the error rate, typically by running the algorithm repeatedly. This often gives an error rate of something like $2^{-k}$ for $k$ ...
9
votes
1answer
131 views

Can an NP-hard problem be polynomial on average?

I'm wondering if there are any $NP$-hard problems which are ``polynomial" in the average case. I think there are two ways to interpret this? If $P \neq NP$, can there be an algorithm solving an ...
8
votes
0answers
117 views

Would $\sf RP = NP$ imply $\sf NP = coNP$?

If $\sf RP = NP$ then the hierarchy collapses to its second level (by the Karp-Lipton theorem). But what about $\sf NP$ and $\sf coNP$? I tried to prove that $\sf BPP$ is contained in $\sf NP$ (the ...
8
votes
1answer
128 views

Probability Distributions and Computational Complexity

This question is about the intersection of probability theory and computational complexity. One key observation is that some distributions are easier to generate than others. For example, the problem ...
2
votes
1answer
60 views

Bloom filter variant

I've been playing around with a simple probabilistic data structure which is very similar to a Bloom filter. Where a Bloom filter would use $k$ independent hash functions to choose $k$ of the $m$ bits ...
2
votes
1answer
232 views

Expected maximum bin load, for balls in bins with equal number of balls and bins [closed]

Suppose we have $n$ balls and $n$ bins. We put the balls into the bins randomly. If we count the maximum number of balls in any bin, the expected value of this is $\Theta(\ln n/\ln\ln n)$. How can we ...
2
votes
1answer
71 views

Are there any practical differences between a Turing machine with a PRNG and a probabilistic Turing machine?

Say I plugged in a hardware true-random number generator (TRNG) to my computer, then wrote programs with output that depends on the TRNG's output. Can it do anything non-trivial that a Turing machine ...
8
votes
1answer
163 views

Proof of PCP theorem

I am reading the proof of PCP theorem in Proof Verication and Hardness of Approximation Problems. The following paragraph appears in section 3 (page 4), "Outline of the Proof of the Main Theorem". ...
1
vote
0answers
92 views

PageRank and EigenTrust: How small should epsilon be?

For probabilistic algorithms such as PageRank and EigenTrust, the stopping case is given as $|R_{t+1} - R_{t}| < \epsilon$ (i.e. convergence is assumed). Neither the papers on EigenTrust or ...
1
vote
1answer
148 views

How are Bayesian Nets, Hidden Markov Chains, Conditional Random Fields and Neural Nets related?

I am having an AI exam in two weeks, and I am still figuring out certain concepts and ideas, related to Bayesian Nets, Hidden Markov Chains, Conditional Random Fields and Neural Nets (yes it is all ...
5
votes
1answer
95 views

Possible to construct a probabilistic halting problem solver?

I'm a CS undergrad so my math/CS knowledge is not that deep so please correct me if my premise is flawed or I have made some incorrect assumptions. So I was thinking, much in the way that some ...
6
votes
0answers
94 views

Complexity class for probabilistic approximation algorithms with bounded error

What's the name of a complexity class of optimization problems that have "bounded error probabilistic approximation algorithms"? Bounded error probabilistic version of APX (as BPP is bounded error ...
5
votes
1answer
119 views

Deleting in Bloom Filters

I know that standard Bloom Filters only have operations like inserting elements and checking if an element belongs to filter, but are also some modification of Bloom filters which enable a delete ...
1
vote
1answer
96 views

What would be a decent threshold for classification problem?

I'm using machine-learning algorithms to solve binary classification problem (i.e. classification can be 'good' or 'bad'). I'm using SVM based algorithms, ...
2
votes
1answer
36 views

finding a an object with constant velocity on an infinite grid in discrete time steps

Assume you have an object moving at a constant velocity(up, down, left, right) in a grid. You have unlimited resources (memory, time). At any given time step in the grid, you can "guess" the location ...
3
votes
2answers
332 views

why not just use a random number generator as a hash function?

I guess at the heart of this is that I don't really understand hash functions. One article says any function mapping objects to an object of fixed size: A hash function usually means a function ...
7
votes
3answers
232 views

Computer science problems related to music?

Are there any CS problems, preferably open, that are related to music or musical theory somehow? I would think of problem with musical notation but also probabilities when randomizing according to a ...
4
votes
3answers
285 views

Why do Bloom filters work?

Let's say I am using Bloom filters to create a function to check if a word exists in a document or not. If I pick a hash function to fill out a bit bucket for all words in my document. Then if for a ...
6
votes
2answers
336 views

Bloom filter and perfect hashing

A Bloom filter uses a hash function to test membership in a given set $S$, by checking if an item is present of not at the specified position. To mitigate the effect of hash collision, multiple ...
4
votes
0answers
49 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
78 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
714 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 ...
7
votes
2answers
173 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
45 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
56 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 ...
8
votes
1answer
352 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
135 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
2answers
547 views

Bloom Filter for 208 million URLs

I need to create a bloom filter of 208 million URLs. What would be a good choice of bit vector size and number of hash functions? I tried a bit vector of size 1 GB and 4 hash functions, but it ...
4
votes
1answer
124 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
129 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
132 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, ...
7
votes
1answer
333 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
117 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 ...
4
votes
2answers
147 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, ...