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.

45 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
812 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 ...
• 4,485
181 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 ...
• 10.3k
278 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 ...
• 21.7k
376 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 ...
• 3,664
300 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 ...
• 14k
507 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 ...
585 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 ...
• 651
240 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 ...
• 1,927
281 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 '...
• 651
158 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 ...
• 171
196 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$ ...
• 1,338
77 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 $... • 531 6 votes 0 answers 233 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? ... • 13k 6 votes 0 answers 185 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 ... • 666 5 votes 0 answers 158 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 ... 5 votes 0 answers 158 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 (... • 2,100 5 votes 0 answers 165 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 ...