• Open Access close
• Preprint close
• Article close
• IL close
• arXiv.org e-Print Archive close

This paper is part of an ongoing endeavor to bring the theory of fair division closer to practice by handling requirements from real-life applications. We focus on two requirements originating from the division of land estates: (1) each agent should receive a plot of a usable geometric shape, and (2) plots of different agents must be physically separated. With these requirements, the classic fairness notion of \emph{proportionality} is impractical, since it may be impossible to attain any multiplicative approximation of it. In contrast, the \emph{ordinal maximin share approximation}, introduced by Budish in 2011, provides meaningful fairness guarantees. We prove upper and lower bounds on achievable maximin share guarantees when the usable shapes are squares, fat rectangles, or arbitrary axis-aligned rectangles, and explore the algorithmic and query complexity of finding fair partitions in this setting. Our work makes use of tools and concepts from computational geometry such as independent sets of rectangles and guillotine partitions. Appears in the 30th International Joint Conference on Artificial Intelligence (IJCAI), 2021

Semi-online models where decisions may be revoked in a limited way have been studied extensively in the last years. This is motivated by the fact that the pure online model is often too restrictive to model real-world applications, where some changes might be allowed. A well-studied measure of the amount of decisions that can be revoked is the migration factor $\beta$: When an object $o$ of size $s(o)$ arrives, the decisions for objects of total size at most $\beta\cdot s(o)$ may be revoked. Usually $\beta$ should be a constant. This means that a small object only leads to small changes. This measure has been successfully investigated for different, classic problems such as bin packing or makespan minimization. The dual of makespan minimization - the Santa Claus or machine covering problem - has also been studied, whereas the dual of bin packing - the bin covering problem - has not been looked at from such a perspective. In this work, we extensively study the bin covering problem with migration in different scenarios. We develop algorithms both for the static case - where only insertions are allowed - and for the dynamic case, where items may also depart. We also develop lower bounds for these scenarios both for amortized migration and for worst-case migration showing that our algorithms have nearly optimal migration factor and asymptotic competitive ratio (up to an arbitrary small $\eps$). We therefore resolve the competitiveness of the bin covering problem with migration.

Real-life parallel machine scheduling problems can be characterized by: (i) limited information about the exact task duration at scheduling time, and (ii) an opportunity to reschedule the remaining tasks each time a task processing is completed and a machine becomes idle. Robust optimization is the natural methodology to cope with the first characteristic of duration uncertainty, yet the existing literature on robust scheduling does not explicitly consider the second characteristic - the possibility to adjust decisions as more information about the tasks' duration becomes available, despite that re-optimizing the schedule every time new information emerges is standard practice. In this paper, we develop a scheduling approach that takes into account, at the beginning of the planning horizon, the possibility that scheduling decisions can be adjusted. We demonstrate that the suggested approach can lead to better here-and-now decisions and better makespan guarantees. To that end, we develop the first mixed integer linear programming model for adjustable robust scheduling, and a scalable two-stage approximation heuristic, where we minimize the worst-case makespan. Using this model, we show via a numerical study that adjustable scheduling leads to solutions with better and more stable makespan realizations compared to static approaches.

In a paper from 1997, Shelah asked whether $Pr_1(\lambda^+,\lambda^+,\lambda^+,\lambda)$ holds for every inaccessible cardinal $\lambda$. Here, we prove that an affirmative answer follows from $\square(\lambda^+)$. Furthermore, we establish that for every pair $\chi<\kappa$ of regular uncountable cardinals, $\square(\kappa)$ implies $Pr_1(\kappa,\kappa,\kappa,\chi)$.

We prove a quantitative variant of a disjointness theorem of nilflows from horospherical flows following a technique of Venkatesh, combined with the structural theorems for nilflows by Green, Tao and Ziegler.

Projection-free optimization via different variants of the Frank-Wolfe (FW) method has become one of the cornerstones in large scale optimization for machine learning and computational statistics. Numerous applications within these fields involve the minimization of functions with self-concordance like properties. Such generalized self-concordant (GSC) functions do not necessarily feature a Lipschitz continuous gradient, nor are they strongly convex. Indeed, in a number of applications, e.g. inverse covariance estimation or distance-weighted discrimination problems in support vector machines, the loss is given by a GSC function having unbounded curvature, implying absence of theoretical guarantees for the existing FW methods. This paper closes this apparent gap in the literature by developing provably convergent FW algorithms with standard O(1/k) convergence rate guarantees. If the problem formulation allows the efficient construction of a local linear minimization oracle, we develop a FW method with linear convergence rate. Comment: This is an extended version of the conference paper arXiv:2002.04320

