Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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.

Filter by
Sorted by
Tagged with
32 votes
2 answers

Derandomizing Valiant-Vazirani?

The Valiant-Vazirani theorem says that if there is a polynomial time algorithm (deterministic or randomized) for distinguishing between a SAT formula that has exactly one satisfying assignment, and an ...
Henry Yuen's user avatar
  • 3,798
7 votes
2 answers

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 ...
user avatar
39 votes
9 answers

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 ...
adrianN's user avatar
  • 877
31 votes
2 answers

Hierarchy for BPP vs derandomization

In one sentence: would the existence of a hierarchy for $\mathsf{BPTIME}$ imply any derandomization results? A related but vaguer question is: does the existence of a hierarchy for $\mathsf{BPTIME}$ ...
Sasho Nikolov's user avatar
27 votes
4 answers

What specific evidence is there for P = RP?

RP is the class of problems decidable by a nondeterministic Turing machine that terminates in polynomial time, but that is also allowed one-sided error. P is the usual class of problems decidable by ...
András Salamon's user avatar
22 votes
1 answer

Consequences of $BQP \subseteq P/poly$?

While Adleman's theorem shows, that $\mathsf{BPP} \subseteq \mathsf{P}/\text{poly}$, I'm not aware of any literature investigating the possible inclusion of $\mathsf{BQP} \subseteq \mathsf{P}/\text{...
Martin Schwarz's user avatar
18 votes
3 answers

Does randomness buy us anything inside P?

Let $\mathsf{BPTIME}(f(n))$ be the class of the decision problems having a bounded two-sided error randomized algorithm running in time $O(f(n))$. Do we know of any problem $Q \in \mathsf{P}$ such ...
aelguindy's user avatar
  • 951
10 votes
2 answers

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?
bppcapnpvsrp's user avatar
65 votes
1 answer

More on PH in PP?

A recent question by Huck Bennett asking whether the class PH was contained in the class PP, received somewhat contradictory answers (all true, it seems). On one hand, several oracle results were ...
Noam's user avatar
  • 9,369
38 votes
3 answers

Why does randomness have stronger effect on reductions than on algorithms?

It is conjectured that randomness does not extend the power of polynomial time algorithms, that is, ${\bf P}={\bf BPP}$ is conjectured to hold. On the other hand, randomness seems to have a quite ...
Andras Farago's user avatar
29 votes
3 answers

Problems in $\mathsf{BPP}$ not known to be in $\mathsf P$?

What problems are known to belong to $\mathsf{BPP}$ but not known to belong to $\mathsf P$? More precisely, I am interested in independent problems, that is whose derandomizations are not known to be ...
Bruno's user avatar
  • 4,514
24 votes
2 answers

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)$-...
Piotr's user avatar
  • 971
23 votes
0 answers

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 ...
Dmytro Taranovsky's user avatar
21 votes
1 answer

A comparison of extractors in terms of tradeoffs between time, randomness and space ?

Is there a good survey that compares different extractors, concentrators and superconcentrators and lays out the best methods in terms of the tradeoff between randomness, time and space ?
Suresh Venkat's user avatar
20 votes
4 answers

Is there an equivalent to derandomization for quantum algorithms?

With some randomized algorithms you can derandomize the algorithm, removing (at a possible cost in run time) the use of random bits and maximizing some lower bound on the objective (usually computed ...
Alexandre Passos's user avatar
18 votes
2 answers

Beginner's Guide to Derandomization

I found the book Pairwise Independence and Derandomization on the subject, but it's more research-oriented than tutorial oriented. I'm new to the subject of "Derandomization," and as such, I wanted ...
Sadeq Dousti's user avatar
  • 16.5k
14 votes
1 answer

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 ...
Stasys's user avatar
  • 6,765
12 votes
3 answers

Streaming derandomization

Stream algorithms require randomization for the most part to do anything nontrivial, and because of the small-space constraint, need PRGs that use little space. I know of two methods that have been ...
Suresh Venkat's user avatar
10 votes
1 answer

Can we construct a k-wise independent permutation on [n] using only constant time and space?

Let $k>0$ be a fixed constant. Given an integer $n$, we want to construct a permutation $\sigma \in S_n$ such that: The construction uses constant time and space (i.e. preprocessing takes constant ...
Sariel Har-Peled's user avatar
3 votes
1 answer

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$ ...
NotSo Smart's user avatar
2 votes
1 answer

Extractors in Practice: How to Determine the Min-Entropy in the Source Distribution

One of the main parameters in the construction of extractors is $k$, the min-entropy of the source distribution. In practice, suppose we want to extract randomness from a given source $S$. How do we ...
epsfooling's user avatar
0 votes
0 answers

P vs. NP via psuedo-random number generators [duplicate]

Possible Duplicate: P vs. NP and Pseudorandom Bit Generators Hello again , and thank you all for making this website a great vehicle for knowledge exchange. So my question is , are you trying to ...
user avatar