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.
105
questions
0
votes
0
answers
46
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$ (...
6
votes
2
answers
273
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 ...
- 321
2
votes
1
answer
90
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 ...
- 223
5
votes
0
answers
113
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
55
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
11
votes
2
answers
870
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 ...
- 5,531
0
votes
1
answer
133
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.8k
7
votes
2
answers
848
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 ...
- 327
3
votes
1
answer
423
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 ...
- 135
0
votes
1
answer
104
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" ...
- 490
3
votes
1
answer
220
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 ...
- 183
2
votes
2
answers
710
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, ...
- 171
1
vote
1
answer
121
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 ...
- 839
2
votes
0
answers
48
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.8k
3
votes
1
answer
248
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,451
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.8k
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)$...
- 1,973
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
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
1
answer
249
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 ...
- 83
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
437
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 ...
- 1,439
9
votes
1
answer
221
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 ...
- 383
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.8k
5
votes
1
answer
338
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?
- 12.8k
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.8k
2
votes
0
answers
95
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,062
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
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.8k
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^\...
- 12.8k
3
votes
0
answers
265
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.8k
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.
...
- 6,685
22
votes
1
answer
3k
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 work non-...
- 6,685
23
votes
0
answers
500
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,537
3
votes
0
answers
118
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.8k
3
votes
1
answer
149
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 ...
- 12.8k
4
votes
0
answers
188
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.8k
7
votes
0
answers
119
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,256
1
vote
0
answers
192
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.8k
1
vote
1
answer
218
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 ...
- 12.8k
5
votes
1
answer
441
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)}}...
- 12.8k
10
votes
1
answer
274
views
Uniform derandomisation of circuit complexity classes
Let $\mathcal{C}$ be a complexity class and $\textrm{BP-}\mathcal{C}$ be the randomized counterpart of $\mathcal{C}$ defined in the same way as $\textrm{BPP}$ is defined with respect to $\textrm{P}$. ...
- 992
13
votes
1
answer
421
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,685
7
votes
0
answers
503
views
On the shortest vector problem (is it $NP$-complete?)
Ajtai has shown that shortest vector problem is $NP$-hard by using randomized reduction from subset sum.
Has this been derandomized?
- 12.8k
3
votes
1
answer
141
views
Notion similar to k-wise independence
I want to construct a family of functions $H:\{0,1\}^n \rightarrow \{0,1\}$ with a property that is similar to k-wise independence. Specifically, I want $H$ to satisfy the following property. Let $k$ ...
- 31
10
votes
2
answers
1k
views
Is it known whether $BPP\cap NP\subseteq RP$?
The reverse inclusion is obvious, as is the fact that any self-reducible NP language in BPP is also in RP. Is this also known to hold for non-self-reducible NP languages?
- 101
2
votes
0
answers
211
views
Derandomization of Polynomial Identity Testing
There are some theorems that state $P = BPP$ if some condition is satisfied. For example, a theorem of Impagliazzo and Wigderson states tha $P=BPP$ unless $DTIME(2^{O(n)})$ has sub-exponential ...
- 1,973
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 ...
user34945
2
votes
1
answer
157
views
Minimum weights needed to derandomize weight assignment by isolation lemma
Under isolation lemma if you have a graph with $2n$ vertices and $m$ edges an isolating weight assignment can be obtained by assigning edges weights randomly from $\{1,2,\dots,2m-1,2m\}$. A weight ...
user34945
5
votes
1
answer
238
views
Connections between Graph Isomorphism and Polynomial Equivalence
Are there any relations between Graph Isomorphism problem and Polynomial Equivalence problem?
In particular does a polynomial time solution to Graph Isomorphism problem provide any evidence towards ...
- 12.8k