Search

We study finite groups $G$ having a normal subgroup $H$ and $D \subset G \setminus H, D \cap D^{-1}=\emptyset,$ such that the multiset $\{ xy^{-1}:x,y \in D\}$ has every non-identity element occur the same number of times (such a $D$ is called a {\it DRAD difference set}). We show that there are no such groups of order $4p^2$, where $p$ is an odd prime., Comment: 15 pages

Given a set of pairwise disjoint polygonal obstacles in the plane, finding an obstacle-avoiding Euclidean shortest path between two points is a classical problem in computational geometry and has been studied extensively. Previously, Hershberger and Suri [SIAM J. Comput. 1999] gave an algorithm of $O(n\log n)$ time and $O(n\log n)$ space, where $n$ is the total number of vertices of all obstacles. Recently, by modifying Hershberger and Suri's algorithm, Wang [SODA 2021] reduced the space to $O(n)$ while the runtime of the algorithm is still $O(n\log n)$. In this paper, we present a new algorithm of $O(n+h\log h)$ time and $O(n)$ space, provided that a triangulation of the free space is given, where $h$ is the number of obstacles. The algorithm, which improves the previous work when $h=o(n)$, is optimal in both time and space as $\Omega(n+h\log h)$ is a lower bound on the runtime. Our algorithm builds a shortest path map for a source point $s$, so that given any query point $t$, the shortest path length from $s$ to $t$ can be computed in $O(\log n)$ time and a shortest $s$-$t$ path can be produced in additional time linear in the number of edges of the path., Comment: To appear in STOC 2021

Time Reversal Symmetry (TRS) broken topological phases provide gapless surface states protected by topology, regardless of additional internal symmetries, spin or valley degrees of freedom. Despite the numerous demonstrations of 2D topological phases, few examples of 3D topological systems with TRS breaking exist. In this article, we devise a general strategy to design 3D Chern insulating (3D CI) cubic photonic crystals in a weakly TRS broken environment with orientable and arbitrarily large Chern vectors. The designs display topologically protected chiral and unidirectional surface states with disjoint equifrequency loops. The resulting crystals present the following characteristics: First, by increasing the Chern number, multiple surface states channels can be supported. Second, the Chern vector can be oriented along any direction simply changing the magnetization axis, opening up larger 3D CI/3D CI interfacing possibilities as compared to 2D. Third, by lowering the TRS breaking requirements, the system is ideal for realistic photonic applications where the magnetic response is weak., A.G.E., C.D. and M.B.P. acknowledge support from the Spanish Ministerio de Ciencia e Innovación (PID2019-109905GA-C2) and from Eusko Jaurlaritza (IT1164-19, KK-2019/00101 and KK-2021/00082). M.G.D., I.R. and M.G.V. acknowledge the Spanish Ministerio de Ciencia e Innovacion (grant PID2019-109905GB-C21). J.L.A. acknowledges support from the Spanish Ministerio de Ciencia e Innovación (PID2019-109905GA-C2). The work of B.B. is supported by the Air Force Office of Scientific Research under award number FA9550-21-1-0131. C.D. acknowledges financial support from the MICIU through the FPI PhD Fellowship CEX2018-000867-S-19-1. The work of J.L.M. has been supported by Spanish Science Ministry grant PGC2018-094626-BC21 (MCIU/AEI/FEDER, EU) and Basque Government grant IT979-16. A.G.E. and M. G. V. acknowledge funding from Programa Red Guipuzcoana de Ciencia, Tecnología e Innovación 2021 (Grant Nr. 2021-CIEN-000070-01. Gipuzkoa Next).

Generative Adversarial Networks (GAN) are a powerful methodology and can be used for unsupervised anomaly detection, where current techniques have limitations such as the accurate detection of anomalies near the tail of a distribution. GANs generally do not guarantee the existence of a probability density and are susceptible to mode collapse, while few GANs use likelihood to reduce mode collapse. In this paper, we create a GAN-based tail formation model for anomaly detection, the Tail of distribution GAN (TailGAN), to generate samples on the tail of the data distribution and detect anomalies near the support boundary. Using TailGAN, we leverage GANs for anomaly detection and use maximum entropy regularization. Using GANs that learn the probability of the underlying distribution has advantages in improving the anomaly detection methodology by allowing us to devise a generator for boundary samples, and use this model to characterize anomalies. TailGAN addresses supports with disjoint components and achieves competitive performance on images. We evaluate TailGAN for identifying Out-of-Distribution (OoD) data and its performance evaluated on MNIST, CIFAR-10, Baggage X-Ray, and OoD data shows competitiveness compared to methods from the literature., Comment: 5 pages, 2020 Sensor Signal Processing for Defence Conference (SSPD)

Answer Set Programming (ASP) is a successful method for solving a range of real-world applications. Despite the availability of fast ASP solvers, computing answer sets demands a very large computational power, since the problem tackled is in the second level of the polynomial hierarchy. A speed-up in answer set computation may be attained, if the program can be split into two disjoint parts, bottom and top. Thus, the bottom part is evaluated independently of the top part, and the results of the bottom part evaluation are used to simplify the top part. Lifschitz and Turner have introduced the concept of a splitting set, i.e., a set of atoms that defines the splitting. In this paper, We show that the problem of computing a splitting set with some desirable properties can be reduced to a classic Search Problem and solved in polynomial time. This allows us to conduct experiments on the size of the splitting set in various programs and lead to an interesting discovery of a source of complication in stable model computation. We also show that for Head-Cycle-Free programs, the definition of splitting sets can be adjusted to allow splitting of a broader class of programs., Comment: In Proceedings ICLP 2021, arXiv:2109.07914

