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. Scheme-theoretic coisotropic reduction

   https://doi.org/10.1093/qmath/haag005  

   Crooks, Peter; Mayrand, Maxence (February 2026, The Quarterly Journal of Mathematics)

   ABSTRACT We develop an affine scheme-theoretic version of Hamiltonian reduction by symplectic groupoids. It works over $$\mathbb {k}=\mathbb {R}$$ or $$\mathbb {k}=\mathbb {C}$$, and is formulated for an affine symplectic groupoid $$\mathcal {G}\,\,\substack{\longrightarrow \\ \longrightarrow }\,\,X$$, an affine Hamiltonian $$\mathcal {G}$$-scheme $$\mu :M\longrightarrow X$$, a coisotropic subvariety $$S\subseteq X$$, and a stabilizer subgroupoid $$\mathcal {H}\,\,\substack{\longrightarrow \\\longrightarrow }\,\,S$$. Our first main result is that the Poisson bracket on $$\mathbb {k}[M]$$ induces a Poisson bracket on the subquotient $$\mathbb {k}[\mu ^{-1}(S)]^{\mathcal {H}}$$. The Poisson scheme $$M\mathbin {//}_{{S,\mathcal {H}}}\mathcal {G}:= \mathrm{Spec}(\mathbb {k}[\mu ^{-1}(S)]^{\mathcal {H}})$$ is then declared to be a Hamiltonian reduction of M. Other main results include sufficient conditions for $$M\mathbin {//}_{{S,\mathcal {H}}}\mathcal {G}$$ to inherit a residual Hamiltonian scheme structure. Our main results are best viewed as affine scheme-theoretic counterparts to [6], where we simultaneously generalize several Hamiltonian reduction processes. In this way, the present work yields scheme-theoretic analogues of Marsden–Ratiu reduction [19], Mikami–Weinstein reduction [20], Śniatycki–Weinstein reduction [23], and symplectic reduction along general coisotropic submanifolds [6]. The initial impetus for this work was its utility in formulating and proving generalizations of the Moore–Tachikawa conjecture. 

   more » « less
3. Sparse representation of vectors in lattices and semigroups

   https://doi.org/10.1007/s10107-021-01657-8  

   Aliev, Iskander; Averkov, Gennadiy; De Loera, Jesús A.; Oertel, Timm (June 2021, Mathematical Programming)

   null (Ed.)

   Abstract We study the sparsity of the solutions to systems of linear Diophantine equations with and without non-negativity constraints. The sparsity of a solution vector is the number of its nonzero entries, which is referred to as the $$\ell _0$$ ℓ 0 -norm of the vector. Our main results are new improved bounds on the minimal $$\ell _0$$ ℓ 0 -norm of solutions to systems $$A\varvec{x}=\varvec{b}$$ A x = b , where $$A\in \mathbb {Z}^{m\times n}$$ A ∈ Z m × n , $${\varvec{b}}\in \mathbb {Z}^m$$ b ∈ Z m and $$\varvec{x}$$ x is either a general integer vector (lattice case) or a non-negative integer vector (semigroup case). In certain cases, we give polynomial time algorithms for computing solutions with $$\ell _0$$ ℓ 0 -norm satisfying the obtained bounds. We show that our bounds are tight. Our bounds can be seen as functions naturally generalizing the rank of a matrix over $$\mathbb {R}$$ R , to other subdomains such as $$\mathbb {Z}$$ Z . We show that these new rank-like functions are all NP-hard to compute in general, but polynomial-time computable for fixed number of variables. 

   more » « less
4. Non-spherical sets versus lines in Euclidean Ramsey theory

   https://doi.org/10.4153/S0008439525101082  

   Conlon, David; Führer, Jakob (March 2026, Canadian Mathematical Bulletin)

   Abstract We show that for every non-spherical setXin$$\mathbb {E}^d$$, there exists a natural numbermand a red/blue-coloring of$$\mathbb {E}^n$$for everynsuch that there is no red copy ofXand no blue progression of lengthmwith each consecutive point at distance$$1$$. This verifies a conjecture of Wu and the first author. 

   more » « less
5. 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