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

Is BPP vs. P a real problem after we know BPP lies in P/poly?

Not sure how much of an answer this is, I'm just indulging in some rumination. Question 1 could be equally asked about P $\neq$ NP and with a similar answer -- the techniques/ideas used to prove the ...
usul's user avatar
  • 7,615
20 votes

Examples of successful derandomization from BPP to P

$SL = L$. $RL$ stands for randomized logspace and $RL=L$ is a smaller version of the problem $RP=P$. A major stepping stone was the proof of Reingold in '04 ("Undirected S-T Connectivity in Logspace")...
usul's user avatar
  • 7,615
16 votes

Examples of successful derandomization from BPP to P

There is basically only one interesting problem in BPP not known to be in P: Polynomial Identity Testing, given an algebraic circuit is the polynomial it generates identically zero. Impagliazzo and ...
Lance Fortnow's user avatar
13 votes

$BPL$ with polylog random bits is in $L$

It follows from this PRG of Nisan and Zuckerman. This paper shows that if you have an algorithm that uses space $S$ and only $\mathrm{poly}(S)$ random bits, then the number of random bits can be ...
Or Meir's user avatar
  • 5,615
13 votes

Examples of successful derandomization from BPP to P

Besides polynomial identity testing, one other very important problem known to be in BPP but not in P is approximating the permanent of a non-negative matrix or even the number of perfect matchings in ...
Raghu Meka's user avatar
11 votes

More on PH in PP?

By the work of Klivans and van Melkebeek (which relativizes), if E = DTIME($2^{O(n)}$) does not have circuits with PP gates of size $2^{o(n)}$ then PH is in PP. The contrapositive says that if PH is ...
Lance Fortnow's user avatar
10 votes
Accepted

If $P=BPP$, then Is it correct that $IP=NP$?

This is not known, but as domotorp stated, it is believed not to be the case. First, note that $\mathsf{P} = \mathsf{BPP}$ doesn't say that randomness isn't useful in any context, just in the context ...
Joshua Grochow's user avatar
10 votes

What is worst case complexity of number field sieve?

In the past few months, a version of the number field sieve has been analyzed rigorously: http://www.fields.utoronto.ca/talks/rigorous-analysis-randomized-number-field-sieve-factoring Basically the ...
djao's user avatar
  • 201
8 votes
Accepted

Can the halting problem be solved probabilistically?

It is well known that any language or function computable by a probabilistic algorithm is also computable deterministically. Here, we require that with probability $>1/2$, the algorithm outputs the ...
Emil Jeřábek's user avatar
8 votes
Accepted

Randomized algorithms not based on Schwartz-Zippel

Here is a natural problem known to be in $\mathsf{BPP}$ but not $\mathsf{RP} \cup \mathsf{coRP}$, Problem 2.6 of [1]: Given a prime $p$, integers $N$ and $d$, and a list $A$ of invertible $d \times d$ ...
Joshua Grochow's user avatar
7 votes

Is it known whether $BPP\cap NP\subseteq RP$?

As with most questions in complexity, I'm not sure there will be a full answer for a very long time. But we can at least show that the answer is non-relativizing: there is an oracle relative to which ...
Andrew Morgan's user avatar
7 votes
Accepted

Implications of faster randomized $CIRCUIT SAT$ algorithm

The gist of the proof of the proposition you're talking about is to simply cite that $EXP\subset P/poly$ implies $EXP=\Sigma_2^p$ (there is a short proof of this in the Arora and Barak book in the ...
Dylan McKay's user avatar
7 votes

Randomized algorithms not based on Schwartz-Zippel

This is a search problem rather than a decision problem: factorization of polynomials over finite fields can be done in randomized polynomial time (TFZPP) using the Cantor–Zassenhaus algorithm, but no ...
Emil Jeřábek's user avatar
6 votes
Accepted

Uniform derandomisation of circuit complexity classes

The class uniform-RNC has been studied a lot. It is an open problem whether uniform-RNC = uniform-NC. Uniform-(R)NC correspond to (randomized) PRAMs with polynomially many processors and ...
Markus Bläser's user avatar
6 votes

Minimum weights needed to derandomize weight assignment by isolation lemma

A deterministic scheme with tiny weights is easy to achieve: first, compute an arbitrary perfect matching, deterministically. Then, give the matched edges weight zero and all other edges weight one. ...
David Eppstein's user avatar
6 votes
Accepted

Why should we believe that $NEXP \not \subset P/poly$

