Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [randomized-algorithms]

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

2
votes
1answer
93 views

Intuitive explanation behind Goemans-Williamson randomized rounding

A very simple randomized cut algorithm achieves $1/2$ of the optimal value: just choose each vertex to be in the cut with probability $1/2$, independently. Goemans-Williamson does something more ...
4
votes
6answers
397 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 ...
-1
votes
0answers
107 views

$BPP$ before Adleman-Sipser-Gacs theorem?

Where was $BPP$ before it was in second level? If we show $BPP$ is in $P^{NP}$ then we would've separated $BPP$ from $EXP^{NP}$. What did $BPP$ in second level accomplish? Did it have to cross any ...
-1
votes
0answers
29 views

Precision Sampling for Heavy Hitters

This is an intermediate step to show that we can use precision sampling to estimate $l_1$ of a stream with help of heavy hitter. Say we have a bunch of random variables $u_i \sim \exp(1)$ for $i = 0, ...
3
votes
0answers
67 views

Generating a random connected bipartite graph

A (n, m, k)-bipartite graph is a bipartite graphs with: independent sets of size $\{n, m\}$ a total of $k \geq n+m-1$ edges We want an algorithm to generate a (n, m, k)-bipartite selected uniformly ...
8
votes
4answers
339 views

List of quantum-inspired algorithms

Advances in quantum computing have led to the development of new classical algorithms. Notable recent examples are quantum-inspired algorithms for linear algebra: A quantum-inspired classical ...
0
votes
0answers
11 views

Is there a stochastic/online version of the GLM-Tron algorithm?

The GLM-Tron algorithm appeared in Theorem $1$ in this paper, https://arxiv.org/pdf/1104.2018.pdf Is there a stochastic version of this? (...essentially something that will randomly sample a few ...
10
votes
2answers
277 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 ...
1
vote
0answers
33 views

PTAS for projective clustering : survey

