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
2
votes
1answer
119 views

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

Let $k\geq 2$ be a constant (in my case, $k=4$), and $n,t \geq 0$ be integers such that $2^t \leq n$. What is the smallest sample space (or, equivalent, how many true independent random bits are ...
1
vote
0answers
246 views

On $BPP$ in $P^{NP}$ and $SETH$

It is believed showing $BPP$ in $P$ involves good $PRG$s and faces lower bound barriers. Does showing $BPP$ in $P^{NP}$ which would mean $BPP\neq EXP^{NP}$ face similar $PRG$ and give lower bounds? ...
2
votes
0answers
53 views

How to improve this pseudorandom generator?

Let $f$ be a Boolean function and $\varepsilon > 0$. There exists a pseudorandom generator $G_f: \{0,1 \}^{n^{\varepsilon}} \to \{0,1 \}^n$ with the following property. Let $T$ be a set and $...
3
votes
1answer
147 views

Algebraic construction of $\varepsilon$-biased sets

Let $\ell> 1$ be an integer and consider the mapping $\text{Tr}:\mathbb{F}_{2^\ell}\to\mathbb{F}_{2^\ell}$ defined by $$\text{Tr}(x)=x^{2^0}+x^{2^{1}}+\cdots+x^{2^{\ell-1}}$$ It is then possible to ...
0
votes
1answer
115 views

Permuting the columns of a 0/1-matrix to avoid short segments

Consider an $n \times n$ table with $n$ stars such that each row contains at most $\log n$ stars. The stars break each row into segments (continuous parts of a row without stars). Let's call a segment ...
3
votes
1answer
145 views

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

Let $D$ be an $\epsilon$-biased distribution we want to show that $$\text{Supp}(D)\geq \Omega\bigg(\frac{n}{\epsilon^2\log(\frac{1}{\epsilon})}\bigg)$$ I know that there are some proofs for this but I ...
3
votes
0answers
54 views

Pseudodeterministically choosing elements from efficiently samplable distributions (or, the plausibility of a weak choice principle)

Suppose we have a poly-time samplable family of distribution. I.e., a family of distributions $D_n \subseteq \{0, 1\}^{\mathsf{poly}(n)}$ and an algorithm $S$ for which $D_n = (r \leftarrow^\$ \{0,1\}^...
5
votes
1answer
224 views

Distributions which are intractable to sample from?

I'm looking for an interesting family of probability distributions $P$ that is intractable to efficiently sample from. I'm not sure what the right notion of intractable is, though I know the notion ...
8
votes
1answer
95 views

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

Consider a $BPL$ machine (namely, a probabilistic algorithm that uses logspace and polynomially many random bits). It is known (Saks-Zhou) that $BPL \subseteq DSPACE(log^{1.5}(n))$. My question is ...
3
votes
0answers
98 views

Does $P=BPP$ say anything about space complexity?

There are many streaming algorithms with sublinear randomized space but linear deterministic space. Does $P=BPP$ have anything to do with derandomizing space and more importantly but not related to ...
5
votes
1answer
228 views

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

If $PIT$ has been derandomized then still how far would we be from showing $P=BPP$? What additional barriers need to be climbed?
1
vote
0answers
56 views

Does deterministic PIT produce deterministic irreducible polynomial generation?

In $\Bbb F_q[x]$ given $d\in\Bbb N$ there is a deterministic $O(poly(nd\log q))$ algorithm to find an irreducible polynomial with $d=deg(x)$ under $GRH$ and an unconditional randomized algorithm. Do ...
2
votes
0answers
75 views

Scaled down and scaled up versions of Impagliazzo-Wigderson Therem

A famous theorem due to Impagliazzo and Wigderson states that if some function in $E=DTIME[2^{O(n)}]$ requires circuits of size $2^{\Omega(n)}$ then P=BPP. When can we change $P$ with some ...
1
vote
0answers
45 views

What is the best known gap between ZPP and Deterministic communication complexity? [duplicate]

I know that $N(f) \times coN(f) \geq D(f)$. This means that $ZPP(f) \geq \sqrt{D(f)}$. Is this separation tight?
0
votes
1answer
189 views

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

We have $EXP\not\subseteq P/poly\implies BPP\subseteq io-DTIME(2^{n^\epsilon})$ at every $\epsilon>0$. This is essentially $DTIME(2^{O(n)})\not\subseteq P/poly\implies BPP\subseteq io-DTIME(2^{n^\...
3
votes
0answers
176 views

Why are one way functions and pseudorandom number generators considered necessary or essential for derandomization?

If strong pseudorandom number generator exists then $BPP=P$ holds and if one way functions exists then $BPP\subseteq SUBEXP$ holds. What are the best statements we have proved that come close to ...
29
votes
0answers
699 views

Is BPP= P known for ANY uniform model of computation?

Many believe that BPP $=$ P "should" hold for Turing machines. We even have some "witnesses" for this: otherwise some "strange" things would happen; see e.g. this paper by Implagliazzo and Wigderson. ...
16
votes
1answer
788 views

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

We know (for now about 40 years, thank Adleman, Bennet and Gill) that the inclusion BPP $\subseteq$ P/poly, and an even stronger BPP/poly $\subseteq$ P/poly hold. The "/poly" means that we work non-...
18
votes
0answers
386 views

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 ...
2
votes
0answers
107 views

On approximating problems in $\#P$

We know that for every counting problem $\#A$ in $\#P$, there is a probabilistic algorithm $\mathcal C$ that on input $x$, computes with high probability a value $v$ such that $$(1 − ε)\#A(x) ≤ v ≤ (1 ...
2
votes
1answer
123 views

On $\Delta_i^P$

We know $P\subseteq NP\cap coNP\subseteq\Delta_i^P=P^{\Sigma_{i-1}^P}\subseteq \Sigma_i^P\cap\Pi_i^P=NP^{\Sigma_{i-1}^P}\cap coNP^{\Sigma_{i-1}^P}$. If $P=BPP$ is there a 'higher' randomized class ...
4
votes
0answers
167 views

On earlier references for $P=BPP$ and Kolmogorov's possible view on modern breakthroughs involving randomness?

Kolmogorov and Uspenskii in this paper 'http://epubs.siam.org/doi/pdf/10.1137/1132060' speculate P=BPP in 1986. They do this without getting into circuit lower bounds and from a different view which ...
6
votes
0answers
102 views

Deterministic approximation algorithms for treewidth

As far as I understand, the factor $O(\sqrt{\log OPT})$ approximation algorithm for treewidth of Feige, Hajiaghayi, and Lee is randomized, and no deterministic approximation algorithm with this factor ...
0
votes
0answers
164 views

P=BPP and derandomizing Vazirani-Valiant?

Vazirani-Valiant reduction is a randomized reduction from $SAT$ to unambiguous $SAT$. 1. Is $P=BPP$ strong enough to derandomize Vazirani-Valiant reduction? 2. If not what other ingredients are ...
1
vote
1answer
136 views

Unambiguous SAT and sparse languages

What is the consequence if there are only polynomially many 'yes' classes of instances of a language that is polynomial time reducible from a problem equivalent to UnambiguousSAT (such as possibly ...
5
votes
1answer
418 views

Implications of faster randomized $CIRCUIT SAT$ algorithm

In here on page $13$ proposition $1$ it says 'If $CIRCUIT$ $SAT$ on $n$ inputs and $m$ gates is in $2^{n^{o(1)}}poly(m)$ time, then $EXP\not\subseteq P/poly$'. Can we have randomized $2^{n^{o(1)}}...
9
votes
1answer
194 views

Uniform derandomisation of circuit complexity classes

Let $\mathcal{C}$ be a complexity class and $\textrm{BP-}\mathcal{C}$ be the randomized counterpart of $\mathcal{C}$ defined in the same way as $\textrm{BPP}$ is defined with respect to $\textrm{P}$. ...
13
votes
1answer
306 views

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 ...
5
votes
0answers
278 views

On the shortest vector problem (is it $NP$-complete?)

Ajtai has shown that shortest vector problem is $NP$-hard by using randomized reduction from subset sum. Has this been derandomized?
3
votes
1answer
110 views

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$ ...
10
votes
2answers
746 views

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?
2
votes
0answers
168 views

Derandomization of Polynomial Identity Testing

There are some theorems that state $P = BPP$ if some condition is satisfied. For example, a theorem of Impagliazzo and Wigderson states tha $P=BPP$ unless $DTIME(2^{O(n)})$ has sub-exponential ...
15
votes
3answers
1k views

Examples of successful derandomization from BPP to P

What are some major examples of successful derandomization or at least progress in showing concrete evidence towards $P=BPP$ goal (not the hardness randomness connection)? The only example that comes ...
2
votes
1answer
144 views

Minimum weights needed to derandomize weight assignment by isolation lemma

Under isolation lemma if you have a graph with $2n$ vertices and $m$ edges an isolating weight assignment can be obtained by assigning edges weights randomly from $\{1,2,\dots,2m-1,2m\}$. A weight ...
4
votes
1answer
192 views

Connections between Graph Isomorphism and Polynomial Equivalence

Are there any relations between Graph Isomorphism problem and Polynomial Equivalence problem? In particular does a polynomial time solution to Graph Isomorphism problem provide any evidence towards ...
5
votes
1answer
265 views

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

It is well-known that $\mathsf{P/poly}(n) = \mathsf{BPP/poly}(n)$. It is a major open problem to prove the conjecture $\mathsf{P} = \mathsf{BPP}$. $\mathsf{P} = \mathsf{BPP}$ implies $\mathsf{P}/f(n) ...
0
votes
0answers
141 views

Consequences of VP = VNP on randomness

According to the answers in posting it is possible that $\mathsf{VP} = \mathsf{VNP}$ and $\mathsf{P} \neq \mathsf{NP}$ are simultaneously correct. $\mathsf{VP} = \mathsf{VNP}$ implies $\mathsf{P/...
12
votes
2answers
2k views

What is worst case complexity of number field sieve?

Given composite $N\in\Bbb N$ general number field sieve is best known factorization algorithm for integer factorization of $N$. It is a randomized algorithm and we get an expected complexity of $O\Big(...
11
votes
2answers
306 views

Consequence of PIT over $\Bbb Z[x_1,\dots,x_n]$ not having efficient algorithm

Given $p(x_1,\dots,x_n),q(x_1,\dots,x_n)\in \Bbb Z[x_1,\dots,x_n]$ such that coefficients of $p,q$ are bounded by $B$, does $p\equiv q$ hold? Schwartz-Zippel lemma applies here since it holds for ...
-2
votes
1answer
329 views

What is the status of intermediate problems if P is not NP in worst way imaginable?

Assume $P\neq BPP\neq NP$ with caveat that there is a deterministic algorithm for every $NP$ complete problem with input size $n$ bits in $2^{(\log n)^{1+f(n)}}$ arithmetic operations on $\log n$ ...
-2
votes
1answer
226 views

Is there a randomized complexity class analogous to $\mathsf{P/Poly}$?

$\mathsf{P/Poly}$ captures those problems that could be solved in polynomial time given some precomputed polynomial number of constants. Is there an analogous complexity class in randomized world ...
10
votes
1answer
266 views

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 ...
12
votes
1answer
225 views

When does randomization stops helping within PSPACE

It is known that adding bounded-error randomization to PSPACE doesn't add power. That is, BPPSAPCE=PSPACE. It is famously unknown whether P=BPP, but it is known that $BPP\subseteq \Sigma_2\cap \Pi_2$....
10
votes
1answer
283 views

On derandomizing polynomial identity testing

In polynomial identity testing we seek a deterministic algorithm to infer equality of two polynomials $g,h\in\Bbb Z[x_1,\dots,x_n]$. Derandomizing known efficient randomized algorithms and producing ...
2
votes
1answer
215 views

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 ...
5
votes
1answer
135 views

Why does the transformation in the proof for SL=L preserve connectedness of s and t?

I'm currently working on this paper showing that $\mathcal{SL} = \mathcal{L}$. But I keep wondering how the transformation $\tau$ in definition 3.1 preserves the connectivity of $s$ and $t$. $\tau$ ...
27
votes
3answers
905 views

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 ...
1
vote
1answer
112 views

Hitting set of very restricted linear forms

We say that $f\in\mathbb{Z}[x_{1},\dots,x_{n}]$ is a {-1,0,1}-linear form if $f=\sum_{i\in S}x_{i}-\sum_{i\in T}x_{i}$ where $S,T\subseteq[n]$. A hitting set $H\subseteq\mathbb{Z}^{n}$ for {-1,0,1}-...
8
votes
0answers
280 views

Extensions of Affine Dispersers

A function $f\colon\{0,1\}^n\to\{0,1\}$ is called an affine disperser for dimension $d$, if for every affine subspace $S\subseteq \{0,1\}^n$ of dimension at least $d$, $f$ is not constant on $S$. This ...
4
votes
0answers
170 views

Randomized Parallel Algorithm for Maximal Independent Set

There are a couple of randomized parallel algorithms for the maximal independent set problem, e.g. A Simple Parallel Algorithm for the Maximal Independent Set Problem, A fast and simple randomized ...