Skip to main content

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
20 votes
0 answers
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 ...
Bjørn Kjos-Hanssen's user avatar
13 votes
0 answers
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 ...
Artem Kaznatcheev's user avatar
12 votes
0 answers
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 ...
Kaveh's user avatar
  • 21.7k
12 votes
0 answers
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 ...
Dai Le's user avatar
  • 3,664
11 votes
0 answers
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 ...
domotorp's user avatar
  • 14k
9 votes
0 answers
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 ...
Alex Repain's user avatar
8 votes
0 answers
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 ...
Zeyu's user avatar
  • 651
7 votes
0 answers
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 ...
Igor Shinkar's user avatar
  • 1,927
7 votes
0 answers
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 '...
Omar Shehab's user avatar
7 votes
0 answers
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 ...
kbkb's user avatar
  • 171
7 votes
0 answers
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$ ...
Marc Bury's user avatar
  • 1,338
6 votes
0 answers
77 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 $...
JoelO's user avatar
  • 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? ...
Turbo's user avatar
  • 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 ...
NAg's user avatar
  • 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 ...
Konstantinos Koiliaris's user avatar
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 (...
Matt Groff's user avatar
  • 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 \...
more_question's user avatar
5 votes
0 answers
136 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 ...
SAmath's user avatar
  • 425
5 votes
0 answers
93 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 \: : \: \{0\hspace{....
user avatar
5 votes
0 answers
317 views

Geometric / Visual explanation that the average height of a random binary tree of given size $n$ is asymptotically $2\sqrt{\pi n}$

I just finished reading the proof that the average height of a random binary of given size $n$ is asymptotically $2\sqrt{\pi n}$. I'm now searching for an intuitive, or geometric, or visual proof of ...
Clément's user avatar
  • 281
4 votes
0 answers
152 views

BPP fragment of a PSPACE complete problem

Consider a PSPACE-complete problem (e.g., TQBF). Is there a sub-problem in BPP, that is not known to be in P? Is there a general technique of finding such sub-problems? Are any of them "natural" (i.e....
Shaull's user avatar
  • 5,656
4 votes
0 answers
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.
user124297's user avatar
4 votes
0 answers
189 views

On earlier references for $P=BPP$ and Kolmogorov's possible view on modern breakthroughs involving randomness?

Kolmogorov and Uspenskii in this paper 'http://epubs.siam.org/doi/pdf/10.1137/1132060' speculate P=BPP in 1986. They do this without getting into circuit lower bounds and from a different view which ...
Turbo's user avatar
  • 13k
4 votes
0 answers
68 views

Embedding of "large" graphs into random graph

Let $G \sim G_{n,p}$ be a binomial random graph and consider a sequence of graphs $\{H_n\}_n$. When $|H_n|=\mathcal{O}(1)$, then one knows the exact threshold $p_0$ for embeddabiliy of $H_n$ in $G$. ...
user136457's user avatar
4 votes
0 answers
466 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 ...
Dimitris's user avatar
  • 1,356
4 votes
0 answers
251 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 ...
NAg's user avatar
  • 666
4 votes
0 answers
152 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 in})...
user avatar
3 votes
0 answers
135 views

Inverse of leftover hash lemma

Leftover hash lemma: Let $X$ be a random variable over $X \in {\mathcal {X}}$ and let $m>0$. Let $h: {\mathcal S} \times {\mathcal X} \rightarrow \{0,1\}^m$ be a 2-universal hash function. If $m \...
delete000's user avatar
  • 828
3 votes
0 answers
114 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 ...
R B's user avatar
  • 9,458
3 votes
0 answers
171 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 ...
Phylliida's user avatar
  • 1,142
3 votes
0 answers
78 views

Are there any "two-sided" strong blenders?

My question is related to explicit extractors and strong blenders. We can define explicit strong blender in a straight forward way. I want to know if there are any known explicit strong blenders $\...
user avatar
3 votes
0 answers
247 views

Is there any research on the notion of weak isolation?

(First of all, sorry for the long article which makes you want to skip through, but since the background and motivations are important to this question or it would be nonsense to the main problem, ...
Hsien-Chih Chang 張顯之's user avatar
2 votes
1 answer
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 ...
Gleb's user avatar
  • 93
2 votes
1 answer
93 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 ...
john mangual's user avatar
1 vote
0 answers
251 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$ (...
Annonymous's user avatar
1 vote
0 answers
116 views

Random variates generation in discrete-event simulation models

In discrete-event simulation, most university textbooks (e.g., Law & Kelton, Banks etc.) state that for generating variates for each random variable (e.g., interarrival time, service time etc.) in ...
E-O's user avatar
  • 21
1 vote
0 answers
142 views

Proof of Sipser-Lautmann Theorem

I have written the following answer as an attempt to prove a variation of Sispser-Lautmann theorem, but it was rejected without any comments. I would appreciate if anyone can find the flaws in this ...
s3683168's user avatar
1 vote
0 answers
143 views

Cluster Assignment in the Stochastic Block Model

Recently, numerous papers have been published about the stochastic block model (SBM). In the literature about SBMs, a plethora of different settings are considered. I am interested in how vertices are ...
tranisstor's user avatar
1 vote
0 answers
325 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 ...
Student's user avatar
  • 654
1 vote
0 answers
101 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 ...
NAg's user avatar
  • 666
0 votes
0 answers
50 views

Does randomness help depth?

Suppose we have a $RNC^i$ or $BPNC^i$ algorithm for a problem, is it suspected that the problem has an $NC^i$ algorithm or just an $NC^j$ algorithm for some $j\geq i$? Is there any evidence for ...
Turbo's user avatar
  • 13k
0 votes
0 answers
34 views

What’s the difference between P-computable distributions and P-samplable distributions?

$\newcommand{\calC}{\mathcal{C}} \newcommand{\calD}{\mathcal{D}} \newcommand{\calE}{\mathcal{E}}$ I have two questions and the first one is presented in the title. The second one is about the ...
Heda Chen's user avatar
  • 181
0 votes
0 answers
122 views

Creating a random tree (BST) on $n$ elements using a random sequence of zeroes and ones

We have a sorted list of $n$ numbers and we shall create a BST for these numbers. We create a random sequence of zeroes and ones of length $n$. We shall make use of this random binary sequence to form ...
Vk1's user avatar
  • 137
0 votes
0 answers
76 views

Randomized Reduction for Maximization Problem

I have two maximization problems $P_1$ and $P_2$ where the decision version $L_1 = \{(x, t) : \operatorname{Val}_1(x)\ge t\}$ of $P_1$ is $\mathsf{NP}$-complete. Let $f:P_1\to P_2$ be a randomized ...
tc1729's user avatar
  • 101
0 votes
0 answers
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 ...
Morten Movik's user avatar