Name
Abstract | ||
|---|---|---|
Given an intersection pattern of arbitrary sets in Euclidean space, is there an arrangement of convex open sets in Euclidean space that exhibits the same intersections? This question is combinatorial and topological in nature, but is motivated by neuroscience. Specifically, we are interested in a type of neuron called a place cell, which fires precisely when an organism is in a certain region, usually convex, called a place field. The earlier question, therefore, can be rephrased as follows: Which neural codes, that is, patterns of neural activity, can arise from a collection of convex open sets? To address this question, Giusti and Itskov proved that convex neural codes have no "local obstructions," which are defined via the topology of a code's simplicial complex. The absence of local obstructions is a necessary criterion for a code to arise from open sets that form a good cover. Here we prove that this criterion is also sufficient. The question of whether a code can be realized by a good cover thus reduces to local considerations. Algorithmically, however, this criterion-which is a method for proving a code is nonconvex-is infeasible: We prove that the good-cover decision problem is undecidable. Nonetheless, we reveal a stronger type of local obstruction that prevents a code from being convex, and prove that the corresponding decision problem is NP-hard. Our proofs use combinatorial and topological methods. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1137/18M1186563 | SIAM JOURNAL ON APPLIED ALGEBRA AND GEOMETRY |
Keywords | Field | DocType |
convex, good cover, simplicial complex, decidability, nerve lemma, neural code, place cell | Discrete mathematics,Decision problem,Combinatorics,Convexity,Euclidean space,Decidability,Simplicial complex,Code (cryptography),Mathematics,Open set,Undecidable problem | Journal |
Volume | Issue | ISSN |
3 | 1 | 2470-6566 |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aaron Chen | 1 | 0 | 0.34 |
| florian frick | 2 | 8 | 3.92 |
| Anne Shiu | 3 | 87 | 14.47 |