An algorithm whose behaviour is determined by its input and a generator producing uniformly random numbers.
-6
votes
0answers
33 views
CalculatorVSCellPhone [closed]
"calculator or calculating machine, device for performing numerical computations; it may be mechanical, electromechanical, or electronic. The electronic computer is also a calculator but performs ...
2
votes
0answers
48 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
111 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
102 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. ...
11
votes
1answer
393 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 ...
8
votes
3answers
357 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
248 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
88 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
176 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}\ ...
22
votes
1answer
407 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
115 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 ...
4
votes
0answers
168 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 ...
13
votes
1answer
273 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
156 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
177 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 ...
25
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
108 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 ...
1
vote
1answer
236 views
Is there a randomized algorithm for set-cover?
Is there a well-known randomized algorithm for the set cover problem in the literature - such that it has an approximation ratio of $O(\log n)$ or $f$ - where $f$ is the max frequency of an element. ...
3
votes
0answers
160 views
Randomized rounding on a graph
Assume we are given an arbitrary undirected graph $G = (V, E)$ where $|V| = n$. We are also given real numbers $x_e \in [0, 1]$ for each $e \in E$. These numbers satisfy the following constraint:
...
6
votes
0answers
114 views
Count $k$-hop neighborhood for every vertex
For a node $v$ of a directed unweighted graph $G$, I define the $k$-hop neighborhood of $v$ as the set of vertices that are reachable from $v$ in $k$ hops or fewer (that is following a path with $k$ ...
23
votes
10answers
1k views
Probabilistic (randomized) algorithms before “modern” computer science appeared
Edit: I choice the answer with highest score by December 06, 2012.
This is a soft question.
The concept of (deterministic) algorithms dates back to BC. What about the probabilistic algorithms?
In ...
9
votes
1answer
156 views
What is the worst case of the randomized incremental delaunay triangulation algorithm?
I know that the expected worst-case runtime of the randomized incremental delaunay triangulation algorithm (as given in Computational Geometry) is $\mathcal O(n \log n)$.
There is an exercise which ...
3
votes
0answers
102 views
Online Interval Coloring Problem
We are given a path $P = (V,E)$ on $n$ nodes, where each edge $e \in E$ has a capacity $c_e$. There are a set of $k$ requests $R_1,\ldots,R_k$. Request $R_i$ has a demand $d_i$, and has an interval ...
7
votes
2answers
387 views
Rigorous proof that a random function and a random permutation cannot be distinguished in polynomial time
I have a background in number theory and I'm trying to learn how to reason rigorously about algorithms. I'm reading chapter 2 of Katz and Lindell's Introduction to Modern Cryptography.
Show that no ...
14
votes
0answers
434 views
Who first proposed using $x^2+y^2 < 1$ Monte Carlo algorithm to calculate Pi?
I'm sure everybody know's of Buffon's needle experiment in the 18th century, that is one of the first probabilistic algorithms to calculate $\pi$.
The implementation of the algorithm in computers ...
6
votes
1answer
284 views
How to generate a permutation uniformly by repeating using an one-bit uniform random generator?
If I have an one-bit uniform random generator, how can I use it to generate a permutation uniformly for the sequence {1, 2, ..., n}.
I have a solution: run the one-bit random generator n*n times to ...
7
votes
1answer
209 views
What are some results on algorithms that estimate polynomials over a given set of points?
There seem to be many randomized algorithms for polynomial identity testing, checking whether or not a given polynomial is zero. Are there any results of algorithms that do some sort of estimation of ...
6
votes
3answers
676 views
Algorithms with finite expected running time and infinite variance
I am working on an algorithm for which the running time is a random variable $X$ that has finite expected value, but infinite variance. Are there examples of other algorithms for which this is the ...
7
votes
3answers
497 views
Does randomness buy us anything inside P?
Let $\mathsf{BPTIME}(f(n))$ be the class of the decision problems having a bounded two-sided error randomized algorithm running in time $O(f(n))$.
Do we know of any problem $Q \in \mathsf{P}$ such ...
8
votes
1answer
89 views
Deciding DDH based in partial information
Decisional Diffie–Hellman assumption, or DDH in short, is a famous problem in cryptography.
The DDH assumption holds on a cyclic group $(G,*)$ of (prime) order $q$, if for a generator $g \in G$, and ...
0
votes
1answer
137 views
Maximum Independent Set using Maximal MIS
I want to use multiple runs of maximal independent set (Luby's algorithm) to find a lower bound on the size of maximum independent set.
Are there any bounds on the number of times the maximal ...
16
votes
2answers
701 views
Are theoretically sound pseudorandom generators used in practice?
As far as I'm aware, most implementations of pseudorandom number generation in practice use methods such as linear shift feedback registers (LSFRs), or these "Mersenne Twister" algorithms. While they ...
18
votes
3answers
446 views
Running a BPP algorithm with a half-random, half-adversarial string
Consider the following model: an n-bit string r=r1...rn is chosen uniformly at random. Next, each index i∈{1,...,n} is put into a set A with independent probability 1/2. Finally, an adversary ...
2
votes
1answer
152 views
Generate random permutation via iid uniforms — is inverse transformation possible?
A very common technique in the analysis of algorithms involving random permutations is to have each element $x$ select a rank $\rho(x)$ uniformly at random from the real interval $[0,1]$. The ...
8
votes
1answer
260 views
Determine the minimum number of coin-weighings
In the paper On two problems of information theory, Erdõs and Rényi give lower bounds on the minimum number of weighings one must do to determine the number of false coins in a set of $n$ coins.
...
6
votes
1answer
370 views
Can this randomized greedy algorithm be made online? Or being proved impossible?
I am going to edge color an undirected simple graph. The following randomized offline algorithm is showed at Online Algorithms for Edge Coloring.
Offline: The potential colors are ordered 1, 2, . . ...
16
votes
2answers
691 views
Yao's Minimax Principle on Monte Carlo Algorithms
The celebrated Yao's Minimax Principle states the relation between distributional complexity and randomized complexity. Let $P$ be a problem with a finite set $\mathcal{X}$ of inputs and a finite set ...
3
votes
1answer
198 views
BPP Error Reduction
Consider the class of all languages $L$ that have a randomized algorithm $A$ that runs in worst-case polynomial time such that for any input $x$ if $x \in L$ then $Pr[A(x)\quad \textrm{accepts}] \ge ...
8
votes
2answers
575 views
How to analyze a randomized recursive algorithm?
Consider the following algorithm, where $c$ is a fixed constant.
...
4
votes
1answer
178 views
What's the strict definition of random coins in streaming algorithm?
I have a very basic question about random bits in streaming. How could a streaming algorithm use them? Can the algorithm use the same random bit at the start of the execution and look at it again ...
8
votes
1answer
406 views
How should one simulate self-avoiding random walks?
There is a trivial method for simulating a random walk through a graph by exponentiating a stochastic adjacency matrix, but the problem becomes harder if you ask that the random walk be self-avoiding. ...
6
votes
1answer
453 views
How to shuffle colour balls?
I have 400 balls, in which 100 are red, 40 are yellow, 50 are green, 60 are blue, 70 are purple, 80 are black. (balls of the same colour are identical)
i need an efficient shuffling algorithm, so ...
7
votes
4answers
371 views
How to shuffle cards with restrictions?
I want as uniformly as possible to pick from all full shuffles such that this additional criterion applied.
For example, i would like to shuffle 4 decks of cards, and make sure:
Any consecutive 4 ...
4
votes
2answers
305 views
FPRAS for #P-complete problems
I just found the following sentence from the #P wiki page:
"Jerrum, Valiant, and Vazirani showed that every #P-complete problem either has an FPRAS, or is essentially impossible to approximate; if ...
3
votes
0answers
215 views
Distinguishing two types of Monte-Carlo algorithms
Recall from Wikipedia that Monte Carlo algorithm is a randomized algorithm whose running time is deterministic, but whose output may be incorrect with a certain (typically small) probability. Consider ...
13
votes
0answers
254 views
Reusing 5-independent hash functions for linear probing
In hash tables that resolve collisions by linear probing, in order to ensure $O(1)$ expected performance, it is both necessary and sufficient that the hash function be from a 5-independent family. ...
3
votes
0answers
278 views
Taking Square Roots of Matrices over Z/nZ
Is it easy (computationally) to take square roots of matrices over Z/nZ, if you know the factorization of n? More specifically, suppose I generate a random matrix M, and square it. Can a ...
1
vote
1answer
199 views
Does there exist polytime algorithm for this partitioning problem?
I would like to know if there exists a polytime probablistic algorithm for the problem described below. It is relevant for construction of a crossvalidation-partitioning in statistics, fulfilling ...
2
votes
0answers
337 views
Texts on application of randomized algorithms
as far as I know, Motwani & Raghavan, ”Randomized Algorithms”, Cambridge University Press, 1995 is the standard book for randomized algorithms. This is an excellent theoretical intro.
Which is ...
16
votes
2answers
529 views
Faster join of treap-like data structures with approximately the same size
Given two AVL trees $T_1$ and $T_2$ and a value $t_r$ such that $\forall x \in T_1, \forall y \in T_2, x < t_r < y$, it is easy to construct a new AVL tree containing $t_r$ and the values in ...
