# Questions tagged [randomized-algorithms]

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

215 questions
Filter by
Sorted by
Tagged with
55 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 ...
412 views

104 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 ...
687 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 ...
93 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, ...
136 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 ...
203 views

97 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 ...
157 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 ...
96 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
96 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 ...
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
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: ...
507 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 ...
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 ...
356 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 ...
138 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 ...
271 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 ...