New answers tagged lower-bounds
2
In the comments I said that $n$ is the number of different possible outcomes of a minimum algorithm and that this is only a lower bound for the number of leaves of the decision trees of the comparison-based minimum algorithms (in which nodes represent the comparisons and edges the results of those comparisons). This is an application of Lemma 1 here, which ...
0
Interesting question!
The way I understand this is that on sorting it happens that one comparison allows you to discard approximately a half of the possible answers. However on the case of the minimum, one comparison allows you to discard only one possible answer in the worst case. Therefore a proper decision tree for the problem of finding the minimum ...
1
In order to bound the number of functions computed by circuits of size $k$, you have at least two options:
Construct a large number of circuits of size $k$, which by construction compute different functions.
Consider a natural probability distribution on circuits of size $k$, and estimate the probability that two random circuits compute the same function.
...
Top 50 recent answers are included
