23
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 ...
- 7,788
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 ...
- 5,675
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 ...
- 38.5k
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 ...
- 18.6k
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$ ...
- 38.5k
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 ...
- 573
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 ...
- 18.6k
7
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 ⊆ ...
- 1,616
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 $...
- 13.3k
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) ...
- 7,620
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 ...
- 2,958
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 $...
- 12.4k
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 (...
- 176
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 ...
- 1,439
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}...
- 1,763
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
- 131
3
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 ...
- 2,813
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-...
- 38.5k
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 ...
- 5,675
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 ...
- 375
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 ...
- 38.5k
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\...
- 4,491
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 ...
- 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 \{...
- 1,763
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.
- 14.2k
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 ...
- 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_\...
- 83
1
vote
Permuting the columns of a 0/1-matrix to avoid short segments
The algorithm below runs in time $O(n\log n)$, but not $O(n)$. On the other hand, it permutes the columns in such a way that there are only $O(\log^2n \cdot\log\log n)$ short segments in the end.
...
1
vote
Accepted
On $\Delta_i^P$
Yes, one can define $BP\Delta_i^P$. Indeed, for any class $\mathcal{C}$ one can define $\mathsf{BP} \cdot \mathcal{C}$ as $L \in \mathsf{BP} \cdot \mathcal{C}$ iff there is a language $L' \in \mathcal{...
- 38.5k
1
vote
Efficient and simple randomized algorithms where determinism is difficult
Finding a 2-approximate weighted vertex cover is known to be in RNC [1]. I don't think it is known to be in NC. That is, the problem has a randomized poly-log-time poly-processor algorithm, but I don'...
- 10.9k
Only top scored, non community-wiki answers of a minimum length are eligible