# 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.

41 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
751 views

### Weighted Hamming distance

Basically my question is, what kind of geometry do we get if we use a "weighted" Hamming distance. This is not necessarily Theoretical Computer Science but I think similar things come up ...
361 views

### Oracle relative to which MA does not have a complete problem?

Babai introduced a hierarchy of complexity classes based on public-coin randomized interactive proof systems, so called Arthur-Merlin games. The game is played by powerful but untrustworthy wizard ...
270 views

### Conditional density of primes

We have some theorems about the density of prime numbers, the most famous one is probably the prime number theorem. My question is about the density of primes when we choose random numbers from a ...
158 views

### Generating a random graph with constraints on spectrum

Consider two sequences $u_1 \geq u_2 \geq ... \geq u_n$ and $l_1 \geq l_2 \geq ... \geq l_n$ with $u_i \geq l_i$ for every $i$. Let $\mathcal{G}(l_{1:n},u_{1:n})$ be all undirected unweighted simple ...
140 views

### Provable BPP Hierarchy

No Time Hierarchy theorem is known for $\mathsf{BPTIME}$, however, consider the following simple modification of the definition: A language is in $\mathsf{ProvableBPTIME}[f(n)]$ if there is a ...
489 views

### Statistical relationship between diameter and density in strongly connected random digraphs

I would like to know if there is any known relation between diameter and density in (connected) simple digraphs. Asymptotic results for n→∞, statistical, conditioned results that would restrict the ...
264 views

### Implication of Bell test loopholes on Vazirani-Vidick random sequence generation scheme

I am trying to imagine what would be the implications of the loopholes on Bell test on the random sequence generation scheme proposed by Vazirani and Vidick (VV protocol) in the paper titled '...
152 views

### Size complexity of probabilistic two-way automata for a Boolean function

I'm interested in computing Boolean functions $f:\{0,1\}^n\rightarrow\{0,1\}$ with two-way finite automata and I will measure the complexity of a Boolean function by the number of states for the ...
191 views

### Communication complexity of random functions with limited independence

Let $X_0, \ldots, X_{2^n-1}$ be $k$-wise independent random $0/1$ variables over a sample space $\Omega$ and $Prob \left[ X_i = 1 \right] = p$ for every $i$ and some $0 < p < 1$. Let assume $n$ ...
557 views

### Extracting randomness from Santha-Vazirani sources using a seed of constant length

This question is actually an exercise problem from Salil Vadhan's draft survey "Pseudorandomness" marked with a star (*) (see Chapter 6, Problem 6.6). I do not know other references. We say a random ...
193 views

### Bias of a random boolean low degree polynomial

What is the bias of a random Boolean function that can be represented as a low degree polynomial over the reals, i.e. has low Fourier degree? More specifically, is it true that if we take a uniformly ...
72 views

The process: Given is a clique $C_n$ of size $n$. Consider the following synchronous process, also known as the (synchronous) voter model (e.g., Even-Dar and Shapira): Define an indicator variable $... 0answers 229 views ### Physical Proof for P versus BPP Lipton asks for a physical proof of$P\neq NP$. Can we even ask for a physical proof for understanding$P=BPP$or$P\neq BPP$? Is there anything in physics that lets us avoid randomness? ... 0answers 182 views ### Squares of random binary matrices Are there results/techniques pertaining to the analysis of squares of random matrices ? More specifically, let$A$be an$n\times n$matrix such that each entry is$1$or$-1$independently and with ... 0answers 140 views ### Random Sampling Threshold to Get a Connected Induced Subgraph Working on network design this summer I have come across certain applications that have inspired me to ask the following question: Given an undirected connected graph$G=(V,E)$what is the minimum ... 0answers 157 views ### Satisfiability threshold and partially random formulas My understanding is that if we have a totally random k-SAT formula, for a ratio$m < \alpha n$far enough below the satisfiability threshold, we can solve for satisfiability in polynomial time (... 0answers 153 views ### Reconstruction of sparse vectors from random matrices In the paper [A], the following linear algebra result (Lemma 5 in [A]) is stated as being well known. Note that a vector is$s$-sparse if it contains at most$s$non-zero entries. Lemma: Let$1 \...
Suppose we have a source $X$ with min-entropy $\ell$. A randomness extractor is defined as a function $f$ which satisfies the total variation $||f(X, R)-U_M||_{TV}\leq \epsilon$ where $R$ is an ...