More Like this

1. Reduction games, provability and compactness

   https://doi.org/10.1142/S021906132250009X  

   Dzhafarov, Damir D.; Hirschfeldt, Denis R.; Reitzes, Sarah (December 2022, Journal of Mathematical Logic)

   Hirschfeldt and Jockusch (2016) introduced a two-player game in which winning strategies for one or the other player precisely correspond to implications and non-implications between [Formula: see text] principles over [Formula: see text]-models of [Formula: see text]. They also introduced a version of this game that similarly captures provability over [Formula: see text]. We generalize and extend this game-theoretic framework to other formal systems, and establish a certain compactness result that shows that if an implication [Formula: see text] between two principles holds, then there exists a winning strategy that achieves victory in a number of moves bounded by a number independent of the specific run of the game. This compactness result generalizes an old proof-theoretic fact noted by H. Wang (1981), and has applications to the reverse mathematics of combinatorial principles. We also demonstrate how this framework leads to a new kind of analysis of the logical strength of mathematical problems that refines both that of reverse mathematics and that of computability-theoretic notions such as Weihrauch reducibility, allowing for a kind of fine-structural comparison between [Formula: see text] principles that has both computability-theoretic and proof-theoretic aspects, and can help us distinguish between these, for example by showing that a certain use of a principle in a proof is “purely proof-theoretic”, as opposed to relying on its computability-theoretic strength. We give examples of this analysis to a number of principles at the level of [Formula: see text], uncovering new differences between their logical strengths. 

   more » « less
2. Residually finite dimensional algebras and polynomial almost identities

   https://doi.org/10.1142/S0219498822500384  

   Larsen, Michael; Shalev, Aner (February 2022, Journal of Algebra and Its Applications)

   Let [Formula: see text] be a residually finite dimensional algebra (not necessarily associative) over a field [Formula: see text]. Suppose first that [Formula: see text] is algebraically closed. We show that if [Formula: see text] satisfies a homogeneous almost identity [Formula: see text], then [Formula: see text] has an ideal of finite codimension satisfying the identity [Formula: see text]. Using well known results of Zelmanov, we conclude that, if a residually finite dimensional Lie algebra [Formula: see text] over [Formula: see text] is almost [Formula: see text]-Engel, then [Formula: see text] has a nilpotent (respectively, locally nilpotent) ideal of finite codimension if char [Formula: see text] (respectively, char [Formula: see text]). Next, suppose that [Formula: see text] is finite (so [Formula: see text] is residually finite). We prove that, if [Formula: see text] satisfies a homogeneous probabilistic identity [Formula: see text], then [Formula: see text] is a coset identity of [Formula: see text]. Moreover, if [Formula: see text] is multilinear, then [Formula: see text] is an identity of some finite index ideal of [Formula: see text]. Along the way we show that if [Formula: see text] has degree [Formula: see text], and [Formula: see text] is a finite [Formula: see text]-algebra such that the probability that [Formula: see text] (where [Formula: see text] are randomly chosen) is at least [Formula: see text], then [Formula: see text] is an identity of [Formula: see text]. This solves a ring-theoretic analogue of a (still open) group-theoretic problem posed by Dixon, 

   more » « less
3. Solving Optimization Problems with Blackwell Approachability

   https://doi.org/10.1287/moor.2023.1376  

   Grand-Clément, Julien; Kroer, Christian (January 2023, Mathematics of Operations Research)

   In this paper, we propose a new algorithm for solving convex-concave saddle-point problems using regret minimization in the repeated game framework. To do so, we introduce the Conic Blackwell Algorithm + ([Formula: see text]), a new parameter- and scale-free regret minimizer for general convex compact sets. [Formula: see text] is based on Blackwell approachability and attains [Formula: see text] regret. We show how to efficiently instantiate [Formula: see text] for many decision sets of interest, including the simplex, [Formula: see text] norm balls, and ellipsoidal confidence regions in the simplex. Based on [Formula: see text], we introduce [Formula: see text], a new parameter-free algorithm for solving convex-concave saddle-point problems achieving a [Formula: see text] ergodic convergence rate. In our simulations, we demonstrate the wide applicability of [Formula: see text] on several standard saddle-point problems from the optimization and operations research literature, including matrix games, extensive-form games, distributionally robust logistic regression, and Markov decision processes. In each setting, [Formula: see text] achieves state-of-the-art numerical performance and outperforms classical methods, without the need for any choice of step sizes or other algorithmic parameters. Funding: J. Grand-Clément is supported by the Agence Nationale de la Recherche [Grant 11-LABX-0047] and by Hi! Paris. C. Kroer is supported by the Office of Naval Research [Grant N00014-22-1-2530] and by the National Science Foundation [Grant IIS-2147361]. 

   more » « less
4. Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design

   https://doi.org/10.1287/moor.2021.1129  

   Nikolov, Aleksandar; Singh, Mohit; Tantipongpipat, Uthaipon (May 2022, Mathematics of Operations Research)

   We study optimal design problems in which the goal is to choose a set of linear measurements to obtain the most accurate estimate of an unknown vector. We study the [Formula: see text]-optimal design variant where the objective is to minimize the average variance of the error in the maximum likelihood estimate of the vector being measured. We introduce the proportional volume sampling algorithm to obtain nearly optimal bounds in the asymptotic regime when the number [Formula: see text] of measurements made is significantly larger than the dimension [Formula: see text] and obtain the first approximation algorithms whose approximation factor does not degrade with the number of possible measurements when [Formula: see text] is small. The algorithm also gives approximation guarantees for other optimal design objectives such as [Formula: see text]-optimality and the generalized ratio objective, matching or improving the previously best-known results. We further show that bounds similar to ours cannot be obtained for [Formula: see text]-optimal design and that [Formula: see text]-optimal design is NP-hard to approximate within a fixed constant when [Formula: see text]. 

   more » « less
5. Bartnik mass via vacuum extensions

   https://doi.org/10.1142/S0129167X19400068  

   Miao, Pengzi; Xie, Naqing (December 2019, International Journal of Mathematics)

   We construct asymptotically flat, scalar flat extensions of Bartnik data [Formula: see text], where [Formula: see text] is a metric of positive Gauss curvature on a two-sphere [Formula: see text], and [Formula: see text] is a function that is either positive or identically zero on [Formula: see text], such that the mass of the extension can be made arbitrarily close to the half area radius of [Formula: see text]. In the case of [Formula: see text], the result gives an analog of a theorem of Mantoulidis and Schoen [On the Bartnik mass of apparent horizons, Class. Quantum Grav. 32(20) (2015) 205002, 16 pp.], but with extensions that have vanishing scalar curvature. In the context of initial data sets in general relativity, the result produces asymptotically flat, time-symmetric, vacuum initial data with an apparent horizon [Formula: see text], for any metric [Formula: see text] with positive Gauss curvature, such that the mass of the initial data is arbitrarily close to the optimal value in the Riemannian Penrose inequality. The method we use is the Shi–Tam type metric construction from [Positive mass theorem and the boundary behaviors of compact manifolds with nonnegative scalar curvature, J. Differential Geom. 62(1) (2002) 79–125] and a refined Shi–Tam monotonicity, found by the first named author in [On a localized Riemannian Penrose inequality, Commun. Math. Phys. 292(1) (2009) 271–284]. 

   more » « less