Questions tagged [randomized-algorithms]
An algorithm whose behaviour is determined by its input and a generator producing uniformly random numbers.
-1
votes
0answers
60 views
Approximate Multi Covering with Randomized Rounding
In the set multicover problem we are given a set $N$ of $n$ elements and a set $S$ of $m$ subsets of $N$. Additionally, each element has a coverage requirement (the number of times it has to be ...
1
vote
0answers
30 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
55 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 ...
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 ...
5
votes
0answers
141 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
63 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
131 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 ...
0
votes
0answers
82 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
74 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{...
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
135 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
26 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 ...
0
votes
0answers
61 views
Applications for non-commutative Khinchine inequality
I am looking for the applications of non-commutative Khinchine inequality (see below) in case when Rademacher random variables are tight by the condition $\sum_{i=1}^N\varepsilon_i=M, \, -N \leq M\leq ...
3
votes
1answer
121 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
46 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 ...
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 ...
3
votes
1answer
115 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
1answer
96 views
Proving that a random permutation generator is not fair [closed]
If I'm generating random permutations using the following algorithm:
...
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 ...
0
votes
2answers
430 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
283 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 ...
1
vote
0answers
67 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
123 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
257 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
96 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
204 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 ...
10
votes
1answer
180 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}$. ...
12
votes
4answers
489 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
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 ...
8
votes
2answers
547 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 ...
13
votes
1answer
294 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 ...
11
votes
1answer
384 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 ...
6
votes
1answer
187 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 ...
10
votes
1answer
130 views
Examples of the use of biased estimators
Biased estimators are useful in statistics because they can optimize mean-squared error more than what an unbiased estimator can manage. I was wondering if in theoryCS if there are any very notable ...
1
vote
1answer
84 views
Estimate the maximum frequency of substring with given length in a very long character stream
Suppose there is a very long string $S\in \Sigma^N$ with length $N$, where $\Sigma$ is a relatively small alphabet (for example, $\Sigma=\{'a', 'b', \ldots, 'z'\}$). Now, given a budget $B$, the goal ...
10
votes
1answer
279 views
When does BPP with a biased coin equal standard BPP?
Let a probabilistic Turing machine have access to an unfair coin that comes up heads with probability $p$ (flips are independent). Define $BPP_p$ as the class of languages recognizable by such a ...
3
votes
6answers
367 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 ...
3
votes
1answer
102 views
Quick Sampling from Probability Distribution: Is there a name for this algorithm?
I'm trying to quickly sample from a near-uniform discrete probability distribution exactly once without calculating the entire CDF. Here's the algorithm.
Givens:
$N,$ the number of elements to ...
2
votes
1answer
348 views
Can every distribution producible by a probabilistic PSpace machine be produced by a PSpace machine with only polynomially many random bits?
Let $M$ be a probabilistic Turing machine with a unary input $n$ whose
space is bounded by a polynomial in $n$ and
its output is a distribution $D$ over binary strings.
Note that the number of ...
1
vote
1answer
102 views
Randomized and deterministic query complexity of symmetric functions
The deterministic query complexity $D(f)$ of a symmetric function $f$ is $\Omega(n)$ (except for f = 0 or f = 1). I am wondering if the same result holds for the (bounded-error) randomized query ...
6
votes
1answer
589 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 ...
16
votes
3answers
940 views
Examples of successful derandomization from BPP to P
What are some major examples of successful derandomization or at least progress in showing concrete evidence towards $P=BPP$ goal (not the hardness randomness connection)?
The only example that comes ...
4
votes
3answers
261 views
Random grid point in a d-dimensional ball
I would like to know if there is any standard algorithm to generate
a random grid point inside a d-dimensional ball with a given radius r.
Thanks
Bin Fu
5
votes
2answers
654 views
The relationship between degree of vertex and size of dominating set
I was wondering is there any relationship between degree of vertex and size of dominating set. For example, if I know the number of vertices is $n$, and I could know each vertex in the graph has ...
7
votes
1answer
214 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 ...
1
vote
0answers
123 views
How to efficiently generate a random 0-1 matrix of a given rank
How to efficiently generate a random $n\!\times\!n$ $0$-$1$ matrix of rank $k<n$?
4
votes
0answers
58 views
Constructing a bad sequence for counter algorithm
Assume that we want to construct a sequence $s\in\{a,b\}^{N}$ such that $s$ contains exactly $n$ times the letter '$a$'.
The sequence is then feed to the following probabilistic algorithm:
...