We derive a method to enhance the evaluation for a text-based Emotion Aware Recommender that we have developed. However, we did not implement a suitable way to assess the top-N recommendations subjectively. In this study, we introduce an emotion-aware Pseudo Association Method to interconnect disjointed users across different datasets so data files can be combined to form a more extensive data file. Users with the same user IDs found in separate data files in the same dataset are often the same users. However, users with the same user ID may not be the same user across different datasets. We advocate an emotion aware Pseudo Association Method to associate users across different datasets. The approach interconnects users with different user IDs across different datasets through the most similar users' emotion vectors (UVECs). We found the method improved the evaluation process of assessing the top-N recommendations objectively., Comment: 21 pages, 9 tables. arXiv admin note: substantial text overlap with arXiv:2007.01455

Point feature labeling is a classical problem in cartography and GIS that has been extensively studied for geospatial point data. At the same time, word clouds are a popular visualization tool to show the most important words in text data which has also been extended to visualize geospatial data (Buchin et al. PacificVis 2016). In this paper, we study a hybrid visualization, which combines aspects of word clouds and point labeling. In the considered setting, the input data consists of a set of points grouped into categories and our aim is to place multiple disjoint and axis-aligned rectangles, each representing a category, such that they cover points of (mostly) the same category under some natural quality constraints. In our visualization, we then place category names inside the computed rectangles to produce a labeling of the covered points which summarizes the predominant categories globally (in a word-cloud-like fashion) while locally avoiding excessive misrepresentation of points (i.e., retaining the precision of point labeling). We show that computing a minimum set of such rectangles is NP-hard. Hence, we turn our attention to developing heuristics and exact SAT models to compute our visualizations. We evaluate our algorithms quantitatively, measuring running time and quality of the produced solutions, on several artificial and real-world data sets. Our experiments show that the heuristics produce solutions of comparable quality to the SAT models while running much faster., Comment: 22 pages, 11 figures (21 subfigures), accepted by sigspatial 2021

We establish the existence of solutions to a weakly-coupled competitive system of polyharmonic equations in \begin{document}$ \mathbb{R}^N $\end{document} which are invariant under a group of conformal diffeomorphisms, and study the behavior of least energy solutions as the coupling parameters tend to \begin{document}$ -\infty $\end{document}. We show that the supports of the limiting profiles of their components are pairwise disjoint smooth domains and solve a nonlinear optimal partition problem of \begin{document}$ \mathbb R^N $\end{document}. We give a detailed description of the shape of these domains.

We propose a novel alignment mechanism to deal with procedural reasoning on a newly released multimodal QA dataset, named RecipeQA. Our model is solving the textual cloze task which is a reading comprehension on a recipe containing images and instructions. We exploit the power of attention networks, cross-modal representations, and a latent alignment space between instructions and candidate answers to solve the problem. We introduce constrained max-pooling which refines the max-pooling operation on the alignment matrix to impose disjoint constraints among the outputs of the model. Our evaluation result indicates a 19\% improvement over the baselines., Comment: Published in ALVR 2020, a workshop in ACL 2020

In this paper, we introduce a reinforcement learning approach utilizing a novel topology-based information gain metric for directing the next best view of a noisy 3D sensor. The metric combines the disjoint sections of an observed surface to focus on high-detail features such as holes and concave sections. Experimental results show that our approach can aid in establishing the placement of a robotic sensor to optimize the information provided by its streaming point cloud data. Furthermore, a labeled dataset of 3D objects, a CAD design for a custom robotic manipulator, and software for the transformation, union, and registration of point clouds has been publicly released to the research community., Comment: To be published in the 2021 IEEE International Conference on Robotics and Automation (ICRA)

A functional k-batch code of dimension $s$ consists of $n$ servers storing linear combinations of $s$ linearly independent information bits. Any multiset request of size $k$ of linear combinations (or requests) of the information bits can be recovered by $k$ disjoint subsets of the servers. The goal under this paradigm is to find the minimum number of servers for given values of $s$ and $k$ . A recent conjecture states that for any $k=2^{s-1}$ requests the optimal solution requires $2^{s}-1$ servers. This conjecture is verified for $s\leqslant 5$ but previous work could only show that codes with $n=2^{s}-1$ servers can support a solution for $k=2^{s-2}+2^{s-4}+ \left\lfloor\frac{2^{s/2}}{\sqrt{24}} \right\rfloor$ requests. This paper reduces this gap and shows the existence of codes for $k= \lfloor\frac{2}{3}2^{s-1}\rfloor$ requests with the same number of servers. Another construction in the paper provides a code with $n=2^{s+1}-2$ servers and $k=2^{s}$ requests, which is an optimal result. These constructions are mainly based on Hadamard codes and equivalently provide constructions for parallel Random I/O (RIO) codes.

Label noise in training data can significantly degrade a model's generalization performance for supervised learning tasks. Here we focus on the problem that noisy labels are primarily mislabeled samples, which tend to be concentrated near decision boundaries, rather than uniformly distributed, and whose features should be equivocal. To address the problem, we propose an ensemble learning method to correct noisy labels by exploiting the local structures of feature manifolds. Different from typical ensemble strategies that increase the prediction diversity among sub-models via certain loss terms, our method trains sub-models on disjoint subsets, each being a union of the nearest-neighbors of randomly selected seed samples on the data manifold. As a result, each sub-model can learn a coarse representation of the data manifold along with a corresponding graph. Moreover, only a limited number of sub-models will be affected by locally-concentrated noisy labels. The constructed graphs are used to suggest a series of label correction candidates, and accordingly, our method derives label correction results by voting down inconsistent suggestions. Our experiments on real-world noisy label datasets demonstrate the superiority of the proposed method over existing state-of-the-arts.

We prove that for all positive integers n and k, there exists an integer N = N ( n , k ) satisfying the following. If U is a set of k nonzero vectors in the plane and J U is the set of all line segments in direction u for some u ∈ U , then for every N families F 1 , … , F N , each consisting of n mutually disjoint segments in J U , there is a set { A 1 , … , A n } of n disjoint segments in ⋃ 1 ≤ i ≤ N F i and distinct integers p 1 , … , p n ∈ { 1 , … , N } satisfying that A j ∈ F p j for all j ∈ { 1 , … , n } . We generalize this property for underlying lines on fixed k directions to k families of simple curves with certain conditions.

