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

learn more… | top users | synonyms

3
votes
0answers
103 views
+50

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
90 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 ...
0
votes
0answers
27 views

Game Tree Evaluation [on hold]

I was reading the chapter Game-Theoretic Techniques of Randomized Algorithm by Motwani and Raghavan and there is something I do not understand. It says the "...cost of evaluating any instance of ...
0
votes
1answer
53 views

stable marriage breaking ties, how to?

I have found the following algorithm proposed by Halldorsson which is a randomized algorithm: ...
2
votes
0answers
74 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
230 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
133 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 ...
23
votes
1answer
369 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
82 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 ...
0
votes
1answer
167 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
548 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
248 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
75 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 ...
0
votes
0answers
61 views

Estimate the maximum by randomized approximation algorithms

Given a set $A$ of $2^n$ elements such that each $a\in A$ is a rational in $[0,1]$. The question is to estimate $\max(A)$, i.e., the maximal element of $A$. Is there a polynomial algorithm to ...
0
votes
1answer
146 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
74 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
307 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 ...
9
votes
1answer
174 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
59 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 ...
12
votes
0answers
198 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
118 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 ...
4
votes
0answers
77 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 ...
2
votes
0answers
104 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
0answers
178 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 ...
12
votes
2answers
506 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 ...
4
votes
1answer
171 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 ...
2
votes
1answer
197 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 ...
0
votes
1answer
164 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
1answer
206 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 ...
25
votes
1answer
620 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, ...
4
votes
0answers
131 views

Sums of products of bernoulli random variables

Let $x_1 \ldots x_a,y_1 \ldots y_b$ be independent random variables taking values +1 or -1. Consider the sum $$S = \sum_{i,j} x_iy_j.$$ I wish to upper bound the probability $P(|S| > t)$. The ...
3
votes
0answers
458 views

Lowest Common Ancestor Problem in Directed Acyclic Graphs

What is the current best bound for the following problem in DAG: "For any pair of vertices in a given graph G, return all the LCAs of the same"? Edit: I am working on all-pair reachability problem in ...
2
votes
0answers
106 views

What upper bound can we get under 3-wise independence? (comparable edition)

Here is the original question: What bound can we get using $k$-th moment inequality under 3-wise independence? .Yury has given a 3-wise independent example that shows the upper bound is no better than ...
7
votes
2answers
327 views

What bound can we get using $k$-th moment inequality under 3-wise independence?

Let $X_1,\dots, X_n$ be 0-1 random variables, which are $3$-wise independent. We want to give a upper bound to $\Pr(|\Sigma_iX_i-\mu|\geq t)$. Can we get better bound than ...
3
votes
0answers
97 views

Concentration Bounds for Dependent Rounding

Consider the following random process which is defined on $n$ numbers $0\leq x_1,\ldots,x_n\leq 1$: At each step, pick an arbitrary number, say $x_i$. Then randomly (and independently) change its ...
6
votes
1answer
212 views

Shortest paths perturbation

I have a graph $G=(V,E)$, with positive weights $w_e, e\in E$ on the edges, and I would like to randomly perturb the weights of the edges so that for each pair of distinct vertices $(u,v)$ such that ...
1
vote
2answers
240 views

Chernoff Bounds for settings with limited dependence

Could someone point me to a way of bounding the tail probability of sums of bernoulli variables each generated by the same distribution but the condition of independence is only partially satisfied. ...
16
votes
1answer
685 views

The complexity of sampling (approximately) the Fourier transform of a Boolean function

One thing that quantum computers can do (possibly even with just BPP + log-depth quantum circuits) is to approximate-sample the Fourier transform of a Boolean $\pm 1$-valued function in P. Here and ...
9
votes
3answers
404 views

What is the fastest known simulation of BPP using Las Vegas algorithms?

$\mathsf{BPP}$ and $\mathsf{ZPP}$ are two of basic probabilistic complexity classes. $\mathsf{BPP}$ is the class of languages decided by probabilistic polynomial-time Turing algorithms where the ...
8
votes
1answer
306 views

logic in the presence of doubt, uncertainty, lies

I was reading Harry Frankfurt's On Bulls*t, a 1986 philosophical essay about this blurry notion between truth and falsity. This is not a gratuitous exercise. This may have applications to computer ...
4
votes
0answers
158 views

Type-and-effect systems, stochasticism and effect squelching: how about quicksort?

There's a feature of Haskell's type system which bugs me: you can't implement a randomized sorting algorithm without the use of randomness spilling out into all of its callers. That seems ...
11
votes
0answers
189 views

On preprocessing a convex polyhedron prior to sampling

Most of the algorithms for estimating the volume of a convex polyhedron $K \subset R^d$ assume the existence of an affine transform $T$ with the property that $$ B \subset TK \tilde{\subset}\ ...
26
votes
1answer
662 views

Consequences of $\mathsf{NP}$ containing $\mathsf{BPP}$

Many believe that $\mathsf{BPP} = \mathsf{P} \subseteq \mathsf{NP}$. However we only know that $\mathsf{BPP}$ is in the second level of polynomial hierarchy, i.e. $\mathsf{BPP}\subseteq \Sigma^ ...
7
votes
1answer
161 views

Sampling from the Voronoi cell of a point

Fix a set of $n$ points $P \subset \mathbb{R}^d$. Now a query point $q$ arrives, and the goal is produce a point $r$ sampled uniformly at random from the Voronoi cell of $q$ in the set $P \cup ...
5
votes
0answers
205 views

Distributed algorithms on sets

Given a connected arbitrary network $G = (V,E)$, where $V$ is a set of nodes (processors) and $E$ is the set of edges between the nodes. Each node $v _i$ is assigned a non-empty set $S(v _i)$, where ...
14
votes
1answer
326 views

Is it enough for linear program constraints to be satisfied in expectation?

In the paper Randomized Primal-Dual analysis of RANKING for Online Bipartite Matching, while proving that the RANKING algorithm is $\left(1 - \frac{1}{e}\right)$-competitive, the authors show that the ...
6
votes
0answers
277 views

Narrowing the gap between BPP and RP

We do not know yet whether the 2-sided error of $BPP$ allows more computing power than the one sided error of $RP$. In view of derandomization results, the conjectured answer is no, since both classes ...
3
votes
1answer
197 views

Coupon collector - the effect of randomization

Given a set $S = \{1, ..., n\}$, an element is randomly drawn with replacement from $S$. Let's say we got the following sequence $X = \{x _1, ..., x _k\}$ until all elements of $S$ are seen, where $x ...
29
votes
6answers
2k views

Efficient and simple randomized algorithms where determinism is difficult

I often hear that for many problems we know very elegant randomized algorithms, but no, or only more complicated, deterministic solutions. However, I only know a few examples for this. Most ...
2
votes
1answer
122 views

Independent iterations in Las Vegas algorithms

In [Randomized Algorithms, Motwani and Raghavan] book, it is stated that the method of independent iterations to reduce the error probability in Monte Carlo algorithms (amplification according to ...