Questions tagged [randomized-algorithms]
An algorithm whose behaviour is determined by its input and a generator producing uniformly random numbers.
214
questions
1
vote
0
answers
184
views
How to efficiently generate a random 0-1 matrix of a given rank
How to efficiently generate a random $n\!\times\!n$ $0$-$1$ matrix of rank $k<n$?
- 73
4
votes
0
answers
71
views
Constructing a bad sequence for counter algorithm
Assume that we want to construct a sequence $s\in\{a,b\}^{N}$ such that $s$ contains exactly $n$ times the letter '$a$'.
The sequence is then feed to the following probabilistic algorithm:
...
- 9,448
5
votes
1
answer
344
views
Smallest $f(n)$ such that $P/f(n) = BPP/f(n)$?
It is well-known that $\mathsf{P/poly}(n) = \mathsf{BPP/poly}(n)$.
It is a major open problem to prove the conjecture $\mathsf{P} = \mathsf{BPP}$.
$\mathsf{P} = \mathsf{BPP}$ implies $\mathsf{P}/f(n) ...
- 555
3
votes
2
answers
240
views
Extended version of the paper "Consistent Hashing and Random Trees" with proofs
I've been reading the following paper:
David Karger, Eric Lehman, Tom Leighton, Rina Panigrahy, Mathew Levine, Daniel Lewin, "Consistent Hashing and Random Trees: Distributed Caching Protocols for ...
- 141
3
votes
0
answers
116
views
Number theoretic problems complete for $\mathsf{RL}$
Are there number theoretic problems (such as those related to $\mathsf{gcd}$) that are in $\mathsf{RL}$?
Can these also be $\mathsf{RL}$-complete problems (is there any $\mathsf{RL}$-complete ...
user34945
9
votes
0
answers
595
views
Exponential time hypothesis for random algorithms
The exponential time hypothesis asserts that an algorithm for SAT must take time $2^{\Omega(n)}$. If I am reading this right, this refers only to deterministic algorithms.
Is it possible that ETH ...
- 3,498
23
votes
3
answers
3k
views
Generalizing the "median trick" to higher dimensions?
For randomized algorithms $\mathcal{A}$ taking real values, the "median trick" is a simple way to reduce the probability of failure to any threshold $\delta > 0$, at the cost of only a ...
- 4,461
11
votes
1
answer
318
views
Randomized Polynomial Hierarchy?
I wonder, what would happen, if in the definition of $PH$ (Polynomial Hierarchy, see, e.g., here), the role of $NP$ would be replaced by $RP$?
It seems, we could still build a hierarchy, the same ...
- 11.4k
-2
votes
1
answer
248
views
Is there a randomized complexity class analogous to $\mathsf{P/Poly}$?
$\mathsf{P/Poly}$ captures those problems that could be solved in polynomial time given some precomputed polynomial number of constants.
Is there an analogous complexity class in randomized world ...
- 12.9k
1
vote
0
answers
83
views
"conservative approximate Set Cover"?
We are given a lattice graph $L$, embedded on the plane, and a certain "shape" (a connected, acyclic subgraph $S$ of $L$).
The task is to approximately cover $L$ with translated, rotated and flipped ...
- 131
10
votes
2
answers
546
views
Exact formula for the number of spanning trees of a rectangle
This blog talks about generating "twisty little mazes" using a computer an enumerating them. The enumeration can be done using Wilson's algorithm to get the UST, but I don't remember the formula for ...
- 568
0
votes
1
answer
101
views
Efficiently picking free position from array with uniform probability.
For each array position it is known if position filled or not.
How efficiently pick one free position with uniform probability?
That task happen during implementation of AI by Monter-Carlo method ...
- 103
2
votes
0
answers
704
views
the confusion about 'with high probability (w.h.p.)'
w.h.p. can often be seen in the analysis of randomized algorithms. It's definition can be seen here https://en.wikipedia.org/wiki/With_high_probability. However my confusion is that:
Assuming we ...
- 179
15
votes
2
answers
1k
views
Which randomized algorithms have exponentially small error probability?
Suppose that a randomized algorithm uses $r$ random bits. The lowest error probability one can expect (falling short of a deterministic algorithm with 0 error) is $2^{-\Omega(r)}$. Which randomized ...
- 11k
-4
votes
1
answer
82
views
Probabilistic protocols [closed]
I want to model a probabilistic protocol using a model checker, but a lot of protocols are already implemented (e.g. Randomised Dining Philosophers, Dining cryptographers, Synchronous leader election ...
- 95
41
votes
7
answers
5k
views
When does randomization speed up algorithms and it "shouldn't"?
Adleman's proof that $BPP$ is contained in $P/poly$ shows that if there is a randomized algorithm for a problem that runs in time $t(n)$ on inputs of size $n$, then there also is a deterministic ...
- 11k
2
votes
1
answer
262
views
Evaluating the expected value of negatively correlated random variables
A polynomial random process satisfying the following properties converts a fractional point $(x_1, x_2, \ldots, x_n) \in \mathcal{P}$, $(x_i \in [0,1])$ to a random integer point $(X_1, X_2, \ldots, ...
- 93
-3
votes
1
answer
611
views
Using Yao's minimax principle [closed]
Consider the basic problem in which the input is an array A of n bits, and we need to output some index i with A[i]=1 (we can read a single bit each time).
Can you give me an example using Yao's ...
- 5
6
votes
1
answer
355
views
FPRAS on #P complete problems and self reducibility
I am quoting a phrase of Martin Dyer in his paper Approximate Counting by Dynamic Programming:
Since 0-1 knapsack is self-reducible, existence of an fpras for the problem now follows indirectly from ...
- 447
3
votes
0
answers
241
views
Probabilistic sorting given pairwise comparison probability
Let $X = \{x_1, \dots, x_n\}$ be a set, and $f:[1..n]^2 \to [0, 1]$ be a function, such that
$$f(i, j) \cdot f(j, k) \le f(i, k)$$
For all $1 \le i, j, k \le n$.
Does there exist a randomized ...
- 445
1
vote
0
answers
101
views
Eigenvalues of Random Regular Bipartite Graphs
I am looking for a way of getting a good estimate of the eigenvalues of random bipartite d-regular graphs. The literature has very precise values the proofs of which are very involved and since I am ...
- 666
5
votes
0
answers
133
views
Tools to bound the singular values of a finite sum of random matrices from below?
Matrix Chernoff bounds (see also this arXiv paper) are usually used to give upper bounds on the largest eigenvalue of a finite sum of random matrices. Sometimes it can also be used to give a lower ...
- 179
0
votes
0
answers
242
views
Steiner Tree and minimum spanning tree
If I must connect: $$2^k$$ terminals in a Steiner Tree choosen randomly and connect them with the cheapest component; "loss - contracting algorithm" is a good way? Or is an "Iterative Randomized ...
- 11
11
votes
2
answers
625
views
Lower bound on estimating $\sum_{k=1}^n a_k$ for non-increasing $(a_k)_k$
I'd like to know (related to this other question) if lower bounds were known for the following testing problem: one is given query access to a sequence of non-negative numbers $a_n \geq \dots\geq a_1$ ...
- 4,461
0
votes
1
answer
325
views
Randomized Algorithm with random input
As per the Yao's principle, in order to lower bound the cost of Randomized algorithm it suffices to find an appropriate distribution of difficult inputs, and to prove that no deterministic algorithm ...
- 101
3
votes
0
answers
868
views
What is the major difference between PP and RP? [closed]
So according to complexity zoo, the definition of RP is:
The class of decision problems solvable by an NP machine such that
1.If the answer is 'yes,' at least 1/2 of computation paths accept.
2.If ...
- 41
10
votes
2
answers
318
views
What is the minimum over all distributions of unit vectors of the variance of the dot product of the vectors?
I am trying to find a distribution over $n$ random vectors, say $x_1,\ldots, x_n$, on the $k$-dimensional unit sphere (where $n > k$) that minimizes $\max_{i\neq j} \mathrm{Var}(x_i^T x_j)$ subject ...
- 101
-2
votes
1
answer
1k
views
Finding cliques in weighted graph
We have given a weighted graph $G=\{V,E\}$, where $V=\{v_1, v_2,...,v_n\}$, and for all $i,j$, the weight of edges $w(v_i, v_j)\in (0,W)$. And we have also given a weight threshold s $w$ (where $0<...
- 639
24
votes
1
answer
625
views
The randomized query complexity of the conjoined trees problem
An important 2003 paper by Childs et al. introduced the "conjoined trees problem": a problem admitting an exponential quantum speedup that's unlike just about any other such problem that we know of. ...
- 13.7k
0
votes
0
answers
97
views
To find OR of $\sqrt{n}$ numbers each of $n$ bits?
Given $\sqrt{n}$ numbers of $n$ bits each. I need to find its OR and store it at another number RESULT of $n$ bits.
Trivially it can be done in $\mathcal{O}(n \sqrt{n})$ time, or $\mathcal{O}(n \sqrt{...
- 171
0
votes
1
answer
261
views
Proving properties of Random Graphs
I am asking the question on a slightly abstract level and it may depend on the specifics but it would be great to have related references or ideas.
Consider the random graph model $G_{n,p}$ where its ...
- 666
21
votes
1
answer
724
views
A flowchart for concentration bounds
When I teach tail bounds, I use the usual progression:
If your r.v is positive, you can apply Markov's inequality
If you have independence and also bounded variance, you can apply Chebyshev's ...
- 32.1k
10
votes
2
answers
852
views
A converse to Fano's inequality ?
Fano's inequality can be stated in many forms, and one particularly useful one is due (with a minor modification) to Oded Regev:
Let $X$ be a random variable, and let $Y = g(X)$ where $g(\cdot)$ is ...
- 32.1k
1
vote
1
answer
809
views
Freivalds matrix multiplication with non binary random vector
Freivalds' algorithm verify matrices (over a field) product $A \times B = C$ by choosing a random binary vector $r$ and verifying if $A(Br)=Cr$ which fails if $AB \neq C$ with probability at most $1/...
- 51
0
votes
1
answer
556
views
PAC algorithms for APX-Hard problems
Do there exist polynomial time algorithms that admit Probably Approximately Correct (PAC) bounds for APX-Hard problems? That is, does there exist a problem $P$ that is APX-Hard, such that for every $\...
- 161
6
votes
1
answer
170
views
Where does randomness help when deciding algebraic geometry over $\mathbb{C}$?
If we have a single straight line program expressing a multivariate polynomial equation with integer coefficients, the Schwartz-Zippel lemma gives a simple randomized algorithm for deciding whether ...
- 3,253
15
votes
1
answer
468
views
Natural theorems proven only "to high probability"?
There are plenty of situations where a randomized "proof" is much easier than a deterministic proof, the canonical example being polynomial identity testing.
Question: Are there any natural ...
- 3,253
10
votes
1
answer
573
views
What is the advantage of designing deterministic distributed algorithms?
Distributed algorithms that are resilient to failures can either be deterministic or probabilistic. Take for example the consensus problem.
Paxos is deterministic in the sense that given the ...
- 201
1
vote
0
answers
68
views
Bound the number of rounds in the sampling
Suppose we have a sequence $a_1,a_2,\ldots, a_n$, each $a_i$ is sampled uniformly and independently from $[0,1]$.
Define
$$
J_1=1,\\
\text{for}~i>1, ~J_i = 1 \iff a_i < \min \{a_1,a_2,...
- 13
12
votes
0
answers
223
views
Hitting edges in graphs at random and let them die with honor
Let $G=(V,E)$ be a finite simple 2-connected graph. Let $B\subseteq E$ be a set of bad edges of size $k:=|B|$. For each edge $e\in E$ we toss a fair coin ($p=1/2$) and if the outcome is head, we hit ...
- 650
2
votes
1
answer
157
views
Complexity of determining unique elements of each cycle in a permutation
It is a well known fact that a permutation is a set of cycles, and that one can find all cycles of a permutation in $O(n)$ time, where $n$ is the length of the permutation.
But suppose that we know ...
- 187
4
votes
0
answers
189
views
Randomized Parallel Algorithm for Maximal Independent Set
There are a couple of randomized parallel algorithms for the maximal independent set problem, e.g. A Simple Parallel Algorithm for the Maximal Independent Set Problem, A fast and simple randomized ...
- 1,338
2
votes
0
answers
235
views
Height of randomly built binary search tree by insert and delete?
In Introduction to algorithm (CLRS), even in its third edition (published in 2009) it is noted in Sec 12.4 that little is known about height of randomly built binary search tree using insert and ...
3
votes
0
answers
298
views
Generating random graphs using the preferential attachment model with degree bounds
I am interested to know the structure of random graphs generated by the preferential attachment model with degree bounds. Specifically, when a vertex is chosen with a probability proportional to its ...
- 1,591
18
votes
3
answers
809
views
In what class are randomized algorithms that err with exactly 25% chance?
Suppose I consider the following variant of BPP, which let us call E(xact)BPP:
A language is in EBPP if there is a polynomial time randomized TG that accepts every word of the language with exactly 3/...
- 14k
4
votes
1
answer
625
views
On Random Self-reducible properties
Permanent is random self-reducible. $\mathsf{SAT}$ is not random self-reducible since otherwise the polynomial hierarchy collapses to $\mathsf{\Sigma_3}$.
1) Is $k$-sum random self-reducible?
That ...
- 12.9k
3
votes
1
answer
1k
views
Approximate Maximum Weight Matching
I am looking for an approximated (or randomized) maximum weight matching algorithm. Do you have any suggestion for me?
In my problem, I have a bipartite graph with N abound 1000 (#vertices on each ...
- 169
0
votes
1
answer
497
views
karger's algorithm contracting nodes not edges [closed]
Karger's algorithm works by contracting edges, not merging nodes (this is different because nodes need not share an edge).
Is there a reason why this is so?
7
votes
1
answer
317
views
Running time of randomized algorithms
This is a very basic doubt, something I've always swept under the carpet.
The definition of BPP allows a machine access to random bits, which are 0 and 1 with equal probability. Many a randomized ...
user1694
28
votes
1
answer
1k
views
Is uniform RNC contained in polylog space?
Log-space-uniform NC is contained in deterministic polylog space (sometimes written PolyL). Is log-space-uniform RNC also in this class? The standard randomized version of PolyL should be in PolyL, ...
- 1,811