We continue the study of real-time replica wormholes initiated in arXiv:2012.00828. Previously, we had discussed the general principles and had outlined a variational principle for obtaining stationary points of the real-time gravitational path integral. In the current work we present several explicit examples in low-dimensional gravitational theories where the dynamics is amenable to analytic computation. We demonstrate the computation of R\'enyi entropies in the cases of JT gravity and for holographic two-dimensional CFTs (using the dual gravitational dynamics). In particular, we explain how to obtain the large central charge result for subregions comprising of disjoint intervals directly from the real-time path integral., Comment: 53 pages, 11 figures. v2: clarifications for JT example, fixed typos

The separation dimension of a hypergraph $G$ is the smallest natural number $d$ for which there is an embedding of $G$ into $\mathbb{R}^d$, such that any pair of disjoint edges is separated by some hyperplane normal to one of the axes. The perfect separation dimension further requires that any pair of disjoint edges is separated by the same amount of such (pairwise nonparallel) hyperplanes. While it is known that for any fixed $r \ge 2$, the separation dimension of any $n$-vertex $r$-graph is $O(\log n)$, the perfect separation dimension is much larger. In fact, no polynomial upper-bound for the perfect separation dimension of $r$-uniform hypergraphs is known. In our first result we essentially resolve the case $r=2$, i.e. graphs. We prove that the perfect separation dimension of $K_n$ is linear in $n$, up to a small polylogarithmic factor. In fact, we prove it is at least $n/2-1$ and at most $n(\log n)^{1+o(1)}$. Our second result proves that the perfect separation dimension of almost all graphs is also linear in $n$, up to a logarithmic factor. This follows as a special case of a more general result showing that the perfect separation dimension of the random graph $G(n,p)$ is w.h.p. $\Omega(n p /\log n)$ for a wide range of values of $p$, including all constant $p$. Finally, we prove that significantly relaxing perfection to just requiring that any pair of disjoint edges of $K_n$ is separated the same number of times up to a difference of $c \log n$ for some absolute constant $c$, still requires the dimension to be $\Omega(n)$. This is perhaps surprising as it is known that if we allow a difference of $7\log_2 n$, then the dimension reduces to $O(\log n)$., Comment: 22 pages, to appear in J. Combin. Des

It is well known that, whenever $k$ divides $n$, the complete $k$-uniform hypergraph on $n$ vertices can be partitioned into disjoint perfect matchings. Equivalently, the set of $k$-subsets of an $n$-set can be partitioned into parallel classes so that each parallel class is a partition of the $n$-set. This result is known as Baranyai's theorem, which guarantees the existence of \emph{Baranyai partitions}. Unfortunately, the proof of Baranyai's theorem uses network flow arguments, making this result non-explicit. In particular, there is no known method to produce Baranyai partitions in time and space that scale linearly with the number of hyperedges in the hypergraph. It is desirable for certain applications to have an explicit construction that generates Baranyai partitions in linear time. Such an efficient construction is known for $k=2$ and $k=3$. In this paper, we present an explicit recursive quadrupling construction for $k=4$ and $n=4t$, where $t \equiv 0,3,4,6,8,9 ~(\text{mod}~12)$. In a follow-up paper (Part II), the other values of~$t$, namely $t \equiv 1,2,5,7,10,11 ~(\text{mod}~12)$, will be considered.

We consider quasi-periodically systems in the presence of dissipation and study the existence of response solutions, i.e. quasi-periodic solutions with the same frequency vector as the forcing term. When the dissipation is large enough and a suitable function involving the forcing has a simple zero, response solutions are known to exist without assuming any non resonance condition on the frequency vector. We analyse the case of non-simple zeroes and, in order to deal with the small divisors problem, we confine ourselves to two-dimensional frequency vectors, so as to use the properties of continued fractions. We show that, if the order of the zero is odd (if it is even, in general no response solution exists), a response solution still exists provided the inverse of the parameter measuring the dissipation belongs to a set given by the union of infinite intervals depending on the convergents of the ratio of the two components of the frequency vector. The intervals may be disjoint and as a consequence we obtain the existence of response solutions in a set with "holes". If we want the set to be connected we have to require some non-resonance condition on the frequency: in fact, we need a condition weaker than the Bryuno condition usually considered in small divisors problems., Comment: 34 pages, 4 figures

Let $X$ be an $n$-element set, where $n$ is even. We refute a conjecture of J. Gordon and Y. Teplitskaya, according to which, for every maximal intersecting family $\mathcal{F}$ of $\frac{n}2$-element subsets of $X$, one can partition $X$ into $\frac{n}2$ disjoint pairs in such a way that no matter how we pick one element from each of the first $\frac{n}2 - 1$ pairs, the set formed by them can always be completed to a member of $\mathcal{F}$ by adding an element of the last pair. The above problem is related to classical questions in extremal set theory. For any $t\ge 2$, we call a family of sets $\mathcal{F}\subset 2^X$ {\em $t$-separable} if for any ordered pair of elements $(x,y)$ of $X$, there exists $F\in\mathcal{F}$ such that $F\cap\{x,y\}=\{x\}$. For a fixed $t, 2\le t\le 5$ and $n\rightarrow\infty$, we establish asymptotically tight estimates for the smallest integer $s=s(n,t)$ such that every family $\mathcal{F}$ with $|\mathcal{F}|\ge s$ is $t$-separable., Comment: 12 pages

We define wedge-lifted codes, a variant of lifted codes, and we study their locality properties. We show that (taking the trace of) wedge-lifted codes yields binary codes with the $t$-disjoint repair property ($t$-DRGP). When $t = N^{1/2d}$, where $N$ is the block length of the code and $d \geq 2$ is any integer, our codes give improved trade-offs between redundancy and locality among binary codes., Comment: 13 pages. Fixed a few typos found in Section 3.3 and Section 4 of the previous submission. The relevant bit patterns in Section 3.3 repeat mod $\ell'$ instead of mod $d$. The inner summation in Lemma 4.1 is over $\mathbb F_q$ and not $\mathbb F_2$

