We’re rewarding the question askers & reputations are being recalculated! Read more.

# Questions tagged [randomized-algorithms]

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

169 questions
Filter by
Sorted by
Tagged with
200 views

### Uniform derandomisation of circuit complexity classes

Let $\mathcal{C}$ be a complexity class and $\textrm{BP-}\mathcal{C}$ be the randomized counterpart of $\mathcal{C}$ defined in the same way as $\textrm{BPP}$ is defined with respect to $\textrm{P}$. ...
309 views

### Algorithm to compute distance between powers

Given coprime $a, b$, can you quickly compute $$\min_{x, y > 0} |a^x - b^y|$$ Here $x, y$ are integers. Obviously taking $x = y = 0$ gives an uninteresting answer; in general how close can these ...
896 views

### How to analyze a randomized recursive algorithm?

Consider the following algorithm, where $c$ is a fixed constant. ...
370 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 ...
978 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. ...
561 views

### Proving skip-lists strongly weight-balanced in expectation

Given a skip list of height $n$, what is its expected length, to within a constant (multiplicative) factor? In section 2.2 of Cache-Oblivious B-Trees, Strongly Weight-Balanced Search Trees are ...
112 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 ...
239 views

567 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 ...
730 views

### Random sampling data structure with removal

I'd like a data structure with the following operations: create a new instances from an array of floating point weights. randomly sample, returning an item with probability proportionate to its ...
454 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 ...
613 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 ...
279 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 ...
544 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 ...
164 views

### Finding the set of paths of smallest cumulated length that cover a given set of patterns

First of all, sorry for this long and maybe not very informative title... Context: Let $G=(V,E)$ be a directed graph, let $v_0 \in V$ be the initial node of paths that I will consider in the graph. ...
265 views

### Random point in a d-dimensional ball

I would like to know if there any algorithm to pick a random grid point inside a d-dimensional ball with a given radius R. And if there any algorithm to pick a random arbitrary point inside a d-...
855 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 ...
617 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 ...
146 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 ...
216 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 ...
124 views

### Directed graph with bounded in-deg can be partitioned in a balanced way

I want to prove that for all $n$, there exists a constant $c(n)$ such that if $G=(V,E)$ is a directed graph with in-degree bounded by $n$, it is possible to partition the set of vertices $V$ into two ...
222 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 ...
985 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$ ...
551 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, . . ....
188 views

### Finding a positive point for a collection of polynomials

I am wondering about the complexity of the following problem: Given $k$ polynomials $p_1(x_1, \ldots, x_n)$, $p_2(x_1, \ldots, x_n)$, $\ldots$, $p_k(x_1, \ldots, x_n)$ over the $n$ real ...
1k 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. ...
179 views

### Max cut problem between two connected subgraphs

Let $G$ be a connected graph. Consider the problem of finding a partition $G = A \cup B$ into connected subgraphs, so that the cut between $A$ and $B$ is maximized. Is there anything which is known ...
182 views

### Correctness of AKS algorithm for shortest vector problem

Short question In the end of section 1 of Regev's notes about the AKS algorithm for SVP, why is the following true? for each such $i$,$y_i− x_i$ remains $w$ with probability $1/2$ or otherwise ...