$(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$-...
1
vote
1answer
57 views

What forms of randomness are 'allowed' in FPRASs?

I cannot seem to find a source describing randomized approximation schemes ((F)PRAS) that tells me exactly what sort of randomness a program is allowed to use. A priori it seems to me that being able ...
5
votes
0answers
143 views

Classification of randomized approximation algorithms

Is there a known classification of randomized approximation algorithms, in the same vein as the distinction between Monte Carlo and Las Vegas algorithms for decision problems? (Or equivalently ...
1
vote
0answers
62 views

Complexity class of approximating perfect match count

We know we can approximate perfect matching count of bipartite and approximate volume of convex bodies in randomized polynomial time. Is there any evidence these approximations could be in Nick's ...
1
vote
0answers
64 views

Missing proof in Salil Vadhan's monograph on pseudorandomness, Random Walks and S-T Connectivity

In Salil Vadhan's monograph on pseudorandomness, chapter 2, half of the proof of Lemma 2.51 is missing http://people.seas.harvard.edu/~salil/pseudorandomness/power.pdf . I don't state the full lemma ...
1
vote
0answers
20 views

What is the maximal load of a “latency-bounded” Cuckoo Hash?

Cuckoo Hashing is a method for storing key-value stores (or just a set of keys) with a constant worst-case lookup time. They use two hash functions $h_1,h_2:\mathbb K\to [n]$, where $\mathbb K$ is ...
4
votes
2answers
135 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 ...
10
votes
2answers
609 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 ...
5
votes
1answer
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. ...
22
votes
2answers
2k 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 $...
0
votes
0answers
86 views

distNP-complete problem

Here on page 367 there is an example of $\text{dist}\mathbb{NP}$-complete problem: let $U$ contain all tuples $\langle M,x,1^t\rangle$ where there exists a string $y\in \{0,1\}^l$such that the ...
-1
votes
1answer
81 views

Reducing disjoint or indexing or inner-product problem to s-t connectivity problem in directed graph

I am asked to prove that an O(1)-pass randomized streaming algorithm that solves s-t connectivity problem in a simple directed graph $G=(V,E)$ with $|V|=n$ vertices, with sucess possibility $>\frac{...
8
votes
2answers
603 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 ...
1
vote
0answers
55 views

Minimization of the maximal adjacent integer sums on a circle

Arrange $\{1,2,\cdots,n\}$ on a circle. What are the arrangements that minimize the maximal sum of all adjacent $k$ integers? For specific and low $n$'s it has been pointed out in math.stackexchange....
4
votes
0answers
137 views

research problem for undergraduate majoring in Computer Science and Mathematics

I am wondering if somebody can suggest a small research problem for undergraduate majoring in Computer Science and Mathematics. Would love to work with random matrices or wavelets.
0
votes
0answers
28 views

Expected size of the min-cut, under edge perturbations

Suppose we have a graph $G(V, E)$. Assume that the min-cut of this graph is given $C=(A/B)$ and denote the size of the cut with $|C|$. Create a random modification of the graph: Drop each ...
3
votes
1answer
128 views

Tighter Probability Bounds

Let $\mathcal{F}$ be a class of binary functions on a probability space $\Omega$. For $f \in \mathcal{F}$, let $P(f) =\mathbb{E}(f(Z))$ and $P_n(f) = \frac{1}{n} \sum_{i=1}^n f(Z_i)$ where $Z_i$'s are ...
1
vote
1answer
54 views

Does the following 2-rounds distributed algorithm approximates a maximal matching well?

Let $G$ be an undirected graph. I'm looking for a two-rounds distributed algorithm that matches as many vertex pairs as possible. Consider the following protocol for vertex $v$. Use a fair coin to ...
1
vote
0answers
48 views

Generating random labelled trees

I am looking for a simple rejection-free algorithm to uniformly sample random labelled trees (i.e. to generate each of them with the same probability). One possibility is to generate Prüfer sequences ...
10
votes
2answers
490 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)$ is ...
9
votes
1answer
308 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 ...
5
votes
0answers
105 views

Learning hidden variable distribution

Consider a set of $k$ continuous variables. Each variable $x_k$ is associated with a hidden distribution from which its value is sampled independently of other variables. I am given a set of ...
5
votes
1answer
256 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) ...
3
votes
1answer
126 views

Literature reference for search-BPP

I'm trying to find the first article/paper that the complexity class search-BPP appeared in. Search-BPP, as defined as follows (in [1]): A binary relation $R$ is in search-BPP if there is a ...
3
votes
2answers
163 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 ...
-3
votes
1answer
104 views
0
votes
2answers
448 views

Naive shuffle algorithm [closed]

Let us have a "shuffle algorithm": for i in range(len(vec)): swap(vec[i], vec[rand()%len(vec)]) Why the reshuffles we get using this algoritm for a number ...
10
votes
1answer
289 views

Find an approximate argmax using only approximate max queries

Consider the following problem. There are $n$ unknown values $v_1, \cdots, v_n \in \mathbb{R}$. The task is to find the index of the largest one using only queries of the following form. A query ...
17
votes
3answers
644 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 3/...
1
vote
0answers
70 views

Time complexity of polynomial regression with random coefficients

Suppose that I have $$\lim_{k,l,m \rightarrow \infty}(f(x,l) ~~=~~ \sum_{n=1}^{m} g(a_{n,k})h(x,n)$$ where the $a_{n,k}$ are pseudo-random real numbers with $k$ digits generated in an arbitrary way, ...
6
votes
1answer
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 ...
8
votes
2answers
259 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-...
4
votes
1answer
97 views

Sublinear finite-precision sampling in a stream

I am looking to sample a single item from a stream such that each item in the stream has an equal probability of being selected. This is a restricted version of the reservoir sampling problem. On a ...
4
votes
1answer
159 views

Lower bound on probability of getting two close points in a sample of $n$ points

Let $D\subseteq \mathbb{R}^k$. Assume that $Pr_{u,v\leftarrow U_D}[|u-v| <B]>p$ for some $B,p$, where $|u-v|$ is the L1 distance of the vectors. $S\subseteq D$ is obtained by sampling $n$ ...
3
votes
1answer
225 views

Weighted balls and bins

Suppose I have $n$ balls and $n$ bins. Each ball $i$ has weight $w_i$. Let the total weight be $T = \sum_{i=1}^n w_i$. We throw the balls into the bins randomly, i.e., each ball lands into a random ...
11
votes
1answer
385 views

Can true randomness (provably) be replaced with Kolmogorov randomness for RP?

Have there been any attempts to show that Kolmogorov randomness would be sufficient for RP? Would the probability used in the statement "If the correct answer is YES, then it (the probabilistic Turing ...
12
votes
4answers
494 views

Can we fast generate perfectly uniformly mod 3 or solve NP problem?

To be honest, I don't know that much about how random number are generated (comments are welcome!) but let's assume the following theoretical model: We can get integers uniformly random from $[1,2^n]$ ...
10
votes
1answer
183 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}$. ...
10
votes
1answer
218 views

Randomness and small circuits complexity classes

Let $\mathcal{C}$ be a complexity class and $\textrm{BP-}\mathcal{C}$ be the randomized counterpart of $\mathcal{C}$ defined as $\textrm{BPP}$ with respect to $\textrm{P}$. More formally we provide ...
13
votes
1answer
297 views

Adleman's theorem over infinite semirings?

Adleman has shown in 1978 that $\mathrm{BPP}\subseteq \mathrm{P/poly}$: if a boolean function $f$ of $n$ variables can be computed by a probabilistic boolean circuit of size $M$, then $f$ can be also ...
14
votes
1answer
388 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. (...
6
votes
1answer
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 ...