Questions tagged [randomized-algorithms]
An algorithm whose behaviour is determined by its input and a generator producing uniformly random numbers.
216 questions
1
vote
0
answers
82
views
Strongest lower bound from averaging argument for probability $\geq 1-p$?
I am reading a research paper where multiple times the authors use the following, which they claim follows from an averaging argument.
Claim: Suppose $\mathcal{X}$ and $\mathcal{Y}$ are two finite ...
- 111
0
votes
0
answers
58
views
Does randomness help depth?
Suppose we have a $RNC^i$ or $BPNC^i$ algorithm for a problem, is it suspected that the problem has an $NC^i$ algorithm or just an $NC^j$ algorithm for some $j\geq i$?
Is there any evidence for ...
- 13.3k
2
votes
1
answer
419
views
A question on combinatorial algorithm
Given n sets $S_1,...,S_n$ such that $S_i \subset \{1,...,n\}$ is there a poly(n) algorithm to find $1 \leq i_1 < i_2 <.... < i_k \leq n$ such that $|\bigcup_{j=1}^k S_{i_j} | = k$ where $1 \...
- 143
4
votes
0
answers
101
views
Working out the constants and probabilities of Stockmeyer's approximate counting algorithm
Stockmeyer's 1983 result on approximate counting using a randomness states that if we have some SAT instance $x$ with $C(x)$ satisfying assignments, then we can find the minimum set of $m$ hash ...
- 191
2
votes
1
answer
160
views
Moments and Deviation (Motwani and Raghavan, 3.7)
Let $a$ and $b$ be chosen independently and uniformly at random from
$\mathbb{Z}_n=\{0,1,2,\ldots,n-1\}$, where $n$ is a prime. Suppose we
generate $t$ pseudo-random numbers from $\mathbb{Z}_n$ by ...
- 75
0
votes
0
answers
70
views
Approximation ratio of randomized rounding for integral multi-commodity flow
In [1], Raghavan and Thompson showed that we can use randomized rounding to approximate integral multi-commodity flow and routing with congestion. The result is that suppose the optimal solution is $W$...
- 68
1
vote
0
answers
45
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
2
votes
0
answers
59
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
13
votes
2
answers
703
views
What is a very simple pseudodeterministic algorithm (for educational purposes)?
Definition. A randomized algorithm for a search problem is pseudodeterministic if it produces a fixed canonical solution to the search problem with high probability.
Question. The notion of a ...
- 133
0
votes
1
answer
125
views
Generalized assignment problem with overall budget
The problem has N tasks. We have M workers. We have the cost of assigning task i to worker j. We have a profit for assigning task i to worker j. We want to assign each task to exactly one worker. One ...
4
votes
0
answers
95
views
Is the Moser-Tardos algorithm used in any real-world applications?
The Moser-Tardos algorithm can be used to construct algorithms for certain combinatorial problems. However, I'm curious about whether this algorithm is utilized in real-world systems (a SAT solver, ...
- 41
3
votes
0
answers
143
views
Inverse of leftover hash lemma
Leftover hash lemma:
Let $X$ be a random variable over $X \in {\mathcal {X}}$ and let $m>0$. Let $h: {\mathcal S} \times {\mathcal X} \rightarrow \{0,1\}^m$ be a 2-universal hash function. If $m \...
- 848
6
votes
0
answers
139
views
Consistent Sampling a Random Walk
Assume there's a random walk $S_k = X_1 + \dots + X_k$ where $X_i \in \{1, -1\}$ are uniformly iid.
I want Alice and Bob to share a function $S(k) = S_k$. A straightforward approach would be to let ...
- 958
0
votes
1
answer
206
views
Construction of a collection of subsets of $\{1,2,\ldots,n\}$ with certain properties
Let $n$ be a large positive integer. Given a collection $\mathfrak S$ of subsets of $[n] := \{1,2,\ldots,n\}$, and a vector $z=(z_1,\ldots,z_n)\in \{\pm 1\}^n$, define
$$
f_{\mathfrak S}(z) := \sum_{\...
- 291
3
votes
2
answers
166
views
Worst-case complexity of computing a certain non-standard dot product + algorithms realizing this complexity
Let $n$ be a large positive integer. Give a nonempty collection $\mathcal S$ of subsets of $[n] := \{1,2,\ldots,n\}$, define an inner-product on $\mathbb R^n$ by
\begin{eqnarray}
\langle x,y\rangle_{\...
- 291
0
votes
1
answer
163
views
Boosting the probability of success(random projections, johnson lindenstrauss)
In the simple proof of the johnson lindenstrauss lemma written by Sanjoy Dasgupta, Anupam Gupta that can be found here they state the following (p.$62$):
Repeating this projection $O(n)$ times can ...
3
votes
1
answer
246
views
Can the ellipsoid method be used with a randomized separation oracle?
Suppose we are trying to solve the following optimization problem:
$$
\text{maximize } ~~ c\cdot y
\\
\text{subject to } ~~ y\in S
$$
where the region $S$ is described by an exponential number of ...
- 101
2
votes
0
answers
106
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 ...
- 21
0
votes
0
answers
97
views
Examples of Gaussian randomized algorithms
I've been thinking about algorithms of the form where a quantity $c$ can be viewed as the expectation of some estimator (random variable) $X$ and the expectation is taken over some multivariate ...
- 111
1
vote
0
answers
99
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 ...
- 11
1
vote
1
answer
68
views
Indexed access with deletion
As part of a larger data structure that I am working on, I have the following sub-problem:
I start with $n$ slots in an array. Initially all slots are valid. I want to support two operations:
...
- 61
4
votes
0
answers
88
views
Universal Relation
In the paper Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems, the authors consider the universal relation problem in 2-party communication complexity, which is ...
- 41
2
votes
2
answers
580
views
Trying to understand the intuition behind Yao's Minimax Principle
$\newcommand{\A}{\mathcal{A}}\newcommand{\I}{\mathcal{I}}\newcommand{\E}{\mathbb{E}}\newcommand{\C}[2]{C(I_{#1},A_{#2})}$The question that I am wondering in this post is if there is any intuition to ...
- 125
5
votes
0
answers
141
views
Evaluating arithmetic circuits with stochastic rounding
Let $x_1, \ldots, x_n \in \mathbb{R}$, and let $y = f(x_i)$ be an arithmetic circuit in the $x_i$'s. That is, $f$ is a circuit of negate, add, subtract, and multiply gates. Let $X_i$ be floating ...
- 3,313
11
votes
2
answers
893
views
Randomized algorithms not based on Schwartz-Zippel
Are there any problems that are known to be in a randomized complexity class (e.g. RNC, ZPP, RP, BPP, or even PP), but not in any lower non-randomized class (e.g. NC, P, NP), and whose membership in ...
- 5,636
0
votes
1
answer
72
views
Deterministic communication complexity of refinement
A partition of $[n]$ is a collection $\mathcal{P}$ of non-empty subsets of $[n]$ such that for each $i \in [n]$ there is a unique $P \in \mathcal{P}$ with $i \in P$. For partitions $\mathcal{P}, \...
- 1,071
5
votes
1
answer
230
views
Hashing-based vs almost uniform sampling-based approximate counting
Corollary 3.6 in the UniqueSAT paper by Valiant and Vazirani [1] states:
For any $\varepsilon > 0$ there is a randomized polynomial-time TM with a SAT oracle, which given a SAT formula $f$ outputs ...
- 848
2
votes
1
answer
115
views
Property testable in sublinear time in bounded degree graphs but not in general graphs
Is there some natural property that is testable in strongly sublinear time (i.e. $O(n^{1-\epsilon})$ for some $\epsilon > 0$) in bounded-degree graphs but not in general graphs? If not such ...
- 630
1
vote
0
answers
53
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
4
votes
0
answers
122
views
Simple randomized priority queue matching the Fibonacci heap time bounds?
Since the Fibonacci heap was developed, many other priority queues have been invented with equivalent time bounds and a simpler design (e.g. hollow heaps, quake heaps, etc.).
Many classical worst-case ...
- 2,262
5
votes
0
answers
162
views
Are there any known Chernoff/Hoeffding bounds for the case of "almost independence"?
The usual statement of a Hoeffding bound (e.g. https://sites.math.washington.edu/~morrow/335_17/ineq.pdf) requires independent random variables.
My question is: Do there exist bounds similar to ...
- 307
0
votes
0
answers
62
views
Reference Request : Accessible reference for Randomised algorithms and Hashing for non-Computer Scientists?
My goal is to understand well a paper like ApproxMC. It discusses the use of Hash functions for Propositional Model Counting. In my understanding what they call hash functions are just random XOR's ...
- 716
8
votes
2
answers
458
views
Is there a linear time algorithm for integer multiplication verification?
There is a quadratic randomized algorithm for matrix product verification.
Is there a similar trick to 'verify given three integers $n,a,b$ if $n=ab$ holds?' in $O(\log n)$ time?
- 13.3k
0
votes
0
answers
81
views
A variant of randomized co-ordinate descent
Let us consider the following optimization problem.
$\mathcal{P} =\{P_1,\cdots,P_n\}$, where $P_i\subset\mathbb{R}^d$. Let $m = max_i\lvert P_i\rvert$. The goal is to find a point $c$ such that ...
- 265
1
vote
0
answers
107
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 ...
- 696
3
votes
1
answer
268
views
Converting a Bernoulli to a Gaussian
It is not hard to see that, given one sample from a univariate unit-variance Gaussian $X\sim \mathcal{N}(\mu,1)$ with unknown $\mu$ s.t. $0<|\mu|\leq 1$, one can simulate one draw from a
"...
- 4,491
3
votes
1
answer
468
views
Can the halting problem be solved probabilistically? [closed]
Let $H$ be the halting oracle, meaning that $H$ is a function on pairs of strings such that $H(P,X) = 1$ iff $P$ halts on $X$. A probabilistic program is a program that has (oracle) access to a random ...
- 134
0
votes
0
answers
119
views
Efficient sampling of primes
Using rejection sampling, it is trivial to construct a Las Vegas algorithm for sampling a uniformly random prime number less than a given $N$. What is known about sampling algorithms that run in worst-...
- 4,051
-1
votes
1
answer
108
views
Required sample size to hit certain subset of a ground set
Suppose $X$ is a set of $n$ points in $\mathbb{R}^d$ and $N_1,\cdots,N_k$ are k disjoint (unknown)subsets of $X$. There is a probability distribution $\phi$ on $X$ defined as $\phi(p) = \frac{\lvert\...
- 265
5
votes
2
answers
252
views
kmeans++ for arbitrary metric spaces and general potential function
I was reading this popular paper "k-means++: The Advantages of Careful Seeding". It appeared in SODA 2007. Since this technique is the most popular clustering technique, I am hoping that my question ...
- 1,561
0
votes
0
answers
49
views
understanding generalized coupon collector for distributions or learning mixture of distribution
Lets suppose we have a set $S=\{1,\ldots,n\}$ and $P$ is the uniform distribution over two subsets $T_1,T_2\subseteq S$, each of size $m\leq n/100$. Now, suppose somehow is given uniform samples from ...
- 251
1
vote
0
answers
123
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,262
6
votes
1
answer
281
views
Uniformly sampling or counting connected graph partitions with any number of blocks
Question: Is it possible to uniformly sample in polynomial time from the set of all connected partitions of a graph? Or is there a JVV type argument that proves this to be NP-hard?
To clarify: By a ...
- 1,479
3
votes
1
answer
209
views
Binary search on coin heads probability
Let $f:[0,1] \to [0,1]$ be a smooth, monotonically increasing function. I want to find the smallest $x$ such that $f(x) \ge 1/2$.
If I had a way to compute $f(x)$ given $x$, I could simply use ...
- 12.4k
0
votes
0
answers
123
views
Using martingale arguments to prove convergence of iterative algorithms
Can someone give me typical/educative examples of how martingales can be used to prove convergence of an iterative algorithmS?
The examples I know of can only go so far as to show that there exists ...
- 1,453
5
votes
0
answers
100
views
Relaxed minimum dominating set
(I moved this question from cs exchange to here, because it might be more on the topic here)
Let $G=(V,E)$ be a directed graph with $n$ nodes. For a subset of nodes $S\subseteq V$, let $\mathcal{N}(S,...
- 689
1
vote
0
answers
106
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
1
answer
126
views
Efficient randomness reduction using k-wise independence
Consider a randomized algorithm with runtime $n$, which succeeds with high probability. The algorithm uses $O(n)$ uniformly random bits.
Now it is given that we can replace these uniformly random ...
- 849
-4
votes
1
answer
537
views
what does NP ⊆ DTIME(...) mean?
Recently I've seen inside theory of a paper. This time complexity, DTIME, is completely new for me. Can somebody explain it?
Also, the paper shows that the misinformation containment problem cannot ...
2
votes
0
answers
97
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