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
4 votes
0 answers
85 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 ...
2 votes
1 answer
136 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 ...
14 votes
1 answer
453 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 ...
0 votes
0 answers
48 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
42 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)$....
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 ...
3 votes
0 answers
126 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 \...
0 votes
1 answer
81 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 ...
13 votes
2 answers
671 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 ...
3 votes
0 answers
88 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, ...
6 votes
0 answers
135 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 ...
0 votes
1 answer
201 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_{\...
3 votes
2 answers
162 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_{\...
5 votes
1 answer
206 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 ...
0 votes
1 answer
133 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
217 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 ...
2 votes
0 answers
90 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 ...
8 votes
1 answer
152 views

Deciding DDH based in partial information

Decisional Diffie–Hellman assumption, or DDH in short, is a famous problem in cryptography. The DDH assumption holds on a cyclic group $(G,*)$ of (prime) order $q$, if for a generator $g \in G$, and ...
0 votes
0 answers
91 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 ...
1 vote
0 answers
90 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 ...
39 votes
9 answers
4k views

Efficient and simple randomized algorithms where determinism is difficult

I often hear that for many problems we know very elegant randomized algorithms, but no, or only more complicated, deterministic solutions. However, I only know a few examples for this. Most ...
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: ...
2 votes
2 answers
450 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 ...
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 ...
14 votes
1 answer
355 views

Generating Graphs with Trivial Automorphisms

I'm revising some cryptographic model. To show its inadequacy, I've devised a contrived protocol based on graph isomorphism. It is "commonplace" (yet controversial!) to assume the existence ...
5 votes
0 answers
137 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 ...
6 votes
1 answer
260 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 ...
11 votes
2 answers
874 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 ...
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}, \...
6 votes
2 answers
559 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 ...
7 votes
3 answers
828 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 ...
2 votes
1 answer
104 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 ...
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. ...
16 votes
5 answers
2k 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
0 answers
115 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 ...
5 votes
2 answers
249 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 ...
4 votes
0 answers
152 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 ...
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 ...
5 votes
2 answers
321 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 votes
1 answer
3k views

Count $k$-hop neighborhood for every vertex

For a node $v$ of a directed unweighted graph $G$, I define the $k$-hop neighborhood of $v$ as the set of vertices that are reachable from $v$ in $k$ hops or fewer (that is following a path with $k$ ...
0 votes
0 answers
74 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 ...
1 vote
0 answers
91 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
1 answer
205 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 "...
18 votes
3 answers
809 views

In what class are randomized algorithms that err with exactly 25% chance?

Suppose I consider the following variant of BPP, which let us call E(xact)BPP: A language is in EBPP if there is a polynomial time randomized TG that accepts every word of the language with exactly 3/...
3 votes
1 answer
440 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
0 answers
108 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-...
15 votes
2 answers
575 views

Reusing 5-independent hash functions for linear probing

In hash tables that resolve collisions by linear probing, in order to ensure $O(1)$ expected performance, it is both necessary and sufficient that the hash function be from a 5-independent family. (...
13 votes
2 answers
960 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 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\...
1 vote
0 answers
109 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 ...

1
2 3 4 5