SN~2018aoz is a Type Ia SN with a $B$-band plateau and excess emission in the infant-phase light curves $\lesssim$ 1 day after first light, evidencing an over-density of surface iron-peak elements as shown in our previous study. Here, we advance the constraints on the nature and origin of SN~2018aoz based on its evolution until the nebular phase. Near-peak spectroscopic features show the SN is intermediate between two subtypes of normal Type Ia: Core-Normal and Broad-Line. The excess emission could have contributions from the radioactive decay of surface iron-peak elements as well as ejecta interaction with either the binary companion or a small torus of circumstellar material. Nebular-phase limits on H$\alpha$ and He~I favour a white dwarf companion, consistent with the small companion size constrained by the low early SN luminosity, while the absence of [O~I] and He~I disfavours a violent merger of the progenitor. Of the two main explosion mechanisms proposed to explain the distribution of surface iron-peak elements in SN~2018aoz, the asymmetric Chandrasekhar-mass explosion is less consistent with the progenitor constraints and the observed blueshifts of nebular-phase [Fe~II] and [Ni~II]. The helium-shell double-detonation explosion is compatible with the observed lack of C spectral features, but current 1-D models are incompatible with the infant-phase excess emission, $B_{\rm max}-V_{\rm max}$ color, and absence of nebular-phase [Ca~II]. Although the explosion processes of SN~2018aoz still need to be more precisely understood, the same processes could produce a significant fraction of Type Ia SNe that appear normal after $\sim$ 1 day. Comment: Submitted for publication in ApJ. 35 pages, 16 figures, 7 tables

High dimensional expanders is a vibrant emerging field of study. Nevertheless, the only known construction of bounded degree high dimensional expanders is based on Ramanujan complexes, whereas one dimensional bounded degree expanders are abundant. In this work, we construct new families of bounded degree high dimensional expanders obeying the local spectral expansion property. This property has a number of important consequences, including geometric overlapping, fast mixing of high dimensional random walks, agreement testing and agreement expansion. Our construction also yields new families of expander graphs which are close to the Ramanujan bound, i.e., their spectral gap is close to optimal. The construction is quite elementary and it is presented in a self contained manner; This is in contrary to the highly involved previously known construction of the Ramanujan complexes. The construction is also very symmetric (such symmetry properties are not known for Ramanujan complexes) ; The symmetry of the construction could be used, for example, in order to obtain good symmetric LDPC codes that were previously based on Ramanujan graphs. The main tool that we use for is the theory of coset geometries. Coset geometries arose as a tool for studying finite simple groups. Here, we show that coset geometries arise in a very natural manner for groups of elementary matrices over any finitely generated algebra over a commutative unital ring. In other words, we show that such groups act simply transitively on the top dimensional face of a pure, partite, clique complex. Comment: 48 pages. The focus of this version slightly shifted from HD expanders to studying the general theory of simplicial complexes arising from elementary matrix groups (and HD expanders as an application of this theory). The construction is now put into the context of coset geometries which shortens the paper. Several typos and minor errors where corrected

Coleman-de Luccia transitions are spontaneous processes of nucleation of bubbles within metastable gravitational vacua including in their interior a true stable vacuum. From the perspective of lower-dimensional gauged supergravities obtained by truncating Type II and M-theory, these instantonic processes are represented by smooth domain walls featured by de Sitter foliations. These geometries must connect two different AdS vacua in such a way that the wall is defined by an interior and an exterior. We propose a first-order formulation for such radial flows and present two fully backreacted examples of gravitational instantons obtained through this technique, beyond the thin-wall approximation. In the first we consider minimal 7d supergravity describing the truncation of M-theory over a squashed 4-sphere and admitting two AdS$_7$ vacua, one supersymmetric and the other not. Secondly we apply the same strategy to 6d Romans supergravity obtained with consistent truncation of massive IIA supergravity. Also in this case we derive a dS domain wall interpolating between the Brandhuber-Oz vacuum and the non-supersymmetric AdS$_6$ vacuum of the theory. Comment: 29 pages, 6 figures, 1 appendix. v2: Added references

Bohmian mechanics was designed to give rise to predictions identical to those derived by standard quantum mechanics, while invoking a specific interpretation of it - one which allows the classical notion of a particle to be maintained alongside a guiding wave. For this, the Bohmian model makes use of a unique quantum potential which governs the trajectory of the particle. In this work we show that this interpretation of quantum theory naturally leads to the derivation of interesting new phenomena. Specifically, we demonstrate how the fundamental Casimir-Polder force, by which atoms are attracted to a surface, may be temporarily suppressed by utilizing a specially designed quantum potential. We show that when harnessing the quantum potential via a suitable atomic wavepacket engineering, the absorption by the surface can be dramatically reduced. This is proven both analytically and numerically. Finally, an experimental scheme is proposed for achieving the required shape for the atomic wavepacket. All these may enable new insights into Bohmian mechanics as well as new applications to metrology and sensing. 7 pages, 5 figures, comments are welcome