Questions tagged [derandomization]
Every randomized algorithm can be simulated by a deterministic algorithm, at the expense of an exponential increase in running time. Derandomization is about converting randomized algorithms into efficient deterministic algorithms.
106
questions
26
votes
1
answer
4k
views
Is BPP vs. P a real problem after we know BPP lies in P/poly?
We know (for now about 40 years, thank Adleman, Bennet and Gill) that the inclusion BPP $\subseteq$ P/poly, and an even stronger BPP/poly $\subseteq$ P/poly hold.
The "/poly" means that we ...
- 9,269
14
votes
1
answer
458
views
Adleman's theorem over infinite semirings?
Adleman has shown in 1978 that $\mathrm{BPP}\subseteq \mathrm{P/poly}$: if a boolean function $f$ of $n$ variables can be computed by a probabilistic boolean circuit of size $M$, then $f$ can be also ...
- 6,765
6
votes
0
answers
168
views
Variation of (derandomized) Valiant-Vazirani
I am interested in the following "improvement" of the Valiant-Vazirani reduction. As pointed out here, under the right derandomization assumptions one can obtain a deterministic polynomial-...
- 988
6
votes
2
answers
349
views
What are the consequences of $BPP \neq P$?
I have seen a lot of people assume, $BPP = P$ . But to me, this seems false intuitively.(Though math is not without unintuitive results) And, to my admittedly limited understanding of the topic, the ...
- 11.4k
0
votes
0
answers
53
views
Amplifying success probability for PTMs with $poly(n) / \exp(n)$ gap?
The following is a well-known result of BPP in complexity theory, e.g., Theorem 1 and its proof from here:
Consider a probabilistic Turing Machine (PTM) $M$, and a language $L \in BPP$:
If $x \in L$ (...
2
votes
1
answer
101
views
Fine-grained average-case derandomization
Many believe derandomization with polynomial overhead, $\mathsf{P} = \mathsf{BPP}$,
because it follows from $2^{\Omega(n)}$ circuit lower bounds for $\mathsf{E}$ (IW97).
Do we have any evidence for or ...
- 176
5
votes
0
answers
114
views
How is inapproximability by polynomial size circuits sufficient for the Nisan-Wigderson generator?
I couldn't understand how exactly Yao's XOR lemma was used to prove the following claim made in the proof of Theorem 2 of the original paper describing the Nisan-Wigderson generator, so I decided to ...
- 201
0
votes
0
answers
56
views
Non-uniform consequences of uniform derandomization
Adleman showed that $\mathsf{BPP/poly} \subseteq \mathsf{P/poly}$.
Does $\mathsf{P} = \mathsf{BPP}$ have any implications for
$\mathsf{BPP}/a(n) \subseteq \mathsf{P}/a(n)$
$\mathsf{BPTIME}(t(n))/a(n) ...
- 223
39
votes
9
answers
4k
views
Efficient and simple randomized algorithms where determinism is difficult
I often hear that for many problems we know very elegant randomized algorithms, but no, or only more complicated, deterministic solutions. However, I only know a few examples for this. Most ...
- 20.9k
7
votes
2
answers
2k
views
P vs. NP and Pseudorandom Bit Generators
According to an article on pseudorandom number generators (PRNG) by Jeff Lagarias, he states that trying to prove that a PRNG is unpredictable (secure) is just "as hard" as trying to prove ...
- 131
11
votes
2
answers
877
views
Randomized algorithms not based on Schwartz-Zippel
Are there any problems that are known to be in a randomized complexity class (e.g. RNC, ZPP, RP, BPP, or even PP), but not in any lower non-randomized class (e.g. NC, P, NP), and whose membership in ...
- 17.4k
0
votes
1
answer
135
views
Derandomizing arbitrary width *read-many* and *ordered* branching programs?
Modifying following TedP
We know that derandomizing width $5\leq k\in O(1)$ read many branching programs is equivalent to $BPNC^1=NC^1$ and derandomizing width $k\in\Omega(n)$ read once ordered ...
- 12.9k
16
votes
5
answers
2k
views
Examples of successful derandomization from BPP to P
What are some major examples of successful derandomization or at least progress in showing concrete evidence towards $P=BPP$ goal (not the hardness randomness connection)?
The only example that comes ...
- 1,969
3
votes
1
answer
237
views
Family of functions with properties similar to k-wise independent hash functions
I am looking for a family of functions that has similar properties to a family of $\ell$-wise independent hash functions. The goal is to hash $\ell$ pairwise different bit strings of length $k$ to a ...
- 1,733
7
votes
2
answers
904
views
Why should we believe that $NEXP \not \subset P/poly$
I am sorry if this is not an advanced question. Most computer scientists believed that $NEXP \not \subset P/poly$ but they are not even close to this assumption. The main evidence that they are used ...
- 12.9k
33
votes
0
answers
1k
views
Is BPP= P known for ANY uniform model of computation?
Many believe that BPP $=$ P "should" hold for Turing machines. We even have some "witnesses" for this: otherwise some "strange" things would happen; see e.g. this paper by Implagliazzo and Wigderson.
...
- 1
3
votes
1
answer
441
views
Can the halting problem be solved probabilistically? [closed]
Let $H$ be the halting oracle, meaning that $H$ is a function on pairs of strings such that $H(P,X) = 1$ iff $P$ halts on $X$. A probabilistic program is a program that has (oracle) access to a random ...
- 17.4k
0
votes
1
answer
107
views
Examples for derandomization via small sample spaces [closed]
I read the book the Probabilistic Method and the lecture note Pseudorandomness to study techniques of derandomization and completed some of exercises.
I'm trying the technique of "Derandomization" ...
- 397
2
votes
2
answers
737
views
If $P=BPP$, then Is it correct that $IP=NP$?
This is my first question in this site. I ask this question since I got no comment and no answer for one year and two months in cs.stackexchange and it was automatically deleted by the system. So, ...
- 37.3k
1
vote
1
answer
124
views
Efficient randomness reduction using k-wise independence
Consider a randomized algorithm with runtime $n$, which succeeds with high probability. The algorithm uses $O(n)$ uniformly random bits.
Now it is given that we can replace these uniformly random ...
- 12.1k
1
vote
0
answers
194
views
P=BPP and derandomizing Vazirani-Valiant?
Vazirani-Valiant reduction is a randomized reduction from $SAT$ to unambiguous $SAT$.
1. Is $P=BPP$ strong enough to derandomize Vazirani-Valiant reduction?
2. If not what other ingredients are ...
- 12.9k
2
votes
0
answers
52
views
Unique SAT and ETH
We know $ETH$ is a reasonable barrier to solving $SAT$ efficiently. We have $SAT$ reducing randomly to promise unique $SAT$ by $VV$. However we do not know if $VV$ can be derandomized. Given the ...
- 12.9k
3
votes
1
answer
259
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 ...
- 2,803
1
vote
0
answers
276
views
On $BPP$ in $P^{NP}$ and $SETH$
It is believed showing $BPP$ in $P$ involves good $PRG$s and faces lower bound barriers.
Does showing $BPP$ in $P^{NP}$ which would mean $BPP\neq EXP^{NP}$ face similar $PRG$ and give lower bounds?
...
- 12.9k
2
votes
0
answers
72
views
How to improve this pseudorandom generator?
Let $f$ be a Boolean function and $\varepsilon > 0$.
There exists a pseudorandom generator $G_f: \{0,1 \}^{n^{\varepsilon}} \to \{0,1 \}^n$ with the following property.
Let $T$ be a set and $p(n)$...
CommunityBot
- 1
6
votes
1
answer
373
views
Error reduction with expanders and derandomization
In "standard" error reduction with an expander, if a randomize algorithm uses $n^d$ random bits, we need $n^d+O(n)$ random bits to achieve $2^{-O(n)}$ error probability.
Now, if the algorithm has a ...
CommunityBot
- 1
3
votes
1
answer
151
views
Algebraic construction of $\varepsilon$-biased sets
Let $\ell> 1$ be an integer and consider the mapping $\text{Tr}:\mathbb{F}_{2^\ell}\to\mathbb{F}_{2^\ell}$ defined by
$$\text{Tr}(x)=x^{2^0}+x^{2^{1}}+\cdots+x^{2^{\ell-1}}$$
It is then possible to ...
- 83
3
votes
1
answer
256
views
Lower bound on the support size of an $\epsilon$-biased distribution
Let $D$ be an $\epsilon$-biased distribution we want to show that
$$\text{Supp}(D)\geq \Omega\bigg(\frac{n}{\epsilon^2\log(\frac{1}{\epsilon})}\bigg)$$
I know that there are some proofs for this but I ...
- 4,461
0
votes
1
answer
131
views
Permuting the columns of a 0/1-matrix to avoid short segments
Consider an $n \times n$ table with $n$ stars such that each row contains at most $\log n$ stars. The stars break each row into segments (continuous parts of a row without stars). Let's call a segment ...
3
votes
0
answers
68
views
Pseudodeterministically choosing elements from efficiently samplable distributions (or, the plausibility of a weak choice principle)
Suppose we have a poly-time samplable family of distribution. I.e., a family of distributions $D_n \subseteq \{0, 1\}^{\mathsf{poly}(n)}$ and an algorithm $S$ for which $D_n = (r \leftarrow^\$ \{0,1\}^...
- 431
5
votes
1
answer
461
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 ...
- 375
9
votes
1
answer
236
views
$BPL$ with polylog random bits is in $L$
Consider a $BPL$ machine (namely, a probabilistic algorithm that uses logspace and polynomially many random bits). It is known (Saks-Zhou) that $BPL \subseteq DSPACE(log^{1.5}(n))$.
My question is ...
- 5,460
3
votes
0
answers
115
views
Does $P=BPP$ say anything about space complexity?
There are many streaming algorithms with sublinear randomized space but linear deterministic space. Does $P=BPP$ have anything to do with derandomizing space and more importantly but not related to ...
- 12.9k
16
votes
2
answers
5k
views
What is worst case complexity of number field sieve?
Given composite $N\in\Bbb N$ general number field sieve is best known factorization algorithm for integer factorization of $N$. It is a randomized algorithm and we get an expected complexity of $O\Big(...
- 201
5
votes
1
answer
353
views
From $PIT\in P$ to $P=BPP$
If $PIT$ has been derandomized then still how far would we be from showing $P=BPP$? What additional barriers need to be climbed?
- 37.3k
2
votes
0
answers
66
views
Does deterministic PIT produce deterministic irreducible polynomial generation?
In $\Bbb F_q[x]$ given $d\in\Bbb N$ there is a deterministic $O(poly(nd\log q))$ algorithm to find an irreducible polynomial with $d=deg(x)$ under $GRH$ and an unconditional randomized algorithm.
Do ...
- 12.9k
2
votes
0
answers
97
views
Scaled down and scaled up versions of Impagliazzo-Wigderson Therem
A famous theorem due to Impagliazzo and Wigderson states that if some function in $E=DTIME[2^{O(n)}]$ requires circuits of size $2^{\Omega(n)}$ then P=BPP.
When can we change $P$ with some ...
- 1,072
5
votes
1
answer
344
views
Smallest $f(n)$ such that $P/f(n) = BPP/f(n)$?
It is well-known that $\mathsf{P/poly}(n) = \mathsf{BPP/poly}(n)$.
It is a major open problem to prove the conjecture $\mathsf{P} = \mathsf{BPP}$.
$\mathsf{P} = \mathsf{BPP}$ implies $\mathsf{P}/f(n) ...
- 1,733
1
vote
0
answers
51
views
What is the best known gap between ZPP and Deterministic communication complexity? [duplicate]
I know that $N(f) \times coN(f) \geq D(f)$. This means that $ZPP(f) \geq \sqrt{D(f)}$. Is this separation tight?
- 891
3
votes
0
answers
273
views
Why are one way functions and pseudorandom number generators considered necessary or essential for derandomization?
If strong pseudorandom number generator exists then $BPP=P$ holds and if one way functions exists then $BPP\subseteq SUBEXP$ holds.
What are the best statements we have proved that come close to ...
- 12.9k
1
vote
0
answers
30
views
On $PP$ and derandomization
$PP\subseteq P/poly\implies PP=\Sigma_2\cap\Pi_2$ and $EXP\subseteq P/Poly\implies EXP=PP$ $=CH=MA$.
If $PP\subseteq P/poly$ then can $PP=\Sigma_2\cap\Pi_2=MA$ hold? Are there difficulties showing ...
- 12.9k
0
votes
1
answer
195
views
What do stronger circuit lower bounds give in terms of derandomization?
We have $EXP\not\subseteq P/poly\implies BPP\subseteq io-DTIME(2^{n^\epsilon})$ at every $\epsilon>0$.
This is essentially $DTIME(2^{O(n)})\not\subseteq P/poly\implies BPP\subseteq io-DTIME(2^{n^\...
- 5,460
24
votes
2
answers
906
views
Space efficient "industrial" unbalanced expanders
I am looking for unbalanced expanders that are "good" and "space-efficient". Specifically, a bipartite left-regular graph $G=(A,B,E)$, $|A|=n$, $|B|=m$, with left degree $d$ is a $(k,\epsilon)$-...
- 3,043
23
votes
0
answers
506
views
Fine-grained complexity of BPP
If E does not have i.o.-$2^{o(n)}$ circuits, then P=BPP, but this does not tell us about the fine-grained containments between $\mathrm{Time}(n^a)$ and $\mathrm{BPTime}(n^b)$.
Are there reasonable ...
- 2,577
3
votes
0
answers
119
views
On approximating problems in $\#P$
We know that for every counting problem $\#A$ in $\#P$, there is a probabilistic algorithm
$\mathcal C$ that on input $x$, computes with high probability a value $v$ such that $$(1 − ε)\#A(x) ≤ v ≤ (1 ...
- 12.9k
3
votes
1
answer
151
views
On $\Delta_i^P$
We know $P\subseteq NP\cap coNP\subseteq\Delta_i^P=P^{\Sigma_{i-1}^P}\subseteq \Sigma_i^P\cap\Pi_i^P=NP^{\Sigma_{i-1}^P}\cap coNP^{\Sigma_{i-1}^P}$.
If $P=BPP$ is there a 'higher' randomized class ...
- 37.3k
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 ...
- 12.9k
7
votes
0
answers
120
views
Deterministic approximation algorithms for treewidth
As far as I understand, the factor $O(\sqrt{\log OPT})$ approximation algorithm for treewidth of Feige, Hajiaghayi, and Lee is randomized, and no deterministic approximation algorithm with this factor ...
- 3,266
1
vote
1
answer
228
views
Unambiguous SAT and sparse languages
What is the consequence if there are only polynomially many 'yes' classes of instances of a language that is polynomial time reducible from a problem equivalent to UnambiguousSAT (such as possibly ...
- 37.3k
5
votes
1
answer
444
views
Implications of faster randomized $CIRCUIT SAT$ algorithm
In here on page $13$ proposition $1$ it says 'If $CIRCUIT$ $SAT$ on $n$ inputs and $m$ gates is in $2^{n^{o(1)}}poly(m)$ time, then $EXP\not\subseteq P/poly$'.
Can we have randomized $2^{n^{o(1)}}...
- 548