Abstract We study several model-theoretic aspects of W $$^*$$ ∗ -probability spaces, that is, $$\sigma $$ σ -finite von Neumann algebras equipped with a faithful normal state. We first study the existentially closed W $$^*$$ ∗ -spaces and prove several structural results about such spaces, including that they are type III $$_1$$ 1 factors that tensorially absorb the Araki–Woods factor $$R_\infty $$ R ∞ . We also study the existentially closed objects in the restricted class of W $$^*$$ ∗ -probability spaces with Kirchberg’s QWEP property, proving that $$R_\infty $$ R ∞ itself is such an existentially closed space in this class. Our results about existentially closed probability spaces imply that the class of type III $$_1$$ 1 factors forms a $$\forall _2$$ ∀ 2 -axiomatizable class. We show that for $$\lambda \in (0,1)$$ λ ∈ ( 0 , 1 ) , the class of III $$_\lambda $$ λ factors is not $$\forall _2$$ ∀ 2 -axiomatizable but is $$\forall _3$$ ∀ 3 -axiomatizable; this latter result uses a version of Keisler’s Sandwich theorem adapted to continuous logic. Finally, we discuss some results around elementary equivalence of III $$_\lambda $$ λ factors. Using a result of Boutonnet, Chifan, and Ioana, we show that, for any $$\lambda \in (0,1)$$ λ ∈ ( 0 , 1 ) , there is a family of pairwise non-elementarily equivalent III $$_\lambda $$ λ factors of size continuum. While we cannot prove the same result for III $$_1$$ 1 factors, we show that there are at least three pairwise non-elementarily equivalent III $$_1$$ 1 factors by showing that the class of full factors is preserved under elementary equivalence.
more »
« less
Comparing Computational Entropies Below Majority (Or: When Is the Dense Model Theorem False?)
Computational pseudorandomness studies the extent to which a random variable Z looks like the uniform distribution according to a class of tests ℱ. Computational entropy generalizes computational pseudorandomness by studying the extent which a random variable looks like a high entropy distribution. There are different formal definitions of computational entropy with different advantages for different applications. Because of this, it is of interest to understand when these definitions are equivalent. We consider three notions of computational entropy which are known to be equivalent when the test class ℱ is closed under taking majorities. This equivalence constitutes (essentially) the so-called dense model theorem of Green and Tao (and later made explicit by Tao-Zeigler, Reingold et al., and Gowers). The dense model theorem plays a key role in Green and Tao’s proof that the primes contain arbitrarily long arithmetic progressions and has since been connected to a surprisingly wide range of topics in mathematics and computer science, including cryptography, computational complexity, combinatorics and machine learning. We show that, in different situations where ℱ is not closed under majority, this equivalence fails. This in turn provides examples where the dense model theorem is false.
more »
« less
- Award ID(s):
- 1909634
- PAR ID:
- 10225152
- Editor(s):
- Lee, James R.
- Date Published:
- Journal Name:
- Innovations in Theoretical Computer Science
- Volume:
- 12
- Issue:
- 1
- Page Range / eLocation ID:
- 2:1-2:20
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: The Case of Extra TrianglesWe aim to understand the extent to which the noise distribution in a planted signal-plus-noise problem impacts its computational complexity. To that end, we consider the planted clique and planted dense subgraph problems, but in a different ambient graph. Instead of Erd\H{o}s-R\'enyi , which has independent edges, we take the ambient graph to be the \emph{random graph with triangles} (RGT) obtained by adding triangles to . We show that the RGT can be efficiently mapped to the corresponding , and moreover, that the planted clique (or dense subgraph) is approximately preserved under this mapping. This constitutes the first average-case reduction transforming dependent noise to independent noise. Together with the easier direction of mapping the ambient graph from Erd\H{o}s-R\'enyi to RGT, our results yield a strong equivalence between models. In order to prove our results, we develop a new general framework for reasoning about the validity of average-case reductions based on \emph{low sensitivity to perturbations}.more » « less
-
Cho, Sung Je (Ed.)In this study, we describe a model of student thinking around equivalence (conceptualized as any type of equivalence relation), presenting vignettes from student conceptions from various college courses ranging from developmental to linear algebra. In this model, we conceptualize student definitions along a continuous plane with two-dimensions: the extent to which definitions are extracted vs. stipulated; and the extent to which conceptions of equivalence are operational or structural. We present examples to illustrate how this model may help us to recognize ill-defined or operational thinking on the part of students even when they appear to be able to provide “standard” definitions of equivalence, as well as to highlight cases in which students are providing mathematically valid, if non-standard, definitions of equivalence. We hope that this framework will serve as a useful tool for analyzing student work and exploring instructional and curricular handling of equivalence.more » « less
-
Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: The Case of Extra TrianglesWe aim to understand the extent to which the noise distribution in a planted signal-plusnoise problem impacts its computational complexity. To that end, we consider the planted clique and planted dense subgraph problems, but in a different ambient graph. Instead of Erd˝os-R´enyi G(n, p), which has independent edges, we take the ambient graph to be the random graph with triangles (RGT) obtained by adding triangles to G(n, p). We show that the RGT can be efficiently mapped to the corresponding G(n, p), and moreover, that the planted clique (or dense subgraph) is approximately preserved under this mapping. This constitutes the first average-case reduction transforming dependent noise to independent noise. Together with the easier direction of mapping the ambient graph from Erd˝os-R´enyi to RGT, our results yield a strong equivalence between models. In order to prove our results, we develop a new general framework for reasoning about the validity of average-case reductions based on low sensitivity to perturbations.more » « less
-
Karunakaran, S. S. ; & Higgins, A. (Ed.)This paper describes a model of student thinking around equivalence (conceptualized as any type of equivalence relation), presenting vignettes from student conceptions from various college courses ranging from developmental to linear algebra, and courses in between (e.g., calculus). In this model, we conceptualize student definitions along a continuous plane with two dimensions: the extent to which definitions are extracted vs. stipulated; and the extent to which conceptions of equivalence are operational or structural. We present examples to illustrate how this model may help us to recognize ill-defined or limited thinking on the part of students even when they appear to be able to provide “standard” definitions of equivalence, as well as to highlight cases in which students are providing mathematically valid, if non-standard, definitions of equivalence. We hope that this framework will serve as a useful tool for analyzing student work, as well as exploring instructional and curricular handling of equivalence.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
