An algorithm whose behaviour is determined by its input and a generator producing uniformly random numbers.

learn more… | top users | synonyms

1
vote
1answer
54 views

Is there a linear space lower bound for streaming set equality?

Consider two streams. In each stream one string arrives at a time. A query asks: Is the set of strings that has arrived so far the same in both streams? Is there a linear space randomized lower ...
3
votes
1answer
53 views

Quick Sampling from Probability Distribution: Is there a name for this algorithm?

I'm trying to quickly sample from a near-uniform discrete probability distribution exactly once without calculating the entire CDF. Here's the algorithm. Givens: $N,$ the number of elements to ...
2
votes
1answer
312 views

Can every distribution producible by a probabilistic PSpace machine be produced by a PSpace machine with only polynomially many random bits?

Let $M$ be a probabilistic Turing machine with a unary input $n$ whose space is bounded by a polynomial in $n$ and its output is a distribution $D$ over binary strings. Note that the number of ...
1
vote
1answer
45 views

Randomized and deterministic query complexity of symmetric functions

The deterministic query complexity $D(f)$ of a symmetric function $f$ is $\Omega(n)$ (except for f = 0 or f = 1). I am wondering if the same result holds for the (bounded-error) randomized query ...
6
votes
1answer
513 views

Johnson and Lindenstrauss lemma for hamming space

A result of Johnson and Lindenstrauss shows that a set of $n$ points in high dimensional Euclidean space can be mapped into an $O(\frac{\log n}{\epsilon^2})$- dimensional Euclidean space such that the ...
16
votes
3answers
586 views

Examples of successful derandomization from BPP to P

What are some major examples of successful derandomization or at least progress in showing concrete evidence towards $P=BPP$ goal (not the hardness randomness connection)? The only example that comes ...
3
votes
3answers
106 views

Random grid point in a d-dimensional ball

I would like to know if there is any standard algorithm to generate a random grid point inside a d-dimensional ball with a given radius r. Thanks Bin Fu
5
votes
2answers
170 views

The relationship between degree of vertex and size of dominating set

I was wondering is there any relationship between degree of vertex and size of dominating set. For example, if I know the number of vertices is $n$, and I could know each vertex in the graph has ...
6
votes
1answer
186 views

Checking properties of matrices

Given a sparse matrix $A$ in $\mathbb{Z}^{n\times n}$, how easily could one check whether a coefficient $\alpha_k$ of the characteristic polynomial $P_A$ of $A$ is equal to $0$ (without the need to ...
0
votes
0answers
88 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$?
3
votes
0answers
46 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: ...
1
vote
0answers
118 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) ...
2
votes
0answers
80 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 ...
2
votes
0answers
88 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 ...
8
votes
0answers
203 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 ...
19
votes
3answers
985 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 ...
11
votes
1answer
205 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 ...
-2
votes
1answer
142 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 ...
1
vote
0answers
73 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 ...
9
votes
2answers
164 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 ...
0
votes
1answer
47 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 ...
2
votes
0answers
191 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 ...
15
votes
2answers
768 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 ...
-4
votes
1answer
54 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 ...
36
votes
5answers
4k 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 ...
1
vote
1answer
193 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, ...
-3
votes
1answer
141 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 ...
6
votes
1answer
135 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 ...
3
votes
0answers
94 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 ...
1
vote
0answers
37 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 ...
5
votes
0answers
101 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 ...
0
votes
0answers
142 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
votes
2answers
472 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$ ...
0
votes
1answer
267 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 ...
2
votes
0answers
212 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. ...
10
votes
2answers
258 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 ...
-2
votes
1answer
295 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<...
23
votes
1answer
434 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. ...
0
votes
0answers
89 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{...
0
votes
1answer
183 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 ...
21
votes
1answer
575 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 ...
9
votes
1answer
331 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)$ ...
1
vote
1answer
185 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/...
0
votes
1answer
259 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 $\...
5
votes
1answer
110 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 ...
15
votes
1answer
320 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 ...
10
votes
1answer
289 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 ...
1
vote
0answers
61 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,...
12
votes
0answers
209 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 ...
2
votes
1answer
123 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 ...