Questions tagged [randomized-algorithms]
An algorithm whose behaviour is determined by its input and a generator producing uniformly random numbers.
212
questions
0
votes
0
answers
39
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$...
1
vote
0
answers
41
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
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
13
votes
2
answers
664
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
56
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 ...
3
votes
0
answers
82
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, ...
- 31
3
votes
0
answers
122
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 \...
- 778
6
votes
0
answers
133
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
197
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
160
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
101
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
209
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 ...
- 91
0
votes
0
answers
121
views
Using simulated annealing within CSP scheduling problem
I'm looking to use simulated annealing to help optimise the cost of a schedule. The schedule must fit some constraints.
Let's say for the purpose of this question there are two different types of ...
user68177
2
votes
0
answers
89
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
80
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
85
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
65
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
81
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
412
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
136
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,243
11
votes
2
answers
870
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,531
0
votes
1
answer
68
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}, \...
- 921
5
votes
1
answer
191
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 ...
- 778
2
votes
1
answer
102
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
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
4
votes
0
answers
113
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,121
4
votes
0
answers
151
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 ...
- 187
0
votes
0
answers
61
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 ...
- 706
5
votes
2
answers
300
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?
- 12.8k
0
votes
0
answers
72
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
90
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 ...
- 616
3
votes
1
answer
188
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,451
3
votes
1
answer
423
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 ...
- 135
0
votes
0
answers
105
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,011
-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
244
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,531
0
votes
0
answers
47
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
107
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,121
6
votes
1
answer
249
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,439
3
votes
1
answer
196
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 ...
- 11.7k
0
votes
0
answers
107
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,443
5
votes
0
answers
92
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,...
- 679
1
vote
0
answers
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,443
1
vote
1
answer
121
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 ...
- 839
-4
votes
1
answer
470
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
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
5
votes
1
answer
230
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 ...
2
votes
1
answer
454
views
How to use a 𝑝-coin so a TM can decide an undecidable language in polynomial time? [closed]
In "Computational complexity- A modern approach" book (page 117) for the lemma 7.12 (following) the author mentioned that if the ρ is efficiently computable ρ-coin cannot give probabilistic algorithm ...
- 29
2
votes
1
answer
98
views
Robustness to non-uniform randomness vs. one-sidedness
Consider any problem where, fixing two (disjoint) subsets $\mathcal{Y},\mathcal{N}\subseteq \{0,1\}^n$ of the input space, the goal is to obtain a randomized algorithm $D$ which, given a uniformly ...
- 4,451
4
votes
1
answer
421
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 ...
- 10.3k