Questions tagged [randomized-algorithms]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
20 views

Given an input sequence of real numbers, how to find the closest sequence in a large set of sequences

We are given a set $S$ of $m\gg 1$ sequences (arrays) of $n$ elements, where each sequence $s\in S$ belongs to $\mathbb{R}^n$. In the problem I am trying to solve, in a sequential fashion, we obtain a ...
4
votes
2answers
191 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?
0
votes
0answers
44 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 ...
0
votes
0answers
79 views

Optimal $\ell^1$ sketching, including the coefficient

Let us define the sketch as mapping $\varphi:R^D\to R^d$, such that for arbitrary $x\in\mathbb{R}^D$, its $\ell^1$ norm is preserved up to $\epsilon$ error, with $1-\delta$ success probability: $$\...
1
vote
0answers
64 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 ...
3
votes
1answer
109 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 "...
3
votes
1answer
279 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 ...
0
votes
0answers
74 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-...
-1
votes
1answer
100 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\...
2
votes
1answer
91 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 ...
0
votes
0answers
44 views

Would a machine learning algorithm benefit from an “optimization oracle”?

I'm trying to understand the behavior of machine learning algorithms where the loss function is non-convex and the problem of training the ML on a specific data set is computationally hard. Now let'...
0
votes
0answers
43 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 ...
1
vote
0answers
63 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 ...
6
votes
1answer
149 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 ...
3
votes
1answer
141 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 ...
0
votes
0answers
48 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 ...
5
votes
0answers
73 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,...
1
vote
0answers
66 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
vote
1answer
98 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 ...
-4
votes
1answer
162 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 ...
1
vote
0answers
82 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 ...
5
votes
1answer
198 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
1answer
186 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 ...
2
votes
1answer
93 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
votes
1answer
173 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 ...
3
votes
0answers
443 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 ...
12
votes
5answers
2k 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 ...
1
vote
0answers
51 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$-...
0
votes
1answer
61 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
69 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
159 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
80 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 ...
3
votes
1answer
78 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 ...
5
votes
2answers
365 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 ...
-1
votes
1answer
153 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
57 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
156 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
37 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
165 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
56 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
68 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 ...
4
votes
0answers
111 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
216 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
162 views

Proving that a random permutation generator is not fair [closed]

If I'm generating random permutations using the following algorithm: ...
10
votes
1answer
337 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
780 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
405 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 ...
13
votes
2answers
822 views

What is the proof of this nonstandard version of Azuma's inequality?

In Appendix B of Boosting and Differential Privacy by Dwork et al., the authors state the following result without proof and refer to it as Azuma's inequality: Let $C_1, \dots, C_k$ be real-valued ...
1
vote
0answers
112 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
130 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 ...