We investigate the problem of using mobile robots equipped with 2D range sensors to optimally guard perimeters or regions, i.e., 1D or 2D sets. Given such a set of arbitrary shape to be guarded, and $k$ mobile sensors where the $i$-th sensor can guard a circular region with a variable radius $r_i$, we seek the optimal strategy to deploy the $k$ sensors to fully cover the set such that $\max r_i$ is minimized. On the side of computational complexity, we show that computing a $1.152$-optimal solution for guarding a perimeter or a region is NP-hard, i.e., the problem is hard to approximate. The hardness result on perimeter guarding holds when each sensor may guard at most two disjoint perimeter segments. On the side of computational methods, for the guarding perimeters, we develop a fully polynomial time approximation scheme (FPTAS) for the special setting where each sensor may only guard a single continuous perimeter segment, suggesting that the aforementioned hard-to-approximate result on the two-disjoint-segment sensing model is tight. For the general problem, we first describe a polynomial-time (2+$\epsilon)$-approximation algorithm as an upper bound, applicable to both perimeter guarding and region guarding. This is followed by a high-performance integer linear programming (ILP) based method that computes near-optimal solutions. Thorough computational benchmarks as well as evaluation on potential application scenarios demonstrate the effectiveness of these algorithmic solutions.

In this note we study IR limits of pure two-dimensional supersymmetric gauge theories with semisimple non-simply-connected gauge groups including SU(k)/Z_k, SO(2k)/Z_2, Sp(2k)/Z_2, E_6/Z_3, and E_7/Z_2 for various discrete theta angles, both directly in the gauge theory and also in nonabelian mirrors, extending a classification begun in previous work. We find in each case that there are supersymmetric vacua for precisely one value of the discrete theta angle, and no supersymmetric vacua for other values, hence supersymmetry is broken in the IR for most discrete theta angles. Furthermore, for the one distinguished value of the discrete theta angle for which supersymmetry is unbroken, the theory has as many twisted chiral multiplet degrees of freedom in the IR as the rank. We take this opportunity to further develop the technology of nonabelian mirrors to discuss how the mirror to a G gauge theory differs from the mirror to a G/K gauge theory for K a subgroup of the center of G. In particular, the discrete theta angles in these cases are considerably more intricate than those of the pure gauge theories studied in previous papers, so we discuss the realization of these more complex discrete theta angles in the mirror construction. We find that discrete theta angles, both in the original gauge theory and their mirrors, are intimately related to the descriptions of centers of universal covering groups as quotients of weight lattices by root sublattices. We perform numerous consistency checks, comparing results against basic group-theoretic relations as well as with decomposition, which describes how two-dimensional theories with one-form symmetries (such as pure gauge theories with nontrivial centers) decompose into disjoint unions, in this case of pure gauge theories with quotiented gauge groups and discrete theta angles., Comment: LaTeX, 49 pages, 1 figure; v2: reference added

In this work we prove that the eigenvalues of the $n$-dimensional massive Dirac operator $\mathscr{D}_0 + V$, $n\ge2$, perturbed by a possibly non-Hermitian potential $V$, are localized in the union of two disjoint disks of the complex plane, provided that $V$ is sufficiently small with respect to the mixed norms $L^1_{x_j} L^\infty_{\widehat{x}_j}$, for $j\in\{1,\dots,n\}$. In the massless case, we prove instead that the discrete spectrum is empty under the same smallness assumption on $V$, and in particular the spectrum is the same of the unperturbed operator, namely $\sigma(\mathscr{D}_0+V)=\sigma(\mathscr{D}_0)=\mathbb{R}$. The main tools we employ are an abstract version of the Birman-Schwinger principle, which include also the study of embedded eigenvalues, and suitable resolvent estimates for the Schr\"odinger operator., Comment: 20 pages

It is a well-known result due to E. St{\o}rmer that every positive qubit map is decomposable into a sum of a completely positive map and a completely copositive map. Here, we generalize this result to tensor squares of qubit maps. Specifically, we show that any positive tensor product of a qubit map with itself is decomposable. This solves a recent conjecture by S. Fillipov and K. Magadov. We contrast this result with examples of non-decomposable positive maps arising as the tensor product of two distinct qubit maps or as the tensor square of a decomposable map from a qubit to a ququart. To show our main result, we reduce the problem to Pauli diagonal maps. We then characterize the cone of decomposable ququart Pauli diagonal maps by determining all 252 extremal rays of ququart Pauli diagonal maps that are both completely positive and completely copositive. These extremal rays split into three disjoint orbits under a natural symmetry group, and two of these orbits contain only entanglement breaking maps. Finally, we develop a general combinatorial method to determine the extremal rays of Pauli diagonal maps that are both completely positive and completely copositive between multi-qubit systems using the ordered spectra of their Choi matrices. Classifying these extremal rays beyond ququarts is left as an open problem., Comment: 63 pages, 4 figures, 3 tables. Matlab code to verify one of the main results is included as auxiliary material. Comments are welcome!

All the known counterexamples to Kac' famous question "can one hear the shape of a drum", i.e., does isospectrality of two Laplacians on domains imply that the domains are congruent, consist of pairs of domains composed of copies of isometric building blocks arranged in different ways, such that the unitary operator intertwining the Laplacians acts as a sum of overlapping "local" isometries mapping the copies to each other. We prove and explore a complementary positive statement: if an operator intertwining two appropriate realisations of the Laplacian on a pair of domains preserves disjoint supports, then under additional assumptions on it generally far weaker than unitarity, the domains are congruent. We show this in particular for the Dirichlet, Neumann and Robin Laplacians on spaces of continuous functions and on $L^2$-spaces.

