skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Approximate homomorphisms and sofic approximations of orbit equivalence relations
Abstract We show that for every countable group, any sequence of approximate homomorphisms with values in permutations can be realized as the restriction of a sofic approximation of an orbit equivalence relation. Moreover, this orbit equivalence relation is uniquely determined by the invariant random subgroup of the approximate homomorphisms. We record applications of this result to recover various known stability and conjugacy characterizations for almost homomorphisms of amenable groups.  more » « less
Award ID(s):
2350049 2144739
PAR ID:
10595207
Author(s) / Creator(s):
;
Publisher / Repository:
Cambridge University Press
Date Published:
Journal Name:
Ergodic Theory and Dynamical Systems
Volume:
44
Issue:
12
ISSN:
0143-3857
Page Range / eLocation ID:
3455 to 3480
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; (, Ergodic Theory and Dynamical Systems)
    Abstract It is a long-standing open question whether every Polish group that is not locally compact admits a Borel action on a standard Borel space whose associated orbit equivalence relation is not essentially countable. We answer this question positively for the class of all Polish groups that embed in the isometry group of a locally compact metric space. This class contains all non-archimedean Polish groups, for which we provide an alternative proof based on a new criterion for non-essential countability. Finally, we provide the following variant of a theorem of Solecki: every infinite-dimensional Banach space has a continuous action whose orbit equivalence relation is Borel but not essentially countable. 
    more » « less
  2. ; ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Cormode, Graham; Shekelyan, Michael (Ed.)
    A query algorithm based on homomorphism counts is a procedure for determining whether a given instance satisfies a property by counting homomorphisms between the given instance and finitely many predetermined instances. In a left query algorithm, we count homomorphisms from the predetermined instances to the given instance, while in a right query algorithm we count homomorphisms from the given instance to the predetermined instances. Homomorphisms are usually counted over the semiring ℕ of non-negative integers; it is also meaningful, however, to count homomorphisms over the Boolean semiring 𝔹, in which case the homomorphism count indicates whether or not a homomorphism exists. We first characterize the properties that admit a left query algorithm over 𝔹 by showing that these are precisely the properties that are both first-order definable and closed under homomorphic equivalence. After this, we turn attention to a comparison between left query algorithms over 𝔹 and left query algorithms over ℕ. In general, there are properties that admit a left query algorithm over ℕ but not over 𝔹. The main result of this paper asserts that if a property is closed under homomorphic equivalence, then that property admits a left query algorithm over 𝔹 if and only if it admits a left query algorithm over ℕ. In other words and rather surprisingly, homomorphism counts over ℕ do not help as regards properties that are closed under homomorphic equivalence. Finally, we characterize the properties that admit both a left query algorithm over 𝔹 and a right query algorithm over 𝔹. 
    more » « less
  3. ; ; ; (, Proceedings of the American Mathematical Society)
    We identify natural conditions for a countable group acting on a countable tree which imply that the orbit equivalence relation of the induced action on the Gromov boundary is Borel hyperfinite. Examples of this condition include acylindrical actions. We also identify a natural weakening of the aforementioned conditions that implies measure hyperfiniteness of the boundary action. We then document examples of group actions on trees whose boundary action is not hyperfinite. 
    more » « less
  4. ; (, Journal of the London Mathematical Society)
    Abstract We develop new tools to analyze the complexity of the conjugacy equivalence relation , whenever is a left‐orderable group. Our methods are used to demonstrate nonsmoothness of for certain groups of dynamical origin, such as certain amalgams constructed from Thompson's group . We also initiate a systematic analysis of , where is a 3‐manifold. We prove that if is not prime, then is a universal countable Borel equivalence relation, and show that in certain cases the complexity of is bounded below by the complexity of the conjugacy equivalence relation arising from the fundamental group of each of the JSJ pieces of . We also prove that if is the complement of a nontrivial knot in then is not smooth, and show how determining smoothness of for all knot manifolds is related to the L‐space conjecture. 
    more » « less
  5. ; ; ; ; ; (, Proceedings of the ACM on Programming Languages)
    Properties such as provable security and correctness for randomized programs are naturally expressed relationally as approximate equivalences. As a result, a number of relational program logics have been developed to reason about such approximate equivalences of probabilistic programs. However, existing approximate relational logics are mostly restricted to first-order programs without general state. In this paper we develop Approxis, a higher-order approximate relational separation logic for reasoning about approximate equivalence of programs written in an expressive ML-like language with discrete probabilistic sampling, higher-order functions, and higher-order state. The Approxis logic recasts the concept of error credits in the relational setting to reason about relational approximation, which allows for expressive notions of modularity and composition, a range of new approximate relational rules, and an internalization of a standard limiting argument for showing exact probabilistic equivalences by approximation. We also use Approxis to develop a logical relation model that quantifies over error credits, which can be used to prove exact contextual equivalence. We demonstrate the flexibility of our approach on a range of examples, including the PRP/PRF switching lemma, IND$-CPA security of an encryption scheme, and a collection of rejection samplers. All of the results have been mechanized in the Coq proof assistant and the Iris separation logic framework. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email