The best evidence is in my opinion follows due to the results of Ryan Williams on even a mild speed up of $CIRCUITSAT$ provides $NQP\not\subset P/poly$ which is an extremely strong result compared to $...
Turbo's user avatar
  • 12.9k
6 votes

Why should we believe that $NEXP \not \subset P/poly$

Proving this separation seems very hard since we don't even know how to separate EXP^NP (which contains NEXP) from P/Poly, and we know that this separation does not algebrize. In addition, if EXP^NP ⊆ ...
Avi Tal's user avatar
  • 1,606
6 votes
Accepted

What are the consequences of $BPP \neq P$?

To me, the intuitive reason for believing that $BPP = P$ is that if you describe to me a randomized algorithm, then in practice, I can implement it by using a pseudorandom number generator (PRNG) ...
Timothy Chow's user avatar
  • 7,550
4 votes
Accepted

Efficient randomness reduction using k-wise independence

Yes. You can generate a random polynomial of degree $k$, then evaluate this polynomial at $n$ different points in $\tilde{O}(n)$ time using the DFT (the DFT lets you evaluate a polynomial of degree $...
D.W.'s user avatar
  • 12.1k
3 votes
Accepted

From $PIT\in P$ to $P=BPP$

If PIT over a finite field $F$ is in P, then there is a family of multilinear polynomials whose graph is decidable in $\mathsf{NE}$ but which does not have poly-size $F$-algebraic circuits (Carmosino-...
Joshua Grochow's user avatar
3 votes
Accepted

What do stronger circuit lower bounds give in terms of derandomization?

It is known that if $E = DTIME(2^{O(n)})$ is not contained in $SIZE(2^{\varepsilon \cdot n})$ for some $\varepsilon>0$ then $BPP = P$ (https://dl.acm.org/citation.cfm?id=258590). (Actually, a ...
Or Meir's user avatar
  • 5,615
3 votes
Accepted

Distributions which are intractable to sample from?

I'll expand my comment to an answer. Many combinatorial structures in graphs are actually NP-hard to sample from. The earliest example I can think of is JVV86 (Thm 5.1), which shows that there is no ...
Heng Guo's user avatar
  • 375
3 votes

Smallest $f(n)$ such that $P/f(n) = BPP/f(n)$?

Nothing better than $\mathbf{BPP}/\text{poly} = \mathbf{P}/\text{poly}$ is known. On the other hand, better results are known in the space bounded setting. Fortnow and Klivans showed that $\mathbf{BPL}...
William Hoza's user avatar
  • 1,743
3 votes

Efficient and simple randomized algorithms where determinism is difficult

Finding square roots modulo prime number: https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm
mercury0114's user avatar
3 votes

Adleman's theorem over infinite semirings?

This is only a partial answer to your general question (I'm not sure what a fully general formulation would be), but it suggests that working over sufficiently nice infinite semirings while ...
Andrew Morgan's user avatar
3 votes
Accepted

Fine-grained average-case derandomization

There are some recent works on this topic, for example [DMOZ20], [CT21a], and [CT21b]. For worst-case derandomization: following [DMOZ20], [CT21a] showed that under plausible hardness assumption (...
Lijie Chen's user avatar
2 votes

Notion similar to k-wise independence

You can do it with the isolation lemma. Here are the important details (admittedly hastily written): We'll imagine picking a hash function from $H$ as follows: first, pick $w_1^0,\ldots,w_n^0,w_1^1,\...
Andrew Morgan's user avatar
2 votes
Accepted

Unambiguous SAT and sparse languages

It puts NP into P/poly, and therefore collapses PH to its second level. By basically the same as the usual proof that BPP is in P/poly, there is polynomial advice that provides good random bits for ...
Joshua Grochow's user avatar
2 votes
Accepted

Examples for derandomization via small sample spaces

Here is an example from low degree testing literature: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/BSVW03/BSVW03.pdf. High-level summary: Consider BLR linearity testing algorithm that given ...
A.2's user avatar
  • 397
2 votes

Family of functions with properties similar to k-wise independent hash functions

Let $m = 1 + \log \ell$. Identify a hash function $h \colon \{0, 1\}^k \to \{0, 1\}^m$ with its $n$-bit truth table $h \in \{0, 1\}^n$ where $n = m \cdot 2^k$. Our hash family $\mathcal{H} \subseteq \{...
William Hoza's user avatar
  • 1,743

Only top scored, non community-wiki answers of a minimum length are eligible