2026-07-23T20:44:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8359 2024-03-06T10:42:09Z ddc:004 open_access

Long Term Memory and the Densest K-Subgraph Problem Legenstein, Robert Maass, Wolfgang Papadimitriou, Christos H. Vempala, Santosh S. Brain computation long term memory assemblies association 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 plasticity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Robert Legenstein and Wolfgang Maass and Christos H. Papadimitriou and Santosh S. Vempala 2018 Is Part Of LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2018.57 urn:nbn:de:0030-drops-83593 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.57 eng https://creativecommons.org/licenses/by/3.0/legalcode