Share Your Experience: Take the 2024 Developer Survey

# Tag Info

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,615

### 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")...
• 7,615

### 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 ...
• 8,691

### $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,615

### 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 ...
• 131

### 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 ...
• 8,691
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 ...
• 37.4k

### 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 ...
• 201
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 ...
• 17.7k
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$ ...
• 37.4k

### 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 ...
• 1,429
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 ...
• 548

### 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 ...
• 17.7k
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,938

### 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. ...
Accepted

• 12.1k
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-...
• 37.4k
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,615
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

• 1,429
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 ...
• 37.4k
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
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 \{...