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
0 votes
0 answers
46 views

Amplifying success probability for PTMs with $poly(n) / \exp(n)$ gap?

The following is a well-known result of BPP in complexity theory, e.g., Theorem 1 and its proof from here: Consider a probabilistic Turing Machine (PTM) $M$, and a language $L \in BPP$: If $x \in L$ (...
hedgehog0's user avatar
6 votes
2 answers
273 views

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

I have seen a lot of people assume, $BPP = P$ . But to me, this seems false intuitively.(Though math is not without unintuitive results) And, to my admittedly limited understanding of the topic, the ...
Colonizor48's user avatar
2 votes
1 answer
90 views

Fine-grained average-case derandomization

Many believe derandomization with polynomial overhead, $\mathsf{P} = \mathsf{BPP}$, because it follows from $2^{\Omega(n)}$ circuit lower bounds for $\mathsf{E}$ (IW97). Do we have any evidence for or ...
Nicholas Brandt's user avatar
5 votes
0 answers
113 views

How is inapproximability by polynomial size circuits sufficient for the Nisan-Wigderson generator?

I couldn't understand how exactly Yao's XOR lemma was used to prove the following claim made in the proof of Theorem 2 of the original paper describing the Nisan-Wigderson generator, so I decided to ...
Johnny's user avatar
  • 201
0 votes
0 answers
55 views

Non-uniform consequences of uniform derandomization

Adleman showed that $\mathsf{BPP/poly} \subseteq \mathsf{P/poly}$. Does $\mathsf{P} = \mathsf{BPP}$ have any implications for $\mathsf{BPP}/a(n) \subseteq \mathsf{P}/a(n)$ $\mathsf{BPTIME}(t(n))/a(n) ...
Nicholas Brandt's user avatar
11 votes
2 answers
870 views

Randomized algorithms not based on Schwartz-Zippel

Are there any problems that are known to be in a randomized complexity class (e.g. RNC, ZPP, RP, BPP, or even PP), but not in any lower non-randomized class (e.g. NC, P, NP), and whose membership in ...
Shaull's user avatar
  • 5,531
0 votes
1 answer
133 views

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

Modifying following TedP We know that derandomizing width $5\leq k\in O(1)$ read many branching programs is equivalent to $BPNC^1=NC^1$ and derandomizing width $k\in\Omega(n)$ read once ordered ...
Turbo's user avatar
  • 12.8k
7 votes
2 answers
848 views

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

I am sorry if this is not an advanced question. Most computer scientists believed that $NEXP \not \subset P/poly$ but they are not even close to this assumption. The main evidence that they are used ...
Mohsen Ghorbani's user avatar
3 votes
1 answer
423 views

Can the halting problem be solved probabilistically? [closed]

Let $H$ be the halting oracle, meaning that $H$ is a function on pairs of strings such that $H(P,X) = 1$ iff $P$ halts on $X$. A probabilistic program is a program that has (oracle) access to a random ...
user21820's user avatar
  • 135
0 votes
1 answer
104 views

Examples for derandomization via small sample spaces [closed]

I read the book the Probabilistic Method and the lecture note Pseudorandomness to study techniques of derandomization and completed some of exercises. I'm trying the technique of "Derandomization" ...
Bubble's user avatar
  • 490
3 votes
1 answer
220 views

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

I am looking for a family of functions that has similar properties to a family of $\ell$-wise independent hash functions. The goal is to hash $\ell$ pairwise different bit strings of length $k$ to a ...
Dave's user avatar
  • 183
2 votes
2 answers
710 views

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

This is my first question in this site. I ask this question since I got no comment and no answer for one year and two months in cs.stackexchange and it was automatically deleted by the system. So, ...
user777's user avatar
  • 171
1 vote
1 answer
121 views

Efficient randomness reduction using k-wise independence

Consider a randomized algorithm with runtime $n$, which succeeds with high probability. The algorithm uses $O(n)$ uniformly random bits. Now it is given that we can replace these uniformly random ...
smapers's user avatar
  • 839
2 votes
0 answers
48 views

Unique SAT and ETH

We know $ETH$ is a reasonable barrier to solving $SAT$ efficiently. We have $SAT$ reducing randomly to promise unique $SAT$ by $VV$. However we do not know if $VV$ can be derandomized. Given the ...
Turbo's user avatar
  • 12.8k
3 votes
1 answer
248 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 ...
Clement C.'s user avatar
  • 4,451
1 vote
0 answers
276 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? ...
Turbo's user avatar
  • 12.8k
2 votes
0 answers
72 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 $p(n)$...
Alexey Milovanov's user avatar
3 votes
1 answer
151 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 ...
user621824's user avatar
0 votes
1 answer
131 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 ...
Alexander S. Kulikov's user avatar
3 votes
1 answer
249 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 ...
user621824's user avatar
3 votes
0 answers
68 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\}^...
Izaak Meckler's user avatar
5 votes
1 answer
437 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 ...
Areaperson's user avatar
  • 1,439
9 votes
1 answer
221 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 ...
BharatRam's user avatar
  • 383
3 votes
0 answers
115 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 ...
Turbo's user avatar
  • 12.8k
5 votes
1 answer
338 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?
Turbo's user avatar
  • 12.8k
2 votes
0 answers
66 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 ...
Turbo's user avatar
  • 12.8k
2 votes
0 answers
95 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 ...
verifying's user avatar
  • 1,062
1 vote
0 answers
51 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?
ivmihajlin's user avatar
1 vote
0 answers
30 views

On $PP$ and derandomization

$PP\subseteq P/poly\implies PP=\Sigma_2\cap\Pi_2$ and $EXP\subseteq P/Poly\implies EXP=PP$ $=CH=MA$. If $PP\subseteq P/poly$ then can $PP=\Sigma_2\cap\Pi_2=MA$ hold? Are there difficulties showing ...
Turbo's user avatar
  • 12.8k
0 votes
1 answer
195 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^\...
Turbo's user avatar
  • 12.8k
3 votes
0 answers
265 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 ...
Turbo's user avatar
  • 12.8k
33 votes
0 answers
1k 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. ...
Stasys's user avatar
  • 6,685
22 votes
1 answer
3k 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-...
Stasys's user avatar
  • 6,685
23 votes
0 answers
500 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 ...
Dmytro Taranovsky's user avatar
3 votes
0 answers
118 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 ...
Turbo's user avatar
  • 12.8k
3 votes
1 answer
149 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 ...
Turbo's user avatar
  • 12.8k
4 votes
0 answers
188 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 ...
Turbo's user avatar
  • 12.8k
7 votes
0 answers
119 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 ...
daniello's user avatar
  • 3,256
1 vote
0 answers
192 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 ...
Turbo's user avatar
  • 12.8k
1 vote
1 answer
218 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 ...
Turbo's user avatar
  • 12.8k
5 votes
1 answer
441 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)}}...
Turbo's user avatar
  • 12.8k
10 votes
1 answer
274 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}$. ...
C.P.'s user avatar
  • 992
13 votes
1 answer
421 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 ...
Stasys's user avatar
  • 6,685
7 votes
0 answers
503 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?
Turbo's user avatar
  • 12.8k
3 votes
1 answer
141 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$ ...
NotSo Smart's user avatar
10 votes
2 answers
1k 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?
bppcapnpvsrp's user avatar
2 votes
0 answers
211 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 ...
Alexey Milovanov's user avatar
16 votes
5 answers
2k 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 ...
user avatar
2 votes
1 answer
157 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 ...
user avatar
5 votes
1 answer
238 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 ...
Turbo's user avatar
  • 12.8k