Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [randomness]

Randomness is a key component of probabilistic algorithms, many combinatorial aarguments, the analysis of hashing functions, and in cryptography, among other applications.

166 questions
Filter by
Sorted by
Tagged with
134 views

### Parity of the sum of pseudorandom bits over a non-sparse set of inputs

Suppose I have a pseudorandom function (in the theoretical sense) $X\colon\{0,1\}^{n+m}\rightarrow\{0,1\}$ (where $m$ is polynomial in $n$) and a non-empty set $S\subseteq\{0,1\}^m$ ($S$ is not sparse,...
280 views

### What kind of string is produced by successive application of argmax M

Fix a version of Solomonoff's universal distribution $\mathbf M$ and consider the following procedure for generating an infinite binary sequence $\omega$. Start with some $\omega_0$. Each subsequent ...
367 views

72 views

### Are there any examples of problems in ZPP not yet in P? [duplicate]

Is there a problem of which we can prove that it is in ZPP but we don’t yet know whether it’s in P or not?
388 views

### Chernoff bound for weighted sums of Bernoulli random variables

I tried to prove the following Chernoff-type bound when doing research, and found that it is of indepent interest. Let $X_1, \dots, X_n$ be independent random varibles such that each $X_i$ is a ...
2k views

### Expected number of random comparisons needed to sort a list

Consider the task of sorting a list x of size n by repeatedly querying an oracle. The oracle draws, without replacement, a random pair of indices (i, j), with i != j, and returns (i, j) if x[i] < x[...
6k views

### Truly random number generator: Turing computable?

I am seeking a definitive answer to whether or not generation of "truly random" numbers is Turing computable. I don't know how to phrase this precisely. This StackExchange question on "efficient ...
1 vote
250 views

### Converse form of Chernoff bound

Suppose $X_1,\ldots,X_n$ are i.i.d. random variables, all with mean $p$, and we have the statement that $\Pr\left[\sum_i X_i\geq 0.8n\right]\geq 0.9$, can we use this to conclude anything about $p$ (...
298 views

### Hardness assumption: an NP-complete problem whose ratio of hard instances do not tend to zero?

I am wondering about the following property $\text{(P)}$ of an $NP$-complete language $L$ \begin{align}\exists M\text{ a polytime machine}\lim_{n\to\infty}P(\text{M solves a random instance of size...
135 views

### Derandomizing arbitrary width *read-many* and *ordered* branching programs?

Modifying following TedP We know that derandomizing width $5\leq k\in O(1)$ read many branching programs is equivalent to $BPNC^1=NC^1$ and derandomizing width $k\in\Omega(n)$ read once ordered ...
128 views

87 views

### Expected value of a random experiment in a graph

I need to find the expected value of R in the random experiment below. $$R = \frac{1}{K} \sum_{C \in \mathcal{H} } \ [\frac{1}{2} |V(C)| * (|V(C)| - 1) - |C|]$$ $\mathcal{H}$ is a partition on ...
125 views

### Lower bound on the worst-case unbiased coin flips to sample a distribution?

Say that we have a distribution $\mathcal{D}$ such that all probabitilities associated with it are $p$-bit fixed precision numbers, so:  \Pr_{X\sim \mathcal{D}}[X = k] =\sum_{i = 1}^p \frac{k_i}{2^i}...
522 views

### Deterministic error reduction, state-of-the-art?

Assume one has a randomized (BPP) algorithm $A$ using $r$ bits of randomness. Natural ways to amplify its probability of success to $1-\delta$, for any chosen $\delta>0$, are Independent runs + ...
511 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 ...
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 ...
264 views

### Optimal bounds for $k$-wise non-uniform random bits

Let $k\geq 2$ be a constant (in my case, $k=4$), and $n,t \geq 0$ be integers such that $2^t \leq n$. What is the smallest sample space (or, equivalent, how many true independent random bits are ...
373 views

### Error reduction with expanders and derandomization

In "standard" error reduction with an expander, if a randomize algorithm uses $n^d$ random bits, we need $n^d+O(n)$ random bits to achieve $2^{-O(n)}$ error probability. Now, if the algorithm has a ...
4k views

### Best way to determine if a list of bytes are random?

Is there some algorithm out there that can return some value indicating a level of randomness? I believe it's called Data Entropy. I recently read this article: http://faculty.rhodes.edu/wetzel/...
190 views

### Strong seeded randomness extractors with low entropy loss

I would like to implement a strong seeded randomness extractor for flat sources as a part of my project. Most of the literature on seeded extractors is concentrated on minimizing seed length. ...
259 views

### Newman's lemma for distributional communication complexity

This may be obvious — sorry if it is. Newman's lemma (Newman91] shows that any public-coin communication protocol to compute a Boolean function $f\colon \{0,1\}^n\times\{0,1\}^n\to\{0,1\}$ can be ...
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 ...
497 views

### Random functions of low degree as a real polynomial

Is there a (reasonable) way to sample a uniformly random boolean function $f:\{0,1\}^n \to \{0,1\}$ whose degree as a real polynomial is at most $d$? EDIT: Nisan and Szegedy have shown that a ...
204 views

### Multiple independent random number streams

Having multiple streams of pseudo-random numbers known to be independent and with a uniform distribution I want to do Monte Carlo simulations in parallel. In other words, one thread will have a full-...
170 views

### Sets of solutions which it is hard to uniformly sample from, but easy to integrate functions over? (Or compute expectations over?)

I'm curious if there is a problem (e.g. something like perfect matchings on a given graph, number of solutions to a boolean equation, etc. for precise frameowork see JVV86) such that: 1) It is hard ...
472 views

### Distributions which are intractable to sample from?

I'm looking for an interesting family of probability distributions $P$ that is intractable to efficiently sample from. I'm not sure what the right notion of intractable is, though I know the notion ...
162 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.
1 vote