More Like this

1. Approximating Red-Blue Set Cover and Minimum Monotone Satisfying Assignment

   https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.11  

   Chlamtáč, Eden; Makarychev, Yury; Vakilian, Ali (September 2023, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023))

   Megow, Nicole; Smith, Adam (Ed.)

   We provide new approximation algorithms for the Red-Blue Set Cover and Circuit Minimum Monotone Satisfying Assignment (MMSA) problems. Our algorithm for Red-Blue Set Cover achieves Õ(m^{1/3})-approximation improving on the Õ(m^{1/2})-approximation due to Elkin and Peleg (where m is the number of sets). Our approximation algorithm for MMSA_t (for circuits of depth t) gives an Õ(N^{1-δ}) approximation for δ = 1/3 2^{3-⌈t/2⌉}, where N is the number of gates and variables. No non-trivial approximation algorithms for MMSA_t with t ≥ 4 were previously known. We complement these results with lower bounds for these problems: For Red-Blue Set Cover, we provide a nearly approximation preserving reduction from Min k-Union that gives an Ω(m^{1/4 - ε}) hardness under the Dense-vs-Random conjecture, while for MMSA we sketch a proof that an SDP relaxation strengthened by Sherali-Adams has an integrality gap of N^{1-ε} where ε → 0 as the circuit depth t → ∞. 

   more » « less
2. A CLASSIFICATION OF LAGRANGIAN PLANES IN HOLOMORPHIC SYMPLECTIC VARIETIES

   https://doi.org/10.1017/S1474748015000328  

   Bakker, Benjamin (September 2017, Journal of the Institute of Mathematics of Jussieu)

   Classically, an indecomposable class $$R$$ in the cone of effective curves on a K3 surface $$X$$ is representable by a smooth rational curve if and only if $$R^{2}=-2$$ . We prove a higher-dimensional generalization conjectured by Hassett and Tschinkel: for a holomorphic symplectic variety $$M$$ deformation equivalent to a Hilbert scheme of $$n$$ points on a K3 surface, an extremal curve class $$R\in H_{2}(M,\mathbb{Z})$$ in the Mori cone is the line in a Lagrangian $$n$$ -plane $$\mathbb{P}^{n}\subset M$$ if and only if certain intersection-theoretic criteria are met. In particular, any such class satisfies $$(R,R)=-\frac{n+3}{2}$$ , and the primitive such classes are all contained in a single monodromy orbit. 

   more » « less
3. MAXIMAL TOWERS AND ULTRAFILTER BASES IN COMPUTABILITY THEORY

   https://doi.org/10.1017/jsl.2022.60  

   LEMPP, STEFFEN; MILLER, JOSEPH S.; NIES, ANDRÉ; SOSKOVA, MARIYA I. (August 2022, The Journal of Symbolic Logic)

   Abstract The tower number $${\mathfrak t}$$ and the ultrafilter number $$\mathfrak {u}$$ are cardinal characteristics from set theory. They are based on combinatorial properties of classes of subsets of $$\omega $$ and the almost inclusion relation $$\subseteq ^*$$ between such subsets. We consider analogs of these cardinal characteristics in computability theory. We say that a sequence $$(G_n)_{n \in {\mathbb N}}$$ of computable sets is a tower if $$G_0 = {\mathbb N}$$ , $$G_{n+1} \subseteq ^* G_n$$ , and $$G_n\smallsetminus G_{n+1}$$ is infinite for each n . A tower is maximal if there is no infinite computable set contained in all $$G_n$$ . A tower $${\left \langle {G_n}\right \rangle }_{n\in \omega }$$ is an ultrafilter base if for each computable R , there is n such that $$G_n \subseteq ^* R$$ or $$G_n \subseteq ^* \overline R$$ ; this property implies maximality of the tower. A sequence $$(G_n)_{n \in {\mathbb N}}$$ of sets can be encoded as the “columns” of a set $$G\subseteq \mathbb N$$ . Our analogs of $${\mathfrak t}$$ and $${\mathfrak u}$$ are the mass problems of sets encoding maximal towers, and of sets encoding towers that are ultrafilter bases, respectively. The relative position of a cardinal characteristic broadly corresponds to the relative computational complexity of the mass problem. We use Medvedev reducibility to formalize relative computational complexity, and thus to compare such mass problems to known ones. We show that the mass problem of ultrafilter bases is equivalent to the mass problem of computing a function that dominates all computable functions, and hence, by Martin’s characterization, it captures highness. On the other hand, the mass problem for maximal towers is below the mass problem of computing a non-low set. We also show that some, but not all, noncomputable low sets compute maximal towers: Every noncomputable (low) c.e. set computes a maximal tower but no 1-generic $$\Delta ^0_2$$ -set does so. We finally consider the mass problems of maximal almost disjoint, and of maximal independent families. We show that they are Medvedev equivalent to maximal towers, and to ultrafilter bases, respectively. 

   more » « less
4. Chromatic fixed point theory and the Balmer spectrum for extraspecial 2-groups

   https://doi.org/10.1353/ajm.2024.a928325  

   Kuhn, Nicholas J; Lloyd, Christopher_J R (June 2024, American Journal of Mathematics)

   abstract: In the early 1940s, P. A. Smith showed that if a finite $$p$$-group $$G$$ acts on a finite dimensional complex $$X$$ that is mod $$p$$ acyclic, then its space of fixed points, $X^G$, will also be mod $$p$$ acyclic. In their recent study of the Balmer spectrum of equivariant stable homotopy theory, Balmer and Sanders were led to study a question that can be shown to be equivalent to the following: if a $$G$$-space $$X$$ is a equivariant homotopy retract of the $$p$$-localization of a based finite $$G$$-C.W. complex, given $H 

   more » « less
5. On the Classification of Normal Stein Spaces and Finite Ball Quotients With Bergman–Einstein Metrics

   https://doi.org/10.1093/imrn/rnab120  

   Ebenfelt, Peter; Xiao, Ming; Xu, Hang (June 2021, International Mathematics Research Notices)

   null (Ed.)

   Abstract We study the Bergman metric of a finite ball quotient $$\mathbb{B}^n/\Gamma $$, where $$n \geq 2$$ and $$\Gamma \subseteq{\operatorname{Aut}}({\mathbb{B}}^n)$$ is a finite, fixed point free, abelian group. We prove that this metric is Kähler–Einstein if and only if $$\Gamma $$ is trivial, that is, when the ball quotient $$\mathbb{B}^n/\Gamma $$ is the unit ball $${\mathbb{B}}^n$$ itself. As a consequence, we characterize the unit ball among normal Stein spaces with isolated singularities and abelian fundamental groups in terms of the existence of a Bergman–Einstein metric. 

   more » « less