Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [probabilistic-computation]

1
vote
1answer
48 views

Soft Truth Values in the PSL model

This might sound like a trivial question. But since am starting out with my research in an area that is entirely new to me, I would really appreciate it if someone could kindly elucidate what Soft ...
5
votes
1answer
142 views

Sets of solutions which it is hard to uniformly sample from, but easy to integrate functions over? (Or compute expectations over?)

I'm curious if there is a problem (e.g. something like perfect matchings on a given graph, number of solutions to a boolean equation, etc. for precise frameowork see JVV86) such that: 1) It is hard ...
3
votes
1answer
223 views

Can we efficiently distinguish between P and BPP?

Let's say algorithm $D$ distinguishes $BPP$ from $P$ if there exists a language $L \in BPP$ such that for all $A \in PTM$, $$D(\langle A\rangle) \in L \leftrightarrow D(\langle A \rangle) \notin L_A$$...
6
votes
1answer
709 views

Power of randomness vs. power of indefinite computation

I am writing a paragraph on the power of randomness, part of which I am trying to ground in theory of computation (I am no expert/researcher in this field). First off, I am aware that for ...
6
votes
0answers
214 views

Why is HyperLogLog (near-)optimal?

The original HyperLogLog paper claims that this probabilistic counting algorithm is "near-optimal". The relevant section of the paper reads: Clearly, maintaining $\epsilon$-approximate counts till ...
-2
votes
1answer
132 views

A curious statement in an old blog

In http://blog.computationalcomplexity.org/2009/08/finding-primes.html, a statement is added which reads "Oddly enough we would usually prefer a probabilistic over the deterministic method to find ...
1
vote
0answers
36 views

How to find a proper probabilistic formulation given the objective function terms?

I want to pose a problem as maximisation of MAP probability $P(X,Y|Z)$ and I know which terms I want to have in the objective function. However, I am unable to combine these terms to form a joint ...
4
votes
1answer
157 views

Probabilistic and quantum analog of $FP$ and $FNP$?

Is there any analog of the computational classes $FP$ and $FNP$ with probabilistic or quantum Turing machines? If so, what are the relation with other computational classes?
5
votes
2answers
137 views

Sampling from the binomial distribution with limited randomness and time

This is a basic question that I can't answer (it's not a homework assignment). A reference would be perfectly acceptable. Consider a $[0,k]$ valued random variable X distributed binomially so that: ...
5
votes
1answer
202 views

Is bounded-error probabilistic computation sensitive to transition types?

In the unbounded-error case, it is known that both realtime quantum and probabilistic finite automata can recognize some uncomputable languages if they are allowed to use arbitrary real numbers in ...