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.

24 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
29
votes
0answers
700 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. ...
18
votes
0answers
386 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 ...
17
votes
0answers
291 views

Problem-Dependent Derandomization

The famous result of Impagliazzo and Wigderson in '97 cemented our belief that BPP is most likely the same as P; that is, problems that can be efficiently solved with randomness can also be ...
8
votes
0answers
280 views

Extensions of Affine Dispersers

A function $f\colon\{0,1\}^n\to\{0,1\}$ is called an affine disperser for dimension $d$, if for every affine subspace $S\subseteq \{0,1\}^n$ of dimension at least $d$, $f$ is not constant on $S$. This ...
7
votes
0answers
530 views

Narrowing the gap between BPP and RP

We do not know yet whether the 2-sided error of $BPP$ allows more computing power than the one sided error of $RP$. In view of derandomization results, the conjectured answer is no, since both classes ...
6
votes
0answers
102 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 ...
6
votes
0answers
223 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? ...
6
votes
0answers
535 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 ...
5
votes
0answers
278 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?
4
votes
0answers
167 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 ...
4
votes
0answers
170 views

Randomized Parallel Algorithm for Maximal Independent Set

There are a couple of randomized parallel algorithms for the maximal independent set problem, e.g. A Simple Parallel Algorithm for the Maximal Independent Set Problem, A fast and simple randomized ...
4
votes
0answers
139 views

Concentration Bounds for Dependent Rounding

Consider the following random process which is defined on $n$ numbers $0\leq x_1,\ldots,x_n\leq 1$: At each step, pick an arbitrary number, say $x_i$. Then randomly (and independently) change its ...
3
votes
0answers
54 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\}^...
3
votes
0answers
98 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 ...
3
votes
0answers
177 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 ...
2
votes
0answers
53 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 $...
2
votes
0answers
75 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 ...
2
votes
0answers
107 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 ...
2
votes
0answers
168 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
vote
0answers
246 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? ...
1
vote
0answers
56 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 ...
1
vote
0answers
237 views

How to derandomize the Chernoff bound?

Avi Wigderson have a paper on how to derandomize the matrix-valued Chernoff bound. I would like to know whether there exists a simple version of paper on how to derandomize the real-valued Chernoff ...
0
votes
0answers
165 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 ...
0
votes
0answers
141 views

Consequences of VP = VNP on randomness

According to the answers in posting it is possible that $\mathsf{VP} = \mathsf{VNP}$ and $\mathsf{P} \neq \mathsf{NP}$ are simultaneously correct. $\mathsf{VP} = \mathsf{VNP}$ implies $\mathsf{P/...