For a real matrix \(\textbf A \in \mathbb{R}^{d \times n}\) with non-collinear columns, we show that \(n \le O(d^{4} \kappa_\textbf A)\) where \(\kappa_\textbf A\) is the circuit imbalance measure of \(\textbf A\). The circuit imbalance measure \(\kappa\) is a real analogue of \(\Delta\)-modularity for integer matrices, satisfying \(\kappa_\textbf A \le \Delta_\textbf A\) for integer \(\textbf A\). The circuit imbalance measure has numerous applications in the context of linear programming (see Ekkbatani, Natura and Végh (2022) for a survey). Our result generalizes the \(O(d^{4} \Delta_\textbf A)\) bound of Averkov and Schymura (2023) for integer matrices and provides the first polynomial bound holding for all parameter ranges on real matrices.

We consider the problem of finding an independent set of maximum weight simultaneously contained in k matroids over a common ground set. This k-matroid intersection problem appears naturally in many contexts, for example in generalizing graph and hypergraph matching problems. In this paper, we provide a (k+1)/(2 ln2)-approximation algorithm for the weighted k-matroid intersection problem. This is the first improvement over the longstanding (k−1)-guarantee of Lee, Sviridenko and Vondrák (2009). Along the way, we also give the first improvement over greedy for the more general weighted matroid k-parity problem. Our key innovation lies in a randomized reduction in which we solve almost unweighted instances iteratively. This perspective allows us to use insights from the unweighted problem for which Lee, Sviridenko, and Vondrák have designed a k/2-approximation algorithm. We analyze this procedure by constructing refined matroid exchanges and leveraging randomness to avoid bad local minima.

This paper introduces a model for opinion dynamics, where at each time step, randomly selected agents see their opinions - modeled as scalars in [0,1] - evolve depending on a local interaction function. In the classical Bounded Confidence Model, agents opinions get attracted when they are close enough. The proposed model extends this by adding a repulsion component, which models the effect of opinions getting further pushed away when dissimilar enough. With this repulsion component added, and under a repulsion-attraction cleavage assumption, it is shown that a new stable configuration emerges beyond the classical consensus configuration, namely the polarization configuration. More specifically, it is shown that total consensus and total polarization are the only two possible limiting configurations. The paper further provides an analysis of the infinite population regime in dimension 1 and higher, with a phase transition phenomenon conjectured and backed heuristically.