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.
148
questions
0
votes
0answers
34 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 ...
0
votes
1answer
163 views
Does two-sided error have more capability than one-sided error?
From $P=RP$ extrapolation we might think $EXP=REXP$.
What evidence do we have $BPP\subseteq REXP$?
What consequence $REXP\subseteq BPP$ gives other than what $EXP\subseteq BPP$ gives?
4
votes
0answers
72 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....
0
votes
0answers
79 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 ...
0
votes
0answers
27 views
Two question regarding coreset construictions
I have two questions regarding coreset construction of clustering problem
In A Unified Framework for Approximating and Clustering Data, a very general framework is given to construct coresets for ...
0
votes
0answers
57 views
Linear time algorithm for projective clustering
There is a lot of work in clustering of high dimensional data. In case of k-means, it is shown here that one can get an $(1+\epsilon)$-approximation in linear time, yielding a PTAS, by random sampling....
12
votes
1answer
398 views
Deterministic error reduction, state-of-the-art?
Assume one has a randomized (BPP) algorithm $A$ using $r$ bits of randomness. Natural ways to amplify its probability of success to $1-\delta$, for any chosen $\delta>0$, are
Independent runs + ...
2
votes
1answer
122 views
Lower bound on the worst-case unbiased coin flips to sample a distribution?
Say that we have a distribution $\mathcal{D}$ such that all probabitilities associated with it are $p$-bit fixed precision numbers, so:
$$
\Pr_{X\sim \mathcal{D}}[X = k] =\sum_{i = 1}^p \frac{k_i}{2^i}...
2
votes
1answer
140 views
How to use a 𝑝-coin so a TM can decide an undecidable language in polynomial time? [closed]
In "Computational complexity- A modern approach" book (page 117) for the lemma 7.12 (following) the author mentioned that if the ρ is efficiently computable ρ-coin cannot give probabilistic algorithm ...
2
votes
1answer
87 views
Robustness to non-uniform randomness vs. one-sidedness
Consider any problem where, fixing two (disjoint) subsets $\mathcal{Y},\mathcal{N}\subseteq \{0,1\}^n$ of the input space, the goal is to obtain a randomized algorithm $D$ which, given a uniformly ...
2
votes
1answer
142 views
Optimal bounds for $k$-wise non-uniform random bits
Let $k\geq 2$ be a constant (in my case, $k=4$), and $n,t \geq 0$ be integers such that $2^t \leq n$.
What is the smallest sample space (or, equivalent, how many true independent random bits are ...
4
votes
1answer
115 views
Strong seeded randomness extractors with low entropy loss
I would like to implement a strong seeded randomness extractor for flat sources as a part of my project.
Most of the literature on seeded extractors is concentrated on minimizing seed length. ...
4
votes
1answer
160 views
Newman's lemma for distributional communication complexity
This may be obvious — sorry if it is.
Newman's lemma (Newman91] shows that any public-coin communication protocol to compute a Boolean function $f\colon \{0,1\}^n\times\{0,1\}^n\to\{0,1\}$ can be ...
1
vote
1answer
59 views
What forms of randomness are 'allowed' in FPRASs?
I cannot seem to find a source describing randomized approximation schemes ((F)PRAS) that tells me exactly what sort of randomness a program is allowed to use. A priori it seems to me that being able ...
5
votes
1answer
150 views
Sets of solutions which it is hard to uniformly sample from, but easy to integrate functions over? (Or compute expectations over?)
I'm curious if there is a problem (e.g. something like perfect matchings on a given graph, number of solutions to a boolean equation, etc. for precise frameowork see JVV86) such that:
1) It is hard ...
5
votes
1answer
246 views
Distributions which are intractable to sample from?
I'm looking for an interesting family of probability distributions $P$ that is intractable to efficiently sample from.
I'm not sure what the right notion of intractable is, though I know the notion ...
4
votes
0answers
148 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.
1
vote
0answers
111 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 ...
2
votes
1answer
161 views
Motivation for randomness extractors
I'm a maths masters student exploring how results in the geometry of finite fields, such as the finite field Kakeya conjecture, applies to randomness extractors. I'm not a computer scientist, and must ...
-1
votes
1answer
150 views
Application of the inequality with expectations
Let $\Vert\cdot\Vert$ is a norm in $R^n$. Let $x_1,\dots,x_N$ non-independent Rademacher random variables random variables (variables which are uniform on $\{-1, 1\}$). . By $E$ we denote an ...
1
vote
2answers
211 views
Is true randomness and the physical Church-Turing thesis incompatible?
As follow up to Does the physical Church-Turing thesis imply that all physical constants are computable?, I ask if true randomness (as predicted by QM) and the physical Church-Turing thesis are ...
9
votes
1answer
168 views
What is the probability that a random Boolean function has a trivial automorphism group?
Given a Boolean function $f$, we have the automorphism group $Aut(f) = \{\sigma \in S_n\ \mid \forall x, f(\sigma(x)) = f(x) \}$.
Are there any known bounds on $Pr_f(Aut(f) \neq 1)$? Is there ...
1
vote
0answers
129 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 ...
1
vote
0answers
150 views
An alternative model of a probabilistic Turing machine [closed]
A probabilistic Turing machine operates with an additional tape of random bits, and its output is a random variable with some distribution over the random bits. Is it also useful to talk about the ...
4
votes
0answers
170 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 ...
2
votes
1answer
275 views
Weighted balls and bins
Suppose I have $n$ balls and $n$ bins. Each ball $i$ has weight $w_i$. Let the total weight be $T = \sum_{i=1}^n w_i$. We throw the balls into the bins randomly, i.e., each ball lands into a random ...
6
votes
1answer
341 views
Where does the “intuitive” understanding of Kolmogorov complexity fails
Often, the Kolmogorov complexity of some string $x$ is defined as the length of the shortest program producing $x$, for example on wikipedia.
So to give this more formal meaning, define
$$
K'(x) := ...
4
votes
1answer
251 views
UnambiguousSAT reductions
Let $\Pi$ be an $\mathsf{NP}$-complete problem. It is standard that $3SAT$ and $\Pi$ are reducible from each other.
Let UnambiguousSAT, or USAT for short, denote the promise problem which is 3SAT but ...
5
votes
1answer
363 views
Connectivity of a random regular graph of degree $d$
An Erdos-Renyi graph over $n$ vertices and average degree $d$ is not connected whp iff $d < \log n$. I was wondering for what the degree $d$ would a random regular graph of degree $d$ be connected? ...
10
votes
1answer
404 views
Can true randomness (provably) be replaced with Kolmogorov randomness for RP?
Have there been any attempts to show that Kolmogorov randomness would be sufficient for RP? Would the probability used in the statement "If the correct answer is YES, then it (the probabilistic Turing ...
2
votes
1answer
158 views
Probability of random variable $X$ less than $max(Y_i)$
For $\lambda > \mu$, consider independent random variables (i) $X \sim Pois(\mu)$ and (ii) $Y_i \sim Pois(\lambda),\;i\in{1,2}$.
Question : Can we upper-bound the following?
$$\mathbb{P}\big(X\...
3
votes
1answer
189 views
The average number of compressible strings in a random set of random strings
In the book Elements of Information Theory (p.446), it is stated:
...although there are some simple sequences, most sequences do not have simple descriptions. Similarly, most integers are not simple. ...
4
votes
0answers
63 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$.
...
1
vote
1answer
378 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 ...
1
vote
0answers
152 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 ...
2
votes
1answer
401 views
Is there a problem currently known to be outside class $\mathsf{NP}\cup\mathsf{coNP}$ but inside $\mathsf{BPP}$?
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\...
7
votes
1answer
64 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) \...
6
votes
1answer
223 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 ...
3
votes
1answer
661 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 ...
6
votes
1answer
236 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 ...
6
votes
1answer
164 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 ...
-2
votes
1answer
329 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$ ...
12
votes
1answer
230 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 ...
5
votes
0answers
135 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 ...
2
votes
1answer
115 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 ...
3
votes
0answers
104 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 ...
8
votes
2answers
460 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{BQP}$ ...
12
votes
1answer
228 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$....
5
votes
1answer
543 views
Example of pairwise independent random process with expected max load $\sqrt{n}$
This question was previously posted at https://math.stackexchange.com/questions/1220292/example-of-pairwise-independent-random-process-with-expected-max-load-sqrtn where it has no answers. I now ...
5
votes
0answers
152 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 (...