Representations of planar triangulations as contact graphs of a set of internally disjoint homothetic triangles or of a set of internally disjoint homothetic squares have received quite some attention in recent years. In this paper we investigate representations of planar triangulations as contact graphs of a set of internally disjoint homothetic pentagons. Surprisingly such a representation exists for every triangulation whose outer face is a $5$-gon. We relate these representations to five color forests. These combinatorial structures resemble Schnyder woods and transversal structures, respectively. In particular there is a bijection to certain $\alpha$-orientations and consequently a lattice structure on the set of five color forests of a given graph. This lattice structure plays a role in an algorithm that is supposed to compute a contact representation with pentagons for a given graph. Based on a five color forest the algorithm builds a system of linear equations and solves it, if the solution is non-negative, it encodes distances between corners of a pentagon representation. In this case the representation is constructed and the algorithm terminates. Otherwise negative variables guide a change of the five color forest and the procedure is restarted with the new five color forest. Similar algorithms have been proposed for contact representations with homothetic triangles and with squares.

The Julia set of the exponential family $E_{\kappa}:z\mapsto\kappa e^z$, $\kappa>0$ was shown to be the entire complex plane when $\kappa>1/e$ essentially by Misiurewicz. Later, Devaney and Krych showed that for $0, Comment: 33 pages, 3 figures, final version, to appear in Ergodic theory and Dynamical Systems

We study the problem of allocating indivisible goods among agents with additive valuations. When randomization is allowed, it is possible to achieve compelling notions of fairness such as envy-freeness, which states that no agent should prefer any other agent's allocation to her own. When allocations must be deterministic, achieving exact fairness is impossible but approximate notions such as envy-freeness up to one good can be guaranteed. Our goal in this work is to achieve both simultaneously, by constructing a randomized allocation that is exactly fair ex-ante and approximately fair ex-post. The key question we address is whether ex-ante envy-freeness can be achieved in combination with ex-post envy-freeness up to one good. We settle this positively by designing an efficient algorithm that achieves both properties simultaneously. If we additionally require economic efficiency, we obtain an impossibility result. However, we show that economic efficiency and ex-ante envy-freeness can be simultaneously achieved if we slightly relax our ex-post fairness guarantee. On our way, we characterize the well-known Maximum Nash Welfare allocation rule in terms of a recently introduced fairness guarantee that applies to groups of agents, not just individuals., Comment: Full version of a paper published as an extended abstract at Economics and Computation (EC) 2020

We show an infinite family of satellite knots that can be unknotted by a single band move, but such that there is no band unknotting the knots which is disjoint from the satellite torus., Comment: 10 pages, 5 figures

Understanding how goals control behavior is a question ripe for interrogation by new methods from machine learning. These methods require large and labeled datasets to train models. To annotate a large-scale image dataset with observed search fixations, we collected 16,184 fixations from people searching for either microwaves or clocks in a dataset of 4,366 images (MS-COCO). We then used this behaviorally-annotated dataset and the machine learning method of inverse-reinforcement learning (IRL) to learn target-specific reward functions and policies for these two target goals. Finally, we used these learned policies to predict the fixations of 60 new behavioral searchers (clock = 30, microwave = 30) in a disjoint test dataset of kitchen scenes depicting both a microwave and a clock (thus controlling for differences in low-level image contrast). We found that the IRL model predicted behavioral search efficiency and fixation-density maps using multiple metrics. Moreover, reward maps from the IRL model revealed target-specific patterns that suggest, not just attention guidance by target features, but also guidance by scene context (e.g., fixations along walls in the search of clocks). Using machine learning and the psychologically-meaningful principle of reward, it is possible to learn the visual features used in goal-directed attention control.

We present a coupling of the Finite Element and the Boundary Element Method in an isogeometric framework to approximate either two-dimensional Laplace interface problems or boundary value problems consisting of two disjoint domains. We consider the Finite Element Method in the bounded domains to simulate possibly non-linear materials. The Boundary Element Method is applied in unbounded or thin domains where the material behavior is linear. The isogeometric framework allows to combine different design and analysis tools: first, we consider the same type of NURBS parameterizations for an exact geometry representation and second, we use the numerical analysis for the Galerkin approximation. Moreover, it facilitates to perform h- and p-refinements. For the sake of analysis, we consider the framework of strongly monotone and Lipschitz continuous operators to ensure well-posedness of the coupled system. Furthermore, we provide a priori error estimates. We additionally show an improved convergence behavior for the errors in functionals of the solution that may double the rate under certain assumptions. Numerical examples conclude the work which illustrate the theoretical results.

For a simply connected domain G, we study the problem of disjoint universality for the sequences of operators T α , n : H ( G ) → H ( G ) , defined by T α , n ( f ) ( z ) = ∑ j = 0 n f ( j ) ( z ) j ! ( α z ) j , where α ∈ C ∖ { 0 } . Note that T α , n ( f ) ( z ) is the n t h partial sum of the Taylor expansion of f around z on ( α + 1 ) z . The motivation to study such sequences comes from universal Taylor series, by changing the role of the center of expansion.

We develop an extension of subhalo abundance matching (SHAM) capable of accurately reproducing the real and redshift-space clustering of galaxies in a state-of-the-art hydrodynamical simulation. Our method uses a low-resolution gravity-only simulation and it includes orphan and tidal disruption prescriptions for satellite galaxies, and a flexible amount of galaxy assembly bias. Furthermore, it includes recipes for star formation rate (SFR) based on the dark matter accretion rate. We test the accuracy of our model against catalogues of stellar-mass- and SFR-selected galaxies in the TNG300 hydrodynamic simulation. By fitting a small number of free parameters, our extended SHAM reproduces the projected correlation function and redshift-space multipoles for number densities $10^{-3} - 10^{-2}\, h^{3}{\rm Mpc}^{-3}$, at $z=1$ and $z=0$, and for scales $r \in [0.3 - 20] h^{-1}{\rm Mpc}$. Simultaneously, the SHAM results also retrieve the correct halo occupation distribution, the level of galaxy assembly bias, and higher-order statistics present in the TNG300 galaxy catalogues. As an application, we show that our model simultaneously fits the projected correlation function of the SDSS in 3 disjoint stellar mass bins, with an accuracy similar to that of TNG300 galaxies. This SHAM extension can be used to get accurate clustering prediction even when using low and moderate-resolution simulations., Comment: 14 pages, 12 figures. Submitted to MNRAS

