More Like this

1. Classification of Constructible Cosheaves

   Curry, J; Patel, A (January 2020, Theory and applications of categories)

   null (Ed.)

   In this paper we prove an equivalence theorem originally observed by Robert MacPherson. On one side of the equivalence is the category of cosheaves that are constructible with respect to a locally cone-like stratification. Our constructibility condition is new and only requires that certain inclusions of open sets are sent to isomorphisms. On the other side of the equivalence is the category of functors from the entrance path category, which has points for objects and certain homotopy classes of paths for morphisms. When our constructible cosheaves are valued in Set we prove an additional equivalence with the category of stratified coverings. 

   more » « less
2. The Borel complexity of the space of left‐orderings, low‐dimensional topology, and dynamics

   https://doi.org/10.1112/jlms.70024  

   Calderoni, Filippo; Clay, Adam (November 2024, 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
3. SPES: A Symbolic Approach to Proving Query Equivalence Under Bag Semantics

   Q. Zhou, J. Arulraj (July 2022, Proceedings International Conference on Data Engineering)

   In database-as-a-service platforms, automated ver-ification of query equivalence helps eliminate redundant computation in the form of overlapping sub-queries. Researchers have proposed two pragmatic techniques to tackle this problem. The first approach consists of reducing the queries to algebraic expressions and proving their equivalence using an algebraic theory. The limitations of this technique are threefold. It cannot prove the equivalence of queries with significant differences in the attributes of their relational operators (e.g., predicates in the filter operator). It does not support certain widely-used SQL features (e.g., NULL values). Its verification procedure is computationally intensive. The second approach transforms this problem to a constraint satisfaction problem and leverages a general-purpose solver to determine query equivalence. This technique consists of deriving the symbolic representation of the queries and proving their equivalence by determining the query containment relationship between the symbolic expressions. While the latter approach addresses all the limitations of the former technique, it only proves the equivalence of queries under set semantics (i.e., output tables must not contain duplicate tuples). However, in practice, database applications use bag semantics (i.e., output tables may contain duplicate tuples) In this paper, we introduce a novel symbolic approach for proving query equivalence under bag semantics. We transform the problem of proving query equivalence under bag semantics to that of proving the existence of a bijective, identity map between tuples returned by the queries on all valid inputs. We classify SQL queries into four categories, and propose a set of novel category-specific verification algorithms. We implement this symbolic approach in SPES and demonstrate that it proves the equivalence of a larger set of query pairs (95/232) under bag semantics compared to the SOTA tools based on algebraic (30/232) and symbolic approaches (67/232) under set and bag semantics, respectively. Furthermore, SPES is 3X faster than the symbolic tool that proves equivalence under set semantics. 

   more » « less
4. Extending to a model structure is not a first-order property

   Droz, Jean-Marie; Zakharevich, Inna (January 2021, New York journal of mathematics)

   Let C be a finitely bicomplete category and W a subcategory. We prove that the existence of a model structure on C with W as the subcategory of weak equivalence is not first order expressible. Along the way we characterize all model structures where C is a partial order and show that these are determined by the homotopy categories. 

   more » « less
5. Asymptotics of the Sketched Pseudoinverse

   https://doi.org/10.1137/22M1530264  

   LeJeune, Daniel; Patil, Pratik; Javadi, Hamid; Baraniuk, Richard G; Tibshirani, Ryan J (March 2024, SIAM Journal on Mathematics of Data Science)

   We take a random matrix theory approach to random sketching and show an asymptotic first-order equivalence of the regularized sketched pseudoinverse of a positive semidefinite matrix to a certain evaluation of the resolvent of the same matrix. We focus on real-valued regularization and extend previous results on an asymptotic equivalence of random matrices to the real setting, providing a precise characterization of the equivalence even under negative regularization, including a precise characterization of the smallest nonzero eigenvalue of the sketched matrix. We then further characterize the second-order equivalence of the sketched pseudoinverse. We also apply our results to the analysis of the sketch-and-project method and to sketched ridge regression. Last, we prove that these results generalize to asymptotically free sketching matrices, obtaining the resulting equivalence for orthogonal sketching matrices and comparing our results to several common sketches used in practice. 

   more » « less