More Like this

1. Sealing from iterability

   Sargsyan, Grigor; Trang, Nam (January 2021, Transactions of the American Mathematical Society)

   null (Ed.)

   We show that if V has a proper class ofWoodin cardinals, a strong cardinal, and a generically universally Baire iteration strategy (as defined in the paper) then Sealing holds after collapsing the successor of the least strong cardinal to be countable. This result is complementary to other work by the authors where it is shown that Sealing holds in a generic extension of a certain minimal universe. The current theorem is more general in that no minimality assumption is needed. A corollary of the main theorem is that Sealing is consistent relative to the existence of a Woodin cardinal which is a limit of Woodin cardinals. This improves significantly on the first consistency of Sealing obtained by W.H. Woodin. The Largest Suslin Axiom (LSA) is a determinacy axiom isolated byWoodin. It asserts that the largest Suslin cardinal is inaccessible for ordinal definable bijections. Let LSA-over-uB be the statement that in all (set) generic extensions there is a model of LSA whose Suslin, co-Suslin sets are the universally Baire sets. The other main result of the paper shows that assuming V has a proper class of inaccessible cardinals which are limit of Woodin cardinals, a strong cardinal, and a generically universally Baire iteration strategy, in the universe V [g], where g is V -generic for the collapse of the successor of the least strong cardinal to be countable, the theory LSA-over-UB fails; this implies that LSA-over-UB is not equivalent to Sealing (over the base theory of V [g]). This is interesting and somewhat unexpected, in light of other work by the authors. Compare this result with Steel’s well-known theorem that “AD in L(R) holds in all generic extensions” is equivalent to “the theory of L(R) is sealed” in the presence of a proper class of measurable cardinals. 

   more » « less
2. SEALING OF THE UNIVERSALLY BAIRE SETS

   https://doi.org/10.1017/bsl.2021.29  

   Sargsyan, Grigor; Trang, Nam (October 2021, The bulletin of symbolic logic)

   A set of reals is universally Baire if all of its continuous preimages in topological spaces have the Baire property. 𝖲𝖾𝖺𝗅𝗂𝗇𝗀 is a type of generic absoluteness condition introduced by Woodin that asserts in strong terms that the theory of the universally Baire sets cannot be changed by set forcings. The 𝖫𝖺𝗋𝗀𝖾𝗌𝗍 𝖲𝗎𝗌𝗅𝗂𝗇 𝖠𝗑𝗂𝗈𝗆 ( 𝖫𝖲𝖠 ) is a determinacy axiom isolated by Woodin. It asserts that the largest Suslin cardinal is inaccessible for ordinal definable surjections. Let 𝖫𝖲𝖠 - 𝗈𝗏𝖾𝗋 - 𝗎𝖡 be the statement that in all (set) generic extensions there is a model of 𝖫𝖲𝖠 whose Suslin, co-Suslin sets are the universally Baire sets. We outline the proof that over some mild large cardinal theory, 𝖲𝖾𝖺𝗅𝗂𝗇𝗀 is equiconsistent with 𝖫𝖲𝖠 - 𝗈𝗏𝖾𝗋 - 𝗎𝖡 . In fact, we isolate an exact theory (in the hierarchy of strategy mice) that is equiconsistent with both (see Definition 3.1). As a consequence, we obtain that 𝖲𝖾𝖺𝗅𝗂𝗇𝗀 is weaker than the theory “ 𝖹𝖥𝖢 + there is a Woodin cardinal which is a limit of Woodin cardinals.” This significantly improves upon the earlier consistency proof of 𝖲𝖾𝖺𝗅𝗂𝗇𝗀 by Woodin. A variation of 𝖲𝖾𝖺𝗅𝗂𝗇𝗀 , called 𝖳𝗈𝗐𝖾𝗋 𝖲𝖾𝖺𝗅𝗂𝗇𝗀 , is also shown to be equiconsistent with 𝖲𝖾𝖺𝗅𝗂𝗇𝗀 over the same large cardinal theory. We also outline the proof that if V has a proper class of Woodin cardinals, a strong cardinal, and a generically universally Baire iteration strategy, then 𝖲𝖾𝖺𝗅𝗂𝗇𝗀 holds after collapsing the successor of the least strong cardinal to be countable. This result is complementary to the aforementioned equiconsistency result, where it is shown that 𝖲𝖾𝖺𝗅𝗂𝗇𝗀 holds in a generic extension of a certain minimal universe. This theorem is more general in that no minimal assumption is needed. A corollary of this is that 𝖫𝖲𝖠 - 𝗈𝗏𝖾𝗋 - 𝗎𝖡 is not equivalent to 𝖲𝖾𝖺𝗅𝗂𝗇𝗀 . 

   more » « less