In the early 1980s, Johnson defined a homomorphism $\mathcal {I}_{g}^1\to \bigwedge ^3 H_1\left (S_{g},\mathbb {Z}\right )$ , where $\mathcal {I}_{g}^1$ is the Torelli group of a closed, connected, and oriented surface of genus g with a boundary component and $S_g$ is the corresponding surface without a boundary component. This is known as the Johnson homomorphism. We study the map induced by the Johnson homomorphism on rational homology groups and apply it to abelian cycles determined by disjoint bounding-pair maps, in order to compute a large quotient of $H_n\left (\mathcal {I}_{g}^1,\mathbb {Q}\right )$ in the stable range. This also implies an analogous result for the stable rational homology of the Torelli group $\mathcal {I}_{g,1}$ of a surface with a marked point instead of a boundary component. Further, we investigate how much of the image of this map is generated by images of such cycles and use this to prove that in the pointed case, they generate a proper subrepresentation of $H_n\left (\mathcal {I}_{g,1}\right )$ for $n\ge 2$ and g large enough.

In this paper, we propose a novel orthogonal frequency division multiplexing with index modulation (OFDM-IM) scheme, which we call Q-ary multi-mode OFDM-IM (Q-MM-OFDM-IM). In the proposed scheme, Q disjoint M-ary constellations are used repeatedly on each subcarrier, and a maximum-distance separable code is applied to the indices of these constellations to achieve the highest number of index symbols. A low-complexity subcarrier-wise detection is shown possible for the proposed scheme. Spectral efficiency (SE) and the error rate performance of the proposed scheme are further analyzed. It is shown that the proposed scheme exhibits a very flexible structure that is capable of encompassing conventional OFDM as a special case. It is also shown that the proposed scheme is capable of considerably outperforming the other OFDM-IM schemes and conventional OFDM in terms of error and SE performance while preserving a low-complexity structure., Comment: 5 pages, 2 figures

Large sets of combinatorial designs has always been a fascinating topic in design theory. These designs form a partition of the whole space into combinatorial designs with the same parameters. In particular, a large set of block designs, whose blocks are of size k taken from an n-set, is a partition of all the k-subsets of the n-set into disjoint copies of block designs, defined on the n-set, and with the same parameters. The current most intriguing question in this direction is whether large sets of Steiner quadruple systems exist and to provide explicit constructions for those parameters for which they exist. In view of its difficulty no one ever presented an explicit construction even for one nontrivial order. Hence, we seek for related generalizations. As generalizations, to the existence question of large sets, we consider two related questions. The first one is to provide constructions for sets on Steiner systems in which each block (quadruple or a k-subset) is contained in exactly $$\mu $$ systems. The constructions of such systems also yield secure protocols for the generalized Russian cards problem. The second question is to provide constructions for large set of H-designs (mainly for quadruples, but also for larger block size), which have applications in threshold schemes and in quantum jump codes. We prove the existence of such systems for many parameters using orthogonal arrays, perpendicular arrays, ordered designs, sets of permutations, and one-factorizations of the complete graph.

Kirkman triple systems (KTSs) are among the most popular combinatorial designs and their existence has been settled a long time ago. Yet, in comparison with Steiner triple systems, little is known about their automorphism groups. In particular, there is no known congruence class representing the orders of a KTS with a number of automorphisms at least close to the number of points. We fill this gap by proving that whenever $v \equiv 39$ (mod 72), or $v \equiv 4^e48 + 3$ (mod $4^e96$) and $e \geq 0$, there exists a KTS on $v$ points having at least $v-3$ automorphisms. This is only one of the consequences of a careful investigation on the KTSs with an automorphism group $G$ acting sharply transitively on all but three points. Our methods are all constructive and yield KTSs which in many cases inherit some of the automorphisms of $G$, thus increasing the total number of symmetries. To obtain these results it was necessary to introduce new types of difference families (the doubly disjoint ones) and difference matrices (the splittable ones) which we believe are interesting by themselves., Comment: 37 pages

For a function $f$ from $\mathbb{F}_2^n$ to $\mathbb{F}_2^n$, the planarity of $f$ is usually measured by its differential uniformity and differential spectrum. In this paper, we propose the concept of vanishing flats, which supplies a combinatorial viewpoint on the planarity. First, the number of vanishing flats of $f$ can be regarded as a measure of the distance between $f$ and the set of almost perfect nonlinear functions. In some cases, the number of vanishing flats serves as an "intermediate" concept between differential uniformity and differential spectrum, which contains more information than differential uniformity, however less than the differential spectrum. Secondly, the set of vanishing flats forms a combinatorial configuration called partial quadruple system, since it convey detailed structural information about $f$. We initiate this study by considering the number of vanishing flats and the partial quadruple systems associated with monomials and Dembowski-Ostrom polynomials. In addition, we present an application of vanishing flats to the partition of a vector space into disjoint equidimensional affine spaces. We conclude the paper with several further questions and challenges., Comment: 12 pages, IEEE Transactions on Information Theory, Accepted

