Skip to main content

Questions tagged [complexity-theory]

For questions related to the (computational) complexity (e.g. time and space complexity) of AI algorithms.

Filter by
Sorted by
Tagged with
0 votes
0 answers
90 views

Why does the algorithm in "Self-attention Does Not Need $O(n^{2})$ Memory" require $O(log n)$ memory when $k, v$ pairs are not ordered?

I am reading Self-attention Does Not Need $O(n^{2})$ Memory which proposes an algorithm that requires $O(1)$ memory for one query and $O(log n)$ memory for self-attention, in theory. In practice the ...
Daviiid's user avatar
  • 575
0 votes
0 answers
164 views

How is complex systems research interacting with AI research?

Because future AI may produce emergent phenomena, and because these are probably gaps in our current understanding of this, it feels like complex systems may be an increasingly important research ...
Single Malt's user avatar
7 votes
1 answer
5k views

Are mult-adds and FLOPs equivalent?

I am comparing different CNN architectures for edge implementation. Some papers describing architectures refer to mult-adds, like the MobileNet V1 paper, where it is claimed that this net has 569M ...
Quintus's user avatar
  • 71
2 votes
0 answers
28 views

Is there any published research on the information-carrying capacity of the human face?

Is there any published research on the information-carrying capacity of the human face? Here I mean "how much information can be conveyed via facial expressions & micro-expressions". This is a ...
DukeZhou's user avatar
  • 6,237
11 votes
1 answer
8k views

What is the time complexity of the forward pass algorithm of a feedforward neural network?

How do I determine the time complexity of the forward pass algorithm of a feedforward neural network? How many multiplications are done to generate the output?
Artificial's user avatar
2 votes
1 answer
259 views

What are some resources regarding the complexity of training neural networks?

In the paper "Provable bounds for learning some deep representations", an autoencoder like a model is constructed with discrete weights and several results are proven using some random-graph theory, ...
thecomplexitytheorist's user avatar