Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [randomized-algorithms]

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

70 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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
202 views

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
205 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: \...
• 181
288 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 ...
• 763
332 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 ...
89 views

### Searching for a proof that non-deterministic logspace with errors is contained in $PL$

In this 10 year old question Non-deterministic logspace with two-sided error the author asked for a complexity class related to $NL$. Namely $NL$ but we are allowed to have two-sided error for the ...
53 views

### Approximately sampling from a discrete unimodal distribution with large support

I have an algorithmic problem and I am curious if a solution is known in the literature, because I cannot find it. I came up with an algorithm of my own, but would be curious if something is known. I ...
• 630
97 views

### Random Self-Reducibility of the Discrete Logarithm

Section 10.1.2 of Sanjeev Arora and Boaz Barak's Computational Complexity: A Modern Approach defines random self-reducibility and proves hardness of the discrete logarithm by reducing a worst case ...
96 views

### Alternative criterion for approximate maximum-weight perfect matching algorithms

I have asked this question in cs.stackeschange, and it was recommended to me that I asked it here. Is there any literature on approximate maximum-weight perfect matchings where the approximation ...
• 29
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 ...
125 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 ...
• 201
472 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 ...
• 121
1 vote
42 views

### How to understand this evolutionary algorithm lower bound calculation?

I have a proof that I understand the most of it except one step Lemma 10. The expected number of steps the $(1+1)$ EA takes to optimize a linear function with all non-zero weights is $\Omega(n \ln n)$....
• 111
1 vote
92 views

### Generalizing Fano's inequality

Fano's inequality says the following: Theorem: Let $X$ be a random variable with range $M$. Let $\hat{X} = g(Y)$ be the predicted value of $X$ given some transmitted value $Y$, where $g$ is a ...
1 vote
52 views

### Failing to understand a lemma regarding Robust Low Rank Approximation

I am reading Low Rank Approximation in the Presence of Outliers by Bhaskara and Kumar and kind of stuck at the proof of Lemma 9. The paper studies robust (to outliers) low rank approximation problem. ...
• 265
1 vote
93 views

### Cover Time of Random Walks with Backtracking on Directed Graphs

The cover time of a random walk on an undirected graph is the expected time for the walk to visit all vertices of the graph (starting from an arbitrary vertex). It is well known that any connected ...
• 676
1 vote
112 views

### Sampling from a family of hash functions, not uniformly at random?

Many algorithms and data structures assume access to a family of hash functions satisfying some nice property (say, $k$-independence or $k$-universality). In these cases, we usually assume that we ...
• 2,242
1 vote
100 views

### What is the state of the art in first order stochastic convex optimization?

What is the optimally fastest convex risk minimizing algorithm which only uses a stochastic first order oracle? Is this SGD? What is the optimally fastest convex function minimizing algorithm which ...
• 1,453
1 vote
$(k,j)$-projective clustering is the natural generalisation for k-clustering, in which one needs to find $k$ $j$-flats in $\mathbb{R}^d$ that minimizes the cost function as defined below: Given a $j$-...