# 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
Filter by
Sorted by
Tagged with
102 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-...
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$ (...
276 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 ...
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 ...
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 ...
55 views

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 ...
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. ...
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-...
501 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 ...
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 ...
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 ...
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 ...
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 ...
1 vote
193 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 ...
1 vote
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)}}... 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}$. ... 13 votes 1 answer 422 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 ... 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? 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$... 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? 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 ... 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 ... 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 ... 