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

learn more… | top users | synonyms

-1
votes
0answers
37 views

reported cases of pseudo random number generator biasing results

occasionally students ask about the theory of (pseudo) random number generators. it occurred to me it would be helpful to know significant reported cases where "not random enough" PRNGs were found to ...
3
votes
0answers
80 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 ...
1
vote
0answers
28 views

Eigenvalues of Random Regular Bipartite Graphs

I am looking for a way of getting a good estimate of the eigenvalues of random bipartite d-regular graphs. The literature has very precise values the proofs of which are very involved and since I am ...
2
votes
1answer
80 views

Extractors in Practice: How to Determine the Min-Entropy in the Source Distribution

One of the main parameters in the construction of extractors is $k$, the min-entropy of the source distribution. In practice, suppose we want to extract randomness from a given source $S$. How do we ...
4
votes
1answer
84 views

How to Quantify Entropy in a Data Set

I'm currently creating a program in Java to analysis the pathological cases of Quicksort. Namely, the transition of complexity from O(n^2) to O(nlogn) as a data set gets less ordered. Since Quicksort ...
4
votes
0answers
123 views

The largest connected component of a random subgraph

Let a graph on $|V|$ vertices and $|E|$ edges. We randomly sample $s= c \cdot \frac{|V|}{{d_{\text{av}}}}$ vertices, without replacement, where $d_{\text{av}}$ is the average degree of $G$ and $c$ is ...
6
votes
0answers
97 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 ...
5
votes
1answer
99 views

Number of points on the interior of the convex hull of a random subset

This question is in regards to the following problem: Suppose you are given a set $S$ of $n$ points in the plane. Let $R$ be a random subset of $S$ of size $r$ with all subsets of size $r$ equally ...
0
votes
0answers
80 views

Regularlity lemma and exceptional set

Regularity lemma is one of the most basic tools in algorithmic thoery and pure math theory like additive number theory and combinatorics. This lemma is stated two ways: the existence of a partion ...
0
votes
1answer
172 views

Proving properties of Random Graphs

I am asking the question on a slightly abstract level and it may depend on the specifics but it would be great to have related references or ideas. Consider the random graph model $G_{n,p}$ where its ...
1
vote
1answer
49 views

nested pseudorandom generator

Suppose we have a pseudorandom number generator PRNG with number of possible seed states K. Let us denote PRNG(k) the number yielded by the generator when the seed state is k. Here k is an integer ...
1
vote
0answers
30 views

randomness extraction of real valued sequences of numbers

I have a sequence of numbers $x_1, x_2, \dots, x_n, \dots \in \mathbb{R}$ I would like to extract fair bits from that sequence. My first thought was to use the Von Neumann extractor. For a ...
1
vote
1answer
116 views

n irrational number whose digits are pseudo-random: conceptual mismatch?

Are there irrational numbers whose digits are considered pseudo-random? Both concepts seem to be mismatched as a pseudo-random number generator typically is periodic and therefore generates a ...
0
votes
0answers
63 views

deterministic randomness extractor and privacy

Suppose $X$ is a message which takes values on the set $\{x_1, \dots, x_m\}$ with probability distribution $P_X$. We transmit the message $X$ over the channel $P_{Y|X}$ which outputs $Y$ taking ...
6
votes
0answers
63 views

Fast convergence of a contagion process in special graphs

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 ...
3
votes
0answers
105 views

Randomly Discovered Algorithm/Counterexample

I was reading Scott Aaronson's blog, and one of the comments sparked a question. "if P!=NP, this would be a general, conceptual result, so you’d expect the proof to be explanatory and in particular ...
15
votes
1answer
308 views

Natural theorems proven only “to high probability”?

There are plenty of situations where a randomized "proof" is much easier than a deterministic proof, the canonical example being polynomial identity testing. Question: Are there any natural ...
5
votes
0answers
99 views

Largest size for randomness extractor

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 ...
7
votes
3answers
159 views

Independent Node Degree in Undirected Graphs

