Long term memory and the densest K-subgraph problem
In a recent experiment , a cell in the human medial temporal lobe (MTL)
encoding one sensory stimulus starts to also respond to a second stimulus
following a combined experience associating the two. We develop a theoretical
model predicting that an assembly of cells with exceptionally high synaptic
intraconnectivity can emerge, in response to a particular sensory experience,
to encode and abstract that experience. We also show that two such assemblies
are modified to increase their intersection after a sensory event that
associates the two corresponding stimuli. The main technical tools employed
are random graph theory, and Bernoulli approximations. Assembly creation
must overcome a computational challenge akin to the Densest K-Subgraph
problem, namely selecting, from a large population of randomly and sparsely
interconnected cells, a subset with exceptionally high density of
interconnections. We identify three mechanisms that help achieve this feat in
our model: (1) a simple two-stage randomized algorithm, and (2) the "triangle
completion bias" in synaptic connectivity  and a "birthday paradox",
while (3) the strength of these connections is enhanced through Hebbian
Reference: R. Legenstein, W. Maass, C. H. Papadimitriou, and
S. S. Vempala.
Long term memory and the densest K-subgraph problem.
In Proc. of Innovations in Theoretical Computer Science (ITCS), 2018.