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.
106
questions
65
votes
1
answer
3k
views
More on PH in PP?
A recent question by Huck Bennett asking whether the class PH was contained in the class PP, received somewhat contradictory answers (all true, it seems). On one hand, several oracle results were ...
- 9,369
39
votes
9
answers
4k
views
Efficient and simple randomized algorithms where determinism is difficult
I often hear that for many problems we know very elegant randomized algorithms, but no, or only more complicated, deterministic solutions. However, I only know a few examples for this. Most ...
- 877
38
votes
3
answers
985
views
Why does randomness have stronger effect on reductions than on algorithms?
It is conjectured that randomness does not extend the power of polynomial time algorithms, that is, ${\bf P}={\bf BPP}$ is conjectured to hold. On the other hand, randomness seems to have a quite ...
- 11.3k
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.
...
- 6,685
31
votes
2
answers
2k
views
Derandomizing Valiant-Vazirani?
The Valiant-Vazirani theorem says that if there is a polynomial time algorithm (deterministic or randomized) for distinguishing between a SAT formula that has exactly one satisfying assignment, and an ...
- 3,758
31
votes
2
answers
1k
views
Hierarchy for BPP vs derandomization
In one sentence: would the existence of a hierarchy for $\mathsf{BPTIME}$ imply any derandomization results?
A related but vaguer question is: does the existence of a hierarchy for $\mathsf{BPTIME}$ ...
- 18.1k
28
votes
3
answers
2k
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 ...
- 4,439
27
votes
4
answers
2k
views
What specific evidence is there for P = RP?
RP is the class of problems decidable by a nondeterministic Turing machine that terminates in polynomial time, but that is also allowed one-sided error. P is the usual class of problems decidable by ...
- 18.9k
24
votes
2
answers
904
views
Space efficient "industrial" unbalanced expanders
I am looking for unbalanced expanders that are "good" and "space-efficient". Specifically, a bipartite left-regular graph $G=(A,B,E)$, $|A|=n$, $|B|=m$, with left degree $d$ is a $(k,\epsilon)$-...
- 971
23
votes
0
answers
501
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,537
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-...
- 6,685
21
votes
1
answer
1k
views
Consequences of $BQP \subseteq P/poly$?
While Adleman's theorem shows, that $\mathsf{BPP} \subseteq \mathsf{P}/\text{poly}$, I'm not aware of any literature investigating the possible inclusion of $\mathsf{BQP} \subseteq \mathsf{P}/\text{...
- 5,446
21
votes
1
answer
333
views
A comparison of extractors in terms of tradeoffs between time, randomness and space ?
Is there a good survey that compares different extractors, concentrators and superconcentrators and lays out the best methods in terms of the tradeoff between randomness, time and space ?
- 32k
20
votes
4
answers
815
views
Is there an equivalent to derandomization for quantum algorithms?
With some randomized algorithms you can derandomize the algorithm, removing (at a possible cost in run time) the use of random bits and maximizing some lower bound on the objective (usually computed ...
- 1,459
19
votes
3
answers
692
views
Running a BPP algorithm with a half-random, half-adversarial string
Consider the following model: an n-bit string r=r1...rn is chosen uniformly at random. Next, each index i∈{1,...,n} is put into a set A with independent probability 1/2. Finally, an adversary ...
- 13.6k
18
votes
2
answers
870
views
A Boolean function that is not constant on affine subspaces of large enough dimension
I'm interested in an explicit Boolean function $f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}$ with the following property: if $f$ is constant on some affine subspace of $\\{0,1\\}^n$, then the dimension ...
18
votes
3
answers
807
views
Does randomness buy us anything inside P?
Let $\mathsf{BPTIME}(f(n))$ be the class of the decision problems having a bounded two-sided error randomized algorithm running in time $O(f(n))$.
Do we know of any problem $Q \in \mathsf{P}$ such ...
- 951
18
votes
2
answers
2k
views
Beginner's Guide to Derandomization
I found the book Pairwise Independence and Derandomization on the subject, but it's more research-oriented than tutorial oriented.
I'm new to the subject of "Derandomization," and as such, I wanted ...
- 16.5k
17
votes
1
answer
552
views
Fooling arbitrary symmetric functions
A distribution $\mathcal{D}$ is said to $\epsilon$-fool a function $f$ if $|E_{x\in U}(f(x)) - E_{x\in \mathcal{D}}(f(x))| \leq \epsilon$. And it is said to fool a class of functions if it fools every ...
- 2,482
17
votes
0
answers
320
views
Problem-Dependent Derandomization
The famous result of Impagliazzo and Wigderson in '97 cemented our belief that BPP is most likely the same as P; that is, problems that can be efficiently solved with randomness can also be ...
- 3,758
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 ...
user34945
16
votes
3
answers
3k
views
Chernoff-type Inequality for pair-wise independent random variables
Chernoff-type inequalities are used to show that the probability that a sum of independent random variables deviates significantly from its expected value is exponentially small in the expected value ...
- 161
16
votes
2
answers
5k
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(...
user34945
16
votes
1
answer
550
views
Does Nisan's pseudo-random generator relativize?
Nisan proved in "Psuedorandom Generators for Space-Bounded Computation",
that there exists a pseudo-random generator which "fools" space-bounded computations.
Does this construction hold for every ...
16
votes
1
answer
274
views
More efficient non-uniform derandomization ?
Adleman, FOCS'78 showed that any randomized circuit for inputs of length $n$ can be non-uniformly derandomized. However, the construction effectively duplicates the original circuit $O(n)$ times, so ...
- 971
13
votes
1
answer
285
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$....
- 5,531
13
votes
1
answer
422
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 ...
- 6,685
13
votes
2
answers
589
views
Pairwise independent gaussians
Given $X_1,\ldots,X_k$ (i.i.d. gaussians with mean $0$ and variance $1$), is it possible (how?) to sample (for $m=k^2$) $Y_1, \ldots, Y_m$ such that
$Y_i$'s are pairwise independent gaussians with ...
Anindya De
12
votes
3
answers
477
views
Streaming derandomization
Stream algorithms require randomization for the most part to do anything nontrivial, and because of the small-space constraint, need PRGs that use little space. I know of two methods that have been ...
- 32k
12
votes
1
answer
1k
views
Impagliazzo and Wigderson's famous P=BPP paper
I'm reading Impagliazzo and Wigderson's famous $\mathsf P=\mathsf{BPP}$ paper in 1997. Since I'm new to this field and the paper is a concise conference version, I have difficulty following their ...
- 895
11
votes
2
answers
624
views
On fooling $AC^0$
I have a few questions regarding fooling constant depth circuits.
It's known that $\log^{O(d)}(n)$-wise independence is necessary to fool $AC^0$ circuits of depth $d$, where $n$ is the size of the ...
user1694
11
votes
3
answers
463
views
Randomized algorithms using a stack
I have developed a new derandomization technique which is aimed at recursive randomized algorithms (or) more generally randomized algorithms that use a stack. Unfortunately, I could not find natural ...
- 10.6k
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 ...
- 5,531
11
votes
1
answer
422
views
Uniform way of quantifying "branching" in nondeterministic, probabilistic, and quantum computation?
The computation of a nondeterministic Turing machine (NTM) is well known to be representable as a tree of configurations, rooted at the starting configuration. Any transition in the program is ...
- 823
11
votes
2
answers
382
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 ...
user34945
11
votes
1
answer
478
views
Borel-Cantelli Lemma and Derandomization
I was reading a paper titled Random Oracles with(out) Programmability. The last paragraph of section 2.3 reads:
[Using our novel approach] there is no
need to apply well-known classical ...
- 16.5k
10
votes
4
answers
503
views
Constructions better than a random one.
I am interested in examples of constructions in the complexity theory which are better than a random constructions.
The only one example of such construction which I know is in the field of error-...
10
votes
1
answer
436
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 ...
- 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}$. ...
- 992
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?
- 101
10
votes
1
answer
406
views
Has the derandomization of slightly non-uniform classes, e.g BPP/linear, been studied?
By BPP/linear I refer to BPP machines with linear advice, which fulfills the promise when given the "correct" advice,
and the derandomization should give us, say, a P/linear or (SUBEXP/linear) ...
10
votes
1
answer
357
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 constant ...
- 9,596
10
votes
1
answer
299
views
What are some results on algorithms that estimate polynomials over a given set of points?
There seem to be many randomized algorithms for polynomial identity testing, checking whether or not a given polynomial is zero. Are there any results of algorithms that do some sort of estimation of ...
- 109
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 ...
- 383
9
votes
0
answers
337
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 ...
- 2,247
8
votes
0
answers
584
views
Extracting randomness from Santha-Vazirani sources using a seed of constant length
This question is actually an exercise problem from Salil Vadhan's draft survey "Pseudorandomness" marked with a star (*) (see Chapter 6, Problem 6.6). I do not know other references.
We say a random ...
- 651
7
votes
2
answers
2k
views
P vs. NP and Pseudorandom Bit Generators
According to an article on pseudorandom number generators (PRNG) by Jeff Lagarias, he states that trying to prove that a PRNG is unpredictable (secure) is just "as hard" as trying to prove ...
Paul Johnson
7
votes
2
answers
849
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 ...
- 327
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 ...
- 3,256
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?
- 12.8k