Skip to main content
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
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
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
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
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

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

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
  • 13k
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,560
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.2k
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
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

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

Lower bound on the support size of an $\epsilon$-biased distribution

You shouldn't have a square root. Namely, for every $\delta$-biased distribution $Z$ (using your notation), we have $$ \delta^2+2^{-n} \geq \lVert Z\rVert^2_2 \geq \frac{1}{\lvert\operatorname{supp} Z\...
Clement C.'s user avatar
  • 4,471
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
2 votes

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

No, but I don't know what would count as a proof. People conjecture P=BPP and IP$\ne$NP, if that is good enough.
domotorp's user avatar
  • 14k
2 votes
Accepted

Optimal bounds for $k$-wise non-uniform random bits

$$s = \Theta( k \cdot ( t + \log n ) )$$ As the question mentions, there is an upper bound of $s \le k\cdot\max\{t,\lceil \log_2 n \rceil\}$ bits for the seed length. Specifically, sample a random ...
Thomas's user avatar
  • 2,803
1 vote

Derandomizing arbitrary width *read-many* and *ordered* branching programs?

(Posting this as an answer because I am unable to comment.) There may be some confusion between models here. Width 5 read many branching programs capture $NC_1$, and width poly$(n)$ ordered branching ...
TedP's user avatar
  • 11
1 vote
Accepted

Algebraic construction of $\varepsilon$-biased sets

recall that $$\langle s(x,y,z),\tau\rangle=\cdots=f_z\Big(\sum_{i,j}x^iy^j\tau_{i,j}\Big)$$ if we define $p_\tau(x,y)=\sum\limits_{i,j}x^iy^j\tau_{i,j}$, we have $$\langle s(x,y,z),\tau\rangle=f_{p_\...
user621824's user avatar

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