We study in detail the onset of chaos and the probability measures formed by individual Bohmian trajectories in entangled states of two-qubit systems for various degrees of entanglement. The qubit systems consist of coherent states of 1-d harmonic oscillators with irrational frequencies. In weakly entangled states chaos is manifested through the sudden jumps of the Bohmian trajectories between successive Lissajous-like figures. These jumps are succesfully interpreted by the `nodal point-X-point complex' mechanism. In strongly entangled states, the chaotic form of the Bohmian trajectories is manifested after a short time. We then study the mixing properties of ensembles of Bohmian trajectories with initial conditions satisfying Born's rule. The trajectory points are initially distributed in two sets $S_1$ and $S_2$ with disjoint supports but they exhibit, over the course of time, abrupt mixing whenever they encounter the nodal points of the wavefunction. Then a substantial fraction of trajectory points is exchanged between $S_1$ and $S_2$, without violating Born's rule. Finally, we provide strong numerical indications that, in this system, the main effect of the entanglement is the establishment of ergodicity in the individual Bohmian trajectories as $t\to\infty$: different initial conditions result to the same limiting distribution of trajectory points., Comment: 19 pages, 10 figures

A rooted digraph is a vertex-flame if for every vertex v there is a set of internally disjoint directed paths from the root to v whose set of terminal edges covers all ingoing edges of v. It was shown by Lovasz that every finite rooted digraph admits a spanning subdigraph which is a vertex-flame and large, where the latter means that it preserves the local connectivity to each vertex from the root. Calvillo-Vives rediscovered and extended this theorem proving that every vertex-flame of a given finite rooted digraph can be extended to be large. The analogue of Lovasz' result for countable digraphs was shown by the third author where the notion of largeness is interpreted in a structural way as in the infinite version of Menger's theorem. We give a common generalisation of this and Calvillo-Vives' result by showing that in every countable rooted digraph each vertex-flame can be extended to a large vertex-flame.

The large-scale search for high-performing candidate 2D materials is limited to calculating a few simple descriptors, usually with first-principles density functional theory calculations. In this work, we alleviate this issue by extending and generalizing crystal graph convolutional neural networks to systems with planar periodicity, and train an ensemble of models to predict thermodynamic, mechanical, and electronic properties. To demonstrate the utility of this approach, we carry out a screening of nearly 45,000 structures for two largely disjoint applications: namely, mechanically robust composites and photovoltaics. An analysis of the uncertainty associated with our methods indicates the ensemble of neural networks is well-calibrated and has errors comparable with those from accurate first-principles density functional theory calculations. The ensemble of models allows us to gauge the confidence of our predictions, and to find the candidates most likely to exhibit effective performance in their applications. Since the datasets used in our screening were combinatorically generated, we are also able to investigate, using an innovative method, structural and compositional design principles that impact the properties of the structures surveyed and which can act as a generative model basis for future material discovery through reverse engineering. Our approach allowed us to recover some well-accepted design principles: for instance, we find that hybrid organic-inorganic perovskites with lead and tin tend to be good candidates for solar cell applications., Comment: 31 pages, 7 figures, 6 pages of Supporting Information

We develop index theory on compact Riemannian spin manifolds with boundary in the case when the topological information is encoded by bundles which are supported away from the boundary. As a first application, we establish a "long neck principle" for a compact Riemannian spin $n$-manifold with boundary $X$, stating that if $\textrm{scal}(X)\geq n(n-1)$ and there is a nonzero degree map into the sphere $f\colon X\to S^n$ which is strictly area decreasing, then the distance between the support of $\textrm{d} f$ and the boundary of $X$ is at most $\pi/n$. This answers, in the spin setting and for strictly area decreasing maps, a question recently asked by Gromov. As a second application, we consider a Riemannian manifold $X$ obtained by removing $k$ pairwise disjoint embedded $n$-balls from a closed spin $n$-manifold $Y$. We show that if $\textrm{scal}(X)>\sigma>0$ and $Y$ satisfies a certain condition expressed in terms of higher index theory, then the radius of a geodesic collar neighborhood of $\partial X$ is at most $\pi \sqrt{(n-1)/(n\sigma)}$. Finally, we consider the case of a Riemannian $n$-manifold $V$ diffeomorphic to $N\times [-1,1]$, with $N$ a closed spin manifold with nonvanishing Rosenberg index. In this case, we show that if $\textrm{scal}(V)\geq\sigma>0$, then the distance between the boundary components of $V$ is at most $2\pi \sqrt{(n-1)/(n\sigma)}$. This last constant is sharp by an argument due to Gromov., Comment: Revised version to appear in GAFA. In Theorem A, the map f is strictly area decreasing, but see Remark 1.7. Technical issues fixed in the proofs of Lemma 5.5 and Theorem 5.2. The inequality in Proposition 3.8 is slightly strengthened

International audience; Algebraic datatypes, and among them lists and trees, have attracted a lot of interest in automated reasoning and Satisfiability Modulo Theories (SMT). Since its latest stable version, the SMT-LIB standard defines a theory of algebraic datatypes, which is currently supported by several mainstream SMT solvers. In this paper, we study this particular theory of datatypes and prove that it is strongly polite, showing also how it can be combined with other arbitrary disjoint theories using polite combination. Our results cover both inductive and finite datatypes, as well as their union. The combination method uses a new, simple, and natural notion of additivity, that enables deducing strong politeness from (weak) politeness.

In this paper, we characterize a mixed graph $F$ which contains $k$ edge and arc disjoint spanning mixed arborescences $F_{1}, \ldots, F_{k}$, such that for each $v \in V(F)$, the cardinality of $\{i \in [k]: v \text{ is the root of } F_{i}\}$ lies in some prescribed interval. This generalizes both Nash-Williams and Tutte's theorem on spanning tree packing for undirected graphs and the previous characterization on digraphs which was given by Cai [in: Arc-disjoint arborescences of digraphs, J. Graph Theory 7(2) (1983), 235-240] and Frank [in: On disjoint trees and arborescences, Algebraic Methods in Graph Theory, Colloquia Mathematica Soc. J. Bolyai, Vol. 25 (North-Holland, Amsterdam) (1978), 159-169].

We show some new results about tilings in Banach spaces. A tiling of a Banach space $X$ is a covering by closed sets with non-empty interior so that they have pairwise disjoint interiors. If moreover the tiles have inner radii uniformly bounded from below, and outer radii uniformly bounded from above, we say that the tiling is normal. In 2010 Preiss constructed a convex normal tiling of the separable Hilbert space. For Banach spaces with Schauder basis we will show that Preiss' result is still true with starshaped tiles instead of convex ones. Also, whenever $X$ is uniformly convex we give precise constructions of convex normal tilings of the unit sphere, the unit ball or in general of any convex body., Comment: 12 pages, 2 figures

In the classical private information retrieval (PIR) setup, a user wants to retrieve a file from a database or a distributed storage system (DSS) without revealing the file identity to the servers holding the data. In the quantum PIR (QPIR) setting, a user privately retrieves a classical file by receiving quantum information from the servers. The QPIR problem has been treated by Song et al. in the case of replicated servers, both without collusion and with all but one servers colluding. In this paper, the QPIR setting is extended to account for maximum distance separable (MDS) coded servers. The proposed protocol works for any $[n,k]$ -MDS code and $t$ -collusion with $t=n-k$ . Similarly to the previous cases, the rates achieved are better than those known or conjectured in the classical counterparts. Further, it is demonstrated how the protocol can adapted to achieve significantly higher retrieval rates from DSSs encoded with a locally repairable code (LRC) with disjoint repair groups, each of which is an MDS code.

A skeleton Huffman tree is a Huffman tree in which all disjoint maximal perfect subtrees are shrunk into leaves. Skeleton Huffman trees, besides saving storage space, are also used for faster decoding and for speeding up Huffman-shaped wavelet trees. In 2017 Klein et al. introduced an optimal skeleton tree: for given symbol frequencies, it has the least number of nodes among all optimal prefix-free code trees (not necessarily Huffman's) with shrunk perfect subtrees. Klein et al. described a simple algorithm that, for fixed codeword lengths, finds a skeleton tree with the least number of nodes; with this algorithm one can process each set of optimal codeword lengths to find an optimal skeleton tree. However, there are exponentially many such sets in the worst case. We describe an $O(n^2\log n)$-time algorithm that, given $n$ symbol frequencies, constructs an optimal skeleton tree and its corresponding optimal code., Comment: 12 pages, 3 figures, accepted to CSR 2020

It has long been suggested that the Cauchy horizon of dynamical black holes is subject to a weak null singularity, under the mass inflation scenario. We study in spherical symmetry the Einstein-Maxwell-Klein-Gordon equations and \textit{while we do not directly show mass inflation}, we obtain a "mass inflation/ridigity" dichotomy. More precisely, we prove assuming (sufficiently slow) decay of the charged scalar field on the event horizon, that the Cauchy horizon emanating from time-like infinity is $\mathcal{CH}_{i^+}= \mathcal{D} \cup \mathcal{S}$ for two (possibly empty) disjoint connected sets $\mathcal{D}$ and $\mathcal{S}$ such that: _$\mathcal{D}$ (the dynamical set) is a past set on which the Hawking mass blows up (mass inflation scenario). _$\mathcal{S}$ (the static set) is a future set isometric to a Reissner--Nordstr\"{o}m Cauchy horizon i.e.\ the radiation is zero on $\mathcal{S}$. As a consequence, we establish a novel classification of Cauchy horizons into three types: dynamical ($\mathcal{S}=\emptyset$), static ($\mathcal{D}=\emptyset$) or mixed, and prove that $\mathcal{CH}_{i^+}$ is globally $C^2$-inextendible. Our main motivation is the $C^2$ Strong Cosmic Censorship Conjecture for a realistic model of spherical collapse in which charged matter emulates the repulsive role of angular momentum: in our case the Einstein-Maxwell-Klein-Gordon system on one-ended space-times. As a result, we prove in spherical symmetry that: - two-ended asymptotically flat space-times are $C^2$-future-inextendible i.e. $C^2$ Strong Cosmic Censorship is true for Einstein-Maxwell-Klein-Gordon, assuming the decay of the scalar field on the event horizon at the expected rate. - In the one-ended case, the Cauchy horizon emanating from time-like infinity is $C^2$-inextendible. This result suppresses the main obstruction to $C^2$ Strong Cosmic Censorship in spherical collapse., Comment: Versions accepted for publication in Communications in Mathematical Physics

We study an end-to-end approach for conversational recommendation that dynamically manages and reasons over users’ past (offline) preferences and current (online) requests through a structured and cumulative user memory knowledge graph. This formulation extends existing state tracking beyond the boundary of a single dialog to user state tracking (UST). For this study, we create a new Memory Graph (MG) Conversational Recommendation parallel corpus called MGConvRex with 7K+ human-to-human role-playing dialogs, grounded on a large-scale user memory bootstrapped from real-world user scenarios. MGConvRex captures human-level reasoning over user memory and has disjoint training/testing sets of users for zero-shot (cold-start) reasoning for recommendation. We propose a simple yet expandable formulation for constructing and updating the MG, and an end-to-end graph-based reasoning model that updates MG from unstructured utterances and predicts optimal dialog policies (eg recommendation) based on updated MG. The prediction of our proposed model inherits the graph structure, providing a natural way to explain policies. Experiments are conducted for both offline metrics and online simulation, showing competitive results.

A graceful difference labeling (gdl for short) of a directed graph G with vertex set V is a bijection f between V and {1,...,|V|} such that, when each arc uv is assigned the difference label f(v)-f(u), the resulting arc labels are distinct. We conjecture that all disjoint unions of circuits have a gdl, except in two particular cases. We prove partial results which support this conjecture., Comment: 21 pages,15 figures, 9 tables

Edge disjoint realization problems have connections for example to discrete tomography. In this paper, we consider the edge disjoint caterpillar realizations of tree degree sequences. We give necessary and sufficient conditions when two tree degree sequences have edge disjoint caterpillar realizations. We conjecture that an arbitrary number of tree degree sequences have edge disjoint realizations if every vertex is a leaf in at most one tree. We prove that the conjecture is true if the number of tree degree sequences is at most four. We also prove that the conjecture is true if n ≥ max { 22 k − 11 , 396 } , where n is the number of vertices and k is the number of tree degree sequences.