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
2 votes
0 answers
91 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 \...
delete000's user avatar
  • 768
6 votes
0 answers
128 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 ...
Thomas Ahle's user avatar
0 votes
1 answer
190 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_{\...
dohmatob's user avatar
  • 291
3 votes
2 answers
151 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_{\...
dohmatob's user avatar
  • 291
0 votes
1 answer
87 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 ...
randomizedalgo's user avatar
3 votes
1 answer
186 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 ...
eden hartman's user avatar
0 votes
0 answers
106 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 ...
user avatar
2 votes
0 answers
78 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 ...
Krish Singal's user avatar
0 votes
0 answers
61 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 ...
user135520's user avatar
1 vote
0 answers
80 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 ...
learning_tcs's user avatar
1 vote
1 answer
63 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: ...
Matthias's user avatar
4 votes
0 answers
78 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 ...
Theo's user avatar
  • 41
2 votes
2 answers
365 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 ...
DenLilleMand's user avatar
5 votes
0 answers
129 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 ...
Geoffrey Irving's user avatar
11 votes
2 answers
859 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 ...
Shaull's user avatar
  • 5,511
0 votes
1 answer
67 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}, \...
user1868607's user avatar
5 votes
1 answer
181 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 ...
delete000's user avatar
  • 768
2 votes
1 answer
100 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 ...
user2316602's user avatar
1 vote
0 answers
51 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. ...
Sudipta Roy's user avatar
4 votes
0 answers
106 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 ...
templatetypedef's user avatar
4 votes
0 answers
143 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 ...
zfkmz's user avatar
  • 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 ...
SagarM's user avatar
  • 706
5 votes
2 answers
265 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?
Turbo's user avatar
  • 12.6k
0 votes
0 answers
67 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 ...
Sudipta Roy's user avatar
1 vote
0 answers
86 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 ...
Springberg's user avatar
3 votes
1 answer
167 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 "...
Clement C.'s user avatar
  • 4,431
3 votes
1 answer
389 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 ...
user21820's user avatar
  • 137
0 votes
0 answers
98 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-...
Mahdi Cheraghchi's user avatar
-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\...
Sudipta Roy's user avatar
5 votes
2 answers
235 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 ...
Inuyasha Yagami's user avatar
0 votes
0 answers
46 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 ...
Annonymous's user avatar
1 vote
0 answers
97 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 ...
templatetypedef's user avatar
6 votes
1 answer
242 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 ...
Elle Najt's user avatar
  • 1,439
3 votes
1 answer
185 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 ...
D.W.'s user avatar
  • 11.3k
0 votes
0 answers
100 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 ...
gradstudent's user avatar
  • 1,443
5 votes
0 answers
87 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,...
AmeerJ's user avatar
  • 679
1 vote
0 answers
98 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 ...
gradstudent's user avatar
  • 1,443
1 vote
1 answer
115 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 ...
smapers's user avatar
  • 814
-4 votes
1 answer
392 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 ...
Reihaneh Hassanzadeh's user avatar
2 votes
0 answers
90 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 ...
prsm's user avatar
  • 29
5 votes
1 answer
220 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 ...
Hilder Vitor Lima Pereira's user avatar
2 votes
1 answer
439 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 ...
Hope's user avatar
  • 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 ...
Clement C.'s user avatar
  • 4,431
4 votes
1 answer
373 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 ...
Aryeh's user avatar
  • 10.2k
4 votes
0 answers
987 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 ...
cglacet's user avatar
  • 141
12 votes
5 answers
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 ...
Juan Miguel Arrazola's user avatar
1 vote
0 answers
64 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$-...
Sudipta Roy's user avatar
0 votes
1 answer
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 ...
Timon Knigge's user avatar
1 vote
0 answers
72 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 ...
Turbo's user avatar
  • 12.6k
5 votes
0 answers
171 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 ...
Bruno's user avatar
  • 4,440

1
2 3 4 5