# Tagged Questions

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

83 views

### How to generate Extended Finite State Machines Randomly with some properties?

This is related to my academic project An extended finite state machine is a tuple $SM=(I,S,T)$ (simplified): $I$ is the set of identifiers and it's divided into two sets Inputs and outputs, for ...
123 views

### How does one sample uniformly at random from an uncountably infinite set?

I want to know if there are any examples of polynomial time algorithms which can sample uniformly at random from a given uncountably infinite set? (assuming it is possible) Does it help if the sample ...
May be this is trivial but I do not know the answer. As far as we know $$\mathsf{BPP}\subseteq\mathsf{\Sigma}_2\cap\mathsf{\Pi}_2$$ holds. As far as we know $$\mathsf{NP}\cup\mathsf{coNP}\subseteq\... 1answer 53 views ### Shoup-style hashing without one-wayness Let H be an almost universal hash family of functions from D^2 to D. For any functions f,g \in H define the function \langle f,g \rangle : D^4 \to D by \langle f,g \rangle(a,b,c,d) \... 1answer 146 views ### Graph that maximizes minimum hitting time? Let G be some connected bidirectional (or undirected) graph. We define a random walk as a walk that begins at a vertex chosen uniformly at random, and at each step proceeds to one of its current ... 1answer 261 views ### Real number p such that a p-coin makes the undecidable decidable [closed] This is an exercice from Arora & Barak, Chapter 7 : Describe a real number p such that given a random coin that comes up "heads" with probability p, a Turing machine can decide an ... 1answer 147 views ### Evidence that there is some problem in BQP distinct from BPP? Are there any evidences (1 physics, 2 mathematics AND 3 computer science) that particular problems such as integer factorization, discrete logarithm are in BQP but not in BPP? There do not seem to be ... 1answer 139 views ### Generating uniform integers in a range from a random generator with another range Let p and q be two positive integers. I have an oracle that can generate a uniform integer in \{1, \ldots, p\}, the integers thus produced being independent across oracle calls. My goal is to ... 1answer 299 views ### What is the status of intermediate problems if P is not NP in worst way imaginable? Assume P\neq BPP\neq NP with caveat that there is a deterministic algorithm for every NP complete problem with input size n bits in 2^{(\log n)^{1+f(n)}} arithmetic operations on \log n ... 1answer 205 views ### Randomized Polynomial Hierarchy? I wonder, what would happen, if in the definition of PH (Polynomial Hierarchy, see, e.g., here), the role of NP would be replaced by RP? It seems, we could still build a hierarchy, the same ... 0answers 86 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 ... 1answer 103 views ### Finding a random regular graph with degree d I'm trying to find undirected random graphs G(V,E) with |V| = d^2 for d \in \mathbb{N} such that \forall v \in V: deg(v) = d. For d \in 2\mathbb{N} +1 this trivially is impossible as no ... 0answers 93 views ### How many neighbors does a vertex has which are closest to a source vertex in random regular graphs? Let G=(V,E) be an undirected, random r-regular graph. Let s,t\in V, and denote by N(v)=\{u\in V\mid (u,v)\in E\} the neighborhood of v. I'm looking for the distribution of the number of ... 2answers 356 views ### Suppose \mathbf{P} = \mathbf{BQP}. Then what is randomness? Would it even exist at all? DISCLAIMERI do apologize in advance if this question turns out to be silly, for some trivial reason that I may be overlooking in this moment. Suppose for a moment that \mathbf{P} = \mathbf{... 1answer 188 views ### When does randomization stops helping within PSPACE It is known that adding bounded-error randomization to PSPACE doesn't add power. That is, BPPSAPCE=PSPACE. It is famously unknown whether P=BPP, but it is known that BPP\subseteq \Sigma_2\cap \Pi_2.... 1answer 316 views ### Example of pairwise independent random process with expected max load \sqrt{n} This question was previously posted at http://math.stackexchange.com/questions/1220292/example-of-pairwise-independent-random-process-with-expected-max-load-sqrtn where it has no answers. I now ... 0answers 101 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 (... 1answer 174 views ### Deterministic Randomness Extractors I have read in several papers it is well known that deterministically extracting even one bit from a weak source is impossible. Could someone explain why? 0answers 137 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 \... 0answers 37 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 ... 1answer 156 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 ... 1answer 107 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 ... 0answers 181 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 ... 0answers 131 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 ... 1answer 122 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 ... 1answer 183 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 ... 1answer 62 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 ... 0answers 38 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 ... 1answer 136 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 ... 1answer 93 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 ... 0answers 68 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 ... 0answers 124 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 ... 1answer 320 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 ... 0answers 111 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 ... 3answers 173 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 ... 3answers 686 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 ... 1answer 177 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 ... 0answers 197 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? ... 2answers 251 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 ... 1answer 488 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 ... 1answer 79 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-... 0answers 247 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 '... 1answer 173 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. 1answer 296 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 ... 0answers 79 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 ... 1answer 233 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 ... 1answer 206 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 ... 1answer 221 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 ... 0answers 188 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 ...
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 - e^{-x/\...