New answers tagged it.information-theory
2
votes
Information theoretic arguments for complexity
If that's the only information you have available, a $\Omega(n)$ lower bound will presumably follow, and presumably this will be the best bound one can hope for in general, as there are plenty of ...
Top 50 recent answers are included
Related Tags
it.information-theory × 190coding-theory × 32
shannon-entropy × 30
reference-request × 17
kolmogorov-complexity × 17
cc.complexity-theory × 16
co.combinatorics × 16
pr.probability × 16
st.statistics × 13
quantum-information × 11
cr.crypto-security × 9
communication-complexity × 9
encoding × 9
ds.algorithms × 8
quantum-computing × 7
machine-learning × 6
randomness × 6
graph-theory × 5
computability × 5
ds.data-structures × 5
boolean-functions × 5
shannon × 5
lower-bounds × 4
randomized-algorithms × 4
big-list × 4