Let $G=(V,E)$ be an undirected graph. The independent node degree $d^i(v)$ of a node $v$ is the maximum size of a set of independent neighbors of $v$. Denote by $\Delta^i(G) = \max \{d^i(v) \mid v \in ...
2
votes
3answers
609 views

Does anyone know of online video courses (in english) on randomness in theoretical computer science?

I have found some video courses like this one but they are all in russian or other languages I don't understand. I'll like to know if anyone has come across lectures (courses) of this kind which are ...
4
votes
1answer
155 views

Arithmetic Analogues of P versus BPP

In the arithmetic hierarchy, is there an analog of $P$ versus $BPP$? Particularly is there a notion of randomness there? If there is no such analogy, why is randomness in the resource bounded case ...
6
votes
0answers
170 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? ...
6
votes
2answers
225 views

Proof Strategies on P versus BPP

Typically to show $P=NP$, one has to show an NP complete problem has a polynomial time solution and to show $P\neq NP$, has to show an NP complete problem has superpolynomial lower bound. These are ...
7
votes
1answer
375 views

Is there a problem in ZPP not yet in P?

Primality was a nice problem that was in ZPP but was not known to be in P. Is there a (preferably simple to state) problem of which we can prove that it is in ZPP but we do not know whether it is in P ...
0
votes
1answer
68 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 ...
7
votes
0answers
207 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 ...
3
votes
1answer
113 views

What is full-entropy bit-strings?

I was going through the description of NIST Randomness Beacon. I would like to know the meaning of the term full-entropy bit-strings used in the third paragraph.
19
votes
1answer
265 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 ...
0
votes
0answers
78 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 ...
7
votes
1answer
207 views

Running time of randomized algorithms

This is a very basic doubt, something I've always swept under the carpet. The definition of BPP allows a machine access to random bits, which are 0 and 1 with equal probability. Many a randomized ...
5
votes
1answer
189 views

Is an infinite incomputable sequence random wrt a computable measure?

Take an arbitrary infinite binary sequence $\omega$. The interesting case is when $\omega$ is not computable. Is there a computable (semi-)measure $\mu$ such that sequence $\omega$ is $\mu$-random in ...
6
votes
1answer
183 views

correlation in an almost independent set of random variables

Suppose I have a set of $n$ binary random variables $X_1, \ldots, X_n$ that sit on a line, and assume that $\Pr(X_i=0)=\delta$ for all $i$. In addition, assume that any two subsets of variables that ...
4
votes
0answers
135 views

Sums of products of bernoulli random variables

Let $x_1 \ldots x_a,y_1 \ldots y_b$ be independent random variables taking values +1 or -1. Consider the sum $$S = \sum_{i,j} x_iy_j.$$ I wish to upper bound the probability $P(|S| > t)$. The ...
7
votes
1answer
631 views

Sum of Independent Exponential Random Variables

Can we prove a sharp concentration result on the sum of independent exponential random variables, i.e. Let $X_1, \ldots X_r$ be independent random variables such that $Pr(X_i < x) = 1 - ...
5
votes
0answers
123 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 ...
3
votes
2answers
138 views

Sort with random deviations

I'm looking for an algorithm that will take a sorted array of numbers and generate a random permutation of this array in such a way that the probability of finding a larger element earlier in a ...
8
votes
2answers
223 views

Almost universal string hashing in $Z_{2^n}$ and sublinear space

Here are two families of hash functions on strings $\vec{x} = \langle x_0 x_1 x_2 \dots x_m \rangle$: For $p$ prime and $x_i \in \mathbb{Z_p}$, $h^1_{a}(\vec{x}) = \sum a^i x_i \bmod p$ for $a \in ...
12
votes
0answers
214 views

How much independence is required for separate chaining?

If $n$ balls are placed into $n$ bins uniformly at random, the heaviest loaded bin has $O(\lg n/\lg \lg n)$ balls in it with high probability. In "The Power of Simple Tabulation Hashing", Pătraşcu and ...
10
votes
3answers
412 views

What is the fastest known simulation of BPP using Las Vegas algorithms?

$\mathsf{BPP}$ and $\mathsf{ZPP}$ are two of basic probabilistic complexity classes. $\mathsf{BPP}$ is the class of languages decided by probabilistic polynomial-time Turing algorithms where the ...
5
votes
0answers
91 views

How short can reversible representations of the n-bit primes be?

For $\: 1 < n \:$ and $\: n^{o(1)} < \sigma \leq n \:$, $\:$ how small can $L$ be for there to be for there to be an efficiently computable (deterministic) function $\;\; f \: : \: ...
7
votes
0answers
133 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 ...
1
vote
3answers
698 views

Will quantum computing pave the way for native, true RNGs?

Obviously, regular computers can't generate random numbers on their own, since they're inherently systematic machines. Would quantum computing be able to run a true RNG without a seed based off user ...
11
votes
0answers
139 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 ...
4
votes
1answer
291 views

Probabilistic circuit complexity or size of probabilistic 2-way automata for Boolean functions

If we consider circuits with arbitrary binary logic gates one can prove by a counting argument that there exists a Boolean function on $n$ variables that require a circuit of size $ \Theta \left( ...
26
votes
1answer
689 views

Consequences of $\mathsf{NP}$ containing $\mathsf{BPP}$

Many believe that $\mathsf{BPP} = \mathsf{P} \subseteq \mathsf{NP}$. However we only know that $\mathsf{BPP}$ is in the second level of polynomial hierarchy, i.e. $\mathsf{BPP}\subseteq \Sigma^ ...
10
votes
1answer
203 views

Is deterministic pseudorandomness possibly stronger than randomness in parallel?

Let the class BPNC (the combination of $\mathsf{BPP}$ and $\mathsf{NC}$) be log depth parallel algorithms with bounded error probability and access to a random source (I'm not sure if this has a ...
20
votes
2answers
550 views

Bounded depth probability distributions

Two related questions about bounded depth computing: 1) Suppose that you start with n bits, and to start with bit i can be 0 or 1 with some probability p(i), independently. (If it makes the problem ...
3
votes
1answer
197 views

Coupon collector - the effect of randomization

Given a set $S = \{1, ..., n\}$, an element is randomly drawn with replacement from $S$. Let's say we got the following sequence $X = \{x _1, ..., x _k\}$ until all elements of $S$ are seen, where $x ...
3
votes
1answer
228 views

Are randomly generated infinite patterns computable?

Fix a prefix-free universal Turing machine $U$. Consider the following random process*. The state of the process is a bit-string $s$, initialized with the empty string (say). Suppose the value of the ...
4
votes
0answers
96 views

Strong extractors with reusable seeds

I have convinced myself of the following: For every $(k,\epsilon^2\hspace{.005 in})$-strong extractor Ext, for every distribution $X$, if $\;\; k\leq$ $\:H_{\infty}$$(\hspace{.01 in}X\hspace{.015 ...