Questions tagged [probabilistic-algorithms]
Questions about (typically randomized) algorithms that can produce no or an incorrect answer with a certain probability.
53
questions with no upvoted or accepted answers
11
votes
0
answers
396
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".
...
- 3,627
10
votes
0
answers
156
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 ...
- 560
4
votes
0
answers
26
views
Error correcting codes for transmitting a real value $x$ in [0,1], minimizing the reconstructed distance to the original $x$
I have been thinking a bit about error correcting codes, in particular the following problem:
Consider the problem of transmitting a single real number $x \in [0,1]$ over a lossy connection, where ...
- 41
4
votes
0
answers
101
views
Distribution of pointer keys in a Skip-list node
Suppose we have a list of $N$ keys where the distribution of keys follows $f(x)$.
We construct a skip list over the keys.
Now if I pick a key (e.g. 31 in the ...
- 121
4
votes
0
answers
65
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 ...
- 378
3
votes
0
answers
122
views
Verify if array is orthogonal
Orthogonal arrays often appear in probabilistic algorithms. They can be efficiently constructed from, e.g., BCH codes.
But is there an efficient algorithm that can verify if an array is orthogonal? I ...
- 125
3
votes
0
answers
68
views
Noisy sorter: optimal algorithm
Given $n$ elements $x_1,\dots, x_n$, and algorithm $A$ which outputs $(r_1,\dots, r_n)=A(x_1,\dots, x_n)$, we say $A$ is $\epsilon$-sorting the list if $rank(x_i) \in (r_i-n\epsilon, r_i+ n\epsilon) $ ...
- 531
3
votes
0
answers
93
views
Is the definition of $\textbf{BPP}$ robust for doubly exponential small (or even smaller) error?
$\textbf{BPP}$ is usually defined in terms of probabilistic polynomial-time TMs which have an error probability of at most $\frac{1}{3}$. Furthermore, using the Chernoff bound it can be proven that ...
- 4,959
3
votes
0
answers
92
views
Probability of a double cycle in cuckoo graph
I have read Chater 17. Balanced Allocations and
Cuckoo Hashing in Mitzenmacher. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis and got ...
- 285
2
votes
0
answers
136
views
Correctness of Karger's min-cut Algorithm
tl;dr in the analysis for Karger's min-cut, the probability of an edge being in the min-cut in the $j$th iteration, $\frac{k}{0.5k(n-j)}$, neglects the fact that all the edges between the two ...
- 151
2
votes
0
answers
102
views
Stochastic Computing: What is "Bundle Processing"?
I'm puzzled by a short paragraph found in the article on Stochastic Processing in Wikipedia. There it says:
Bundle Processing involves sending a fixed number of bits instead of a stream. One of the ...
- 141
2
votes
0
answers
66
views
Box labelling game
I have a box of stickers. It contains $n$ stickers. Each sticker is labelled with a different number from $\mathbb{Z}$.
I have infinite supply of boxes.
Box labelling game: I pick a random sticker ...
- 1,731
2
votes
0
answers
168
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 ...
- 121
2
votes
0
answers
64
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$ ...
- 121
1
vote
0
answers
33
views
How can $R_HL$ differ from $RL$?
https://complexityzoo.net/Complexity_Zoo:R
RL: Randomized Logarithmic-Space Has the same relation to L as RP does
to P. The randomized machine must halt with probability 1 on any
input. It must also ...
- 239
1
vote
0
answers
46
views
Combine Las Vegas and Montecarlo probabilistic algorithms to improve chance of finding correct answer
Let's say that I have a Las Vegas algorithm for a given problem (whose answer is true/false for simplicity) with a chance of ...
- 239
1
vote
0
answers
39
views
Probability that an Algorithm Deviates from Its Behaviour after Multiple Rewindings
I do have a seemingly fundamental question that I somehow struggle to intuitively make sense of.
Setting:
Let us consider a randomized algorithm $R$ that has $t$ steps. In each step, it is fed with ...
- 11
1
vote
1
answer
68
views
Weighted sample of ~k elements from array in O(n) time?
I have an array $a$ with $n$ elements, all of which have an associated weight. For example:
$a = \{ (A,2), (B,5), (C,9), ..., (Z,1) \}$, such that element $A$ has weight $w_A=2$, element $B$ has ...
- 11
1
vote
0
answers
24
views
What are practical applications for markovs algorithm(string rewriting systems)
:)
Currently I am browsing through the internet on the hunt for a topic for my bachelors thesis. Whilst being on Reddit I discovered an interesting repo (https://github.com/mxgmn/MarkovJunior) for a ...
- 11
1
vote
0
answers
19
views
Usage cases of AMS algorithm
This question is about the second frequency algorithm described in N. Alon, T. Matias, and M. Szegedy The space complexity of approximating the frequency moments. Specifically, I am asking about the ...
- 125
1
vote
0
answers
25
views
RP with very small error = P
I was asked to show the equality $ RP(1 − 2^{-2^{n}}) = P $, which seems wrong to me (?).
The $ \supseteq $ direction is obvious, and I want to show the other direction.
My first intuition was to run ...
- 161
1
vote
1
answer
78
views
Does the reliability of polynomial hashing depend on whether the modulus is prime, for coprime base and modulus?
A polynomial hash of a string $s$ with base $b$ and modulus $M$ is defined as
$$
H(s) = (s_0 + s_1 b + s_2 b^2 + \dots + s_{n-1} b^{n-1}) \mod M.
$$
I have proven (and this is quite obvious) that ...
- 11
1
vote
0
answers
19
views
Distribution independence property testing
I have been reading the proof in the following paper, and I am unable to understand some parts in the proof. This paper shows that a distribution $A$ over $[n]\times[m]$, $n\geq m$, can be $\epsilon$-...
- 11
1
vote
0
answers
36
views
Computing a threshold function
Let $f$ be any function from $\{0, 1\}^{n}$ to $\{-1, 1\}$. For a given $f$, let us define another function $g_f$ as
\begin{equation}
g_f(x) = \sum_{x \in \{0, 1\}^{n}} f(x).
\end{equation}
Let us be ...
- 219
1
vote
0
answers
761
views
kth smallest element using Randomized select
I have recently started studying Randomized algorithms on my own. I am refering to Rajiv motwani - randomized algorithms book.
Objective - find kth smallest element using radomized select in $O(n^\...
1
vote
1
answer
147
views
Calculating a jackpot winner based on probabilities
Imagine a jackpot where users can bet as much as they want, and each bet increases their winning chance. Given a roll [0-100], how would you calculate the winner?
...
- 111
1
vote
0
answers
33
views
Distributional error probability of deterministic algorithm implies error probability of randomized algorithm?
Consider some problem $P$ and let's assume we sample the problem instance u.a.r. from some set $I$.
Let $p$ be a lower bound on the distributional error of a deterministic algorithm on $I$, i.e., ...
1
vote
0
answers
542
views
Perfect Completeness of AM protocols?
I understand the idea behind making a MA protocol perfectly complete. In a MA protocol, Merlin sends a proof $\pi$ which Arthur checks with his machine $V$ by plugging in some random bits $r$ such ...
1
vote
0
answers
35
views
Probability lower bound on a double cycle on two vertices in random cuckoo graph
I have read Chater 17. Balanced Allocations and
Cuckoo Hashing in Mitzenmacher. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis and got ...
- 285
1
vote
0
answers
22
views
Extracting room voids in a house
I am looking to create a series of closed volumes that represent the empty voids made by rooms in a house.
In order to do this, all I have is the raw geometry of all the elements that encapsulate ...
- 111
1
vote
0
answers
37
views
Probabilistic linebreaking algorithm
I'm currently trying to implement this paper. Based on a bayesian network, the paper stays unclear about how to ultimately use it's content ("straightforward inference"). But after a lot of ...
lprndn
1
vote
0
answers
59
views
Finding subset of integer summing up above threshold
Given an array $|A|=n$ of integers, and $m,k \in \mathbb{N}$, I want to find $m$ elements $a_{i_1},...,a_{i_m}$ of $A$ such that $\sum a_{ij} \geq k$ (repitions allowd), or determine that no such ...
- 101
1
vote
0
answers
142
views
distinguishing two biased coins
I had a simple probability question: suppose we have two coins, coin 1 is heads with probability $= 10\epsilon$ and coin 2 is heads with probability $=\epsilon/10$. Given an unknown coin, how many ...
- 11
1
vote
0
answers
91
views
How to select cuckoo filter parameters?
If I want a cuckoo filter to hold a dataset with N entries with a target false positive rate of ϵ, how do I select the sizes for the table, bucket, and fingerprint parameters?
- 169
1
vote
0
answers
44
views
What's the polynomial involved in the PCP theorem?
Statements of the PCP theorem always speak of a proof of length $poly(n)$. But what polynomial is that exactly? Could you actually construct the PCP for some mathematical fact in real life?
- 1,048
1
vote
0
answers
33
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 ...
- 253
1
vote
0
answers
84
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 ...
- 97
1
vote
0
answers
493
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 ...
- 111
1
vote
1
answer
60
views
Are there efficient probabilistic multiplication algorithms that use O(n log n) gates?
Recently Harvey and Hoeven published a paper proving that integer multiplication can be performed using at most O(n log n) operations. This algorithm is theoretically interesting, but in practice ...
- 5,772
0
votes
0
answers
55
views
PP and the most significant bit of functions in #P
I've found the following sentence (and some variants) in a lot of places, namely in Arora and Barak's Computational Complexity: A Modern Approach.
Intuitively, PP corresponds to computing the most ...
- 403
0
votes
0
answers
34
views
Rank of random binary string with Bernoulli distribution
For $1\ge p_1 \ge \dots \ge p_n \ge 0$, and for $i\in[n]$ draw $k$ iid binary strings with $m$ length:
$$X_{i,1},\dots,X_{i,k}\stackrel{iid}{\sim} \text{Bernoulli}(p_i)^m.$$
Viewing these binary ...
- 531
0
votes
0
answers
112
views
Techniques to prove lower bounds on randomized algorithms
I am interested in proving lower bounds for AM-like languages. The usual techniques for lower bounds in non-probabilistic machines don't work for probabilistic machines.
Intuitively, when I think ...
- 11.4k
0
votes
1
answer
53
views
How to implement conditional probability distribution on set-valued Random Variables
I'm trying to implement conditional probability distribution when the events of two RVs are sets. If I try to extrapolate concepts from real or categorical variables to sets things become confusing ...
- 1
0
votes
0
answers
56
views
Hashing algorithm which minimizes distribution
Consider applications A1, A2 .. AN having properties P11, P12,... PN1, PN2.. Also consider buckets ...
- 101
0
votes
0
answers
33
views
Chernoff Bounds (upper tail)
For the proof of Chernoff Bounds (upper tail) we suppose δ<2e−1 .
Like in this paper ([see this link ]) 1. Can you tell me why ?
- 17
0
votes
0
answers
74
views
Prove an estimator
Consider an undirected graph $G=(V,E)$ representing the social network of friendship/trust between students. We would like to form teams of three students that know each other. The question is to ...
- 17
0
votes
0
answers
17
views
What is the probability that an expanding bipartite graph exists with the property, |V1|=|V2|?
I want to find a bound on the above problem, and show that a random graph has a positive probability of being an expanding bipartite with the property, |V1|=|V2|. I am not getting, where should I ...
- 129
0
votes
0
answers
38
views
Construction of hash function with a given distribution
Two questions about the construction of a hash function:
Let $U = \{u_1,...,u_n\}$ be a set of size $n$, and suppose that one is interested in a function $h\colon U \rightarrow [0,1]$ such that $h$ "...
- 101
0
votes
0
answers
42
views
PCP variant in P with non 0 randomness and polynomial proof
I am trying to show that a particular language $L$ in PCP(log,q) is also in P. The PCP protocol works as follows: log many random bits and checks at q positions in a polynomial length proof. The ...
- 313
0
votes
0
answers
54
views
Show that if language belongs to $BPP$ then also similar language belgons to $QP$
Prove that for each arbitrary set of natural numbers $A$ we have:
$$\{bin(n) | n\in A\} \in BPP \to \{0^n|n\in A\}\in QP$$ where $bin
(n)$ is binary representation of $n$ $$QP = \bigcup_{c\in \...
- 379