# Questions tagged [probabilistic-computation]

The tag has no usage guidance.

12 questions
20 views

### Determine the error-probability of biased coin tosses using chernoff-bounds

Let's assume we have a biased coin with probabilities $\frac{4}{5}$ and $\frac{1}{5}$ and we don't know to which event (head or tail) the probabilities belong to. But we want to decide it by majority ...
156 views

### If I know pretty well '(a,b)', I know pretty well 'a', or 'b', or 'a xor b'

I've a quite simple problem: let's imagine I have a couple of bits $(a,b) \in \{0,1\}^2$ sampled uniformly at random. Then, I give a function of these bits $f(a,b)$ (it can be any function, including ...
53 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 ...
143 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 ...
227 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$$...
712 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 ...
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 ...
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 ...
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 ...
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?
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: ...