3. On the Computational Complexity of Non-Dictatorial Aggregation

   https://doi.org/10.1613/jair.1.12476  

   Livieratos, John; Kolaitis, Phokion G.; Kirousis, Lefteris (September 2021, Journal of Artificial Intelligence Research)

   We investigate when non-dictatorial aggregation is possible from an algorithmic perspective, where non-dictatorial aggregation means that the votes cast by the members of a society can be aggregated in such a way that there is no single member of the society that always dictates the collective outcome. We consider the setting in which the members of a society take a position on a fixed collection of issues, where for each issue several different alternatives are possible, but the combination of choices must belong to a given set X of allowable voting patterns. Such a set X is called a possibility domain if there is an aggregator that is non-dictatorial, operates separately on each issue, and returns values among those cast by the society on each issue. We design a polynomial-time algorithm that decides, given a set X of voting patterns, whether or not X is a possibility domain. Furthermore, if X is a possibility domain, then the algorithm constructs in polynomial time a non-dictatorial aggregator for X. Furthermore, we show that the question of whether a Boolean domain X is a possibility domain is in NLOGSPACE. We also design a polynomial-time algorithm that decides whether X is a uniform possibility domain, that is, whether X admits an aggregator that is non-dictatorial even when restricted to any two positions for each issue. As in the case of possibility domains, the algorithm also constructs in polynomial time a uniform non-dictatorial aggregator, if one exists. Then, we turn our attention to the case where X is given implicitly, either as the set of assignments satisfying a propositional formula, or as a set of consistent evaluations of a sequence of propositional formulas. In both cases, we provide bounds to the complexity of deciding if X is a (uniform) possibility domain. Finally, we extend our results to four types of aggregators that have appeared in the literature: generalized dictatorships, whose outcome is always an element of their input, anonymous aggregators, whose outcome is not affected by permutations of their input, monotone, whose outcome does not change if more individuals agree with it and systematic, which aggregate every issue in the same way. 

   more » « less
4. Clustering with Neighborhoods is Hard for Squares

   Klimenko, Georgiy; Raichel, Benjamin (July 2023, Proceedings of the 35th Canadian Conference on Computational Geometry)

   Pankratov, Denis (Ed.)

   In the clustering with neighborhoods problem one is given a set S of disjoint convex objects in the plane and an integer parameter k ≥ 0, and the goal is to select a set C of k center points in the plane so as to minimize the maximum distance of an object in S to its nearest center in C. Previously [HKR21] showed that this problem cannot be approximated within any factor when S is a set of disjoint line segments, however, when S is a set of disjoint disks there is a roughly 8.46 approximation algorithm and a roughly 6.99 approximation lower bound. In this paper we investigate this significant discrepancy in hardness between these shapes. Specifically, we show that when S is a set of axis aligned squares of the same size, the problem again is hard to approximate within any factor. This surprising fact shows that the discrepancy is not due to the fatness of the object class, as one might otherwise naturally suspect. 

   more » « less
5. Minimum norm interpolation in the ℓ1(ℕ) space

   https://doi.org/10.1142/S0219530520400059  

   Cheng, Raymond; Xu, Yuesheng (January 2021, Analysis and Applications)

   null (Ed.)

   We consider the minimum norm interpolation problem in the [Formula: see text] space, aiming at constructing a sparse interpolation solution. The original problem is reformulated in the pre-dual space, thereby inducing a norm in a related finite-dimensional Euclidean space. The dual problem is then transformed into a linear programming problem, which can be solved by existing methods. With that done, the original interpolation problem is reduced by solving an elementary finite-dimensional linear algebra equation. A specific example is presented to illustrate the proposed method, in which a sparse solution in the [Formula: see text] space is compared to the dense solution in the [Formula: see text] space. This example shows that a solution of the minimum norm interpolation problem in the [Formula: see text] space is indeed sparse, while that of the minimum norm interpolation problem in the [Formula: see text] space is not. 

   more » « less