@inproceedings{10190, abstract = {The verification of concurrent programs remains an open challenge, as thread interaction has to be accounted for, which leads to state-space explosion. Stateless model checking battles this problem by exploring traces rather than states of the program. As there are exponentially many traces, dynamic partial-order reduction (DPOR) techniques are used to partition the trace space into equivalence classes, and explore a few representatives from each class. The standard equivalence that underlies most DPOR techniques is the happens-before equivalence, however recent works have spawned a vivid interest towards coarser equivalences. The efficiency of such approaches is a product of two parameters: (i) the size of the partitioning induced by the equivalence, and (ii) the time spent by the exploration algorithm in each class of the partitioning. In this work, we present a new equivalence, called value-happens-before and show that it has two appealing features. First, value-happens-before is always at least as coarse as the happens-before equivalence, and can be even exponentially coarser. Second, the value-happens-before partitioning is efficiently explorable when the number of threads is bounded. We present an algorithm called value-centric DPOR (VCDPOR), which explores the underlying partitioning using polynomial time per class. Finally, we perform an experimental evaluation of VCDPOR on various benchmarks, and compare it against other state-of-the-art approaches. Our results show that value-happens-before typically induces a significant reduction in the size of the underlying partitioning, which leads to a considerable reduction in the running time for exploring the whole partitioning.}, author = {Chatterjee, Krishnendu and Pavlogiannis, Andreas and Toman, Viktor}, booktitle = {Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications}, issn = {2475-1421}, keywords = {safety, risk, reliability and quality, software}, location = {Athens, Greece}, publisher = {ACM}, title = {{Value-centric dynamic partial order reduction}}, doi = {10.1145/3360550}, volume = {3}, year = {2019}, } @article{105, abstract = {Clinical Utility Gene Card. 1. Name of Disease (Synonyms): Pontocerebellar hypoplasia type 9 (PCH9) and spastic paraplegia-63 (SPG63). 2. OMIM# of the Disease: 615809 and 615686. 3. Name of the Analysed Genes or DNA/Chromosome Segments: AMPD2 at 1p13.3. 4. OMIM# of the Gene(s): 102771.}, author = {Marsh, Ashley and Novarino, Gaia and Lockhart, Paul and Leventer, Richard}, journal = {European Journal of Human Genetics}, pages = {161--166}, publisher = {Springer Nature}, title = {{CUGC for pontocerebellar hypoplasia type 9 and spastic paraplegia-63}}, doi = {10.1038/s41431-018-0231-2}, volume = {27}, year = {2019}, } @article{319, abstract = {We study spaces of modelled distributions with singular behaviour near the boundary of a domain that, in the context of the theory of regularity structures, allow one to give robust solution theories for singular stochastic PDEs with boundary conditions. The calculus of modelled distributions established in Hairer (Invent Math 198(2):269–504, 2014. https://doi.org/10.1007/s00222-014-0505-4) is extended to this setting. We formulate and solve fixed point problems in these spaces with a class of kernels that is sufficiently large to cover in particular the Dirichlet and Neumann heat kernels. These results are then used to provide solution theories for the KPZ equation with Dirichlet and Neumann boundary conditions and for the 2D generalised parabolic Anderson model with Dirichlet boundary conditions. In the case of the KPZ equation with Neumann boundary conditions, we show that, depending on the class of mollifiers one considers, a “boundary renormalisation” takes place. In other words, there are situations in which a certain boundary condition is applied to an approximation to the KPZ equation, but the limiting process is the Hopf–Cole solution to the KPZ equation with a different boundary condition.}, author = {Gerencser, Mate and Hairer, Martin}, issn = {1432-2064}, journal = {Probability Theory and Related Fields}, number = {3-4}, pages = {697–758}, publisher = {Springer}, title = {{Singular SPDEs in domains with boundaries}}, doi = {10.1007/s00440-018-0841-1}, volume = {173}, year = {2019}, } @article{405, abstract = {We investigate the quantum Jensen divergences from the viewpoint of joint convexity. It turns out that the set of the functions which generate jointly convex quantum Jensen divergences on positive matrices coincides with the Matrix Entropy Class which has been introduced by Chen and Tropp quite recently.}, author = {Virosztek, Daniel}, journal = {Linear Algebra and Its Applications}, pages = {67--78}, publisher = {Elsevier}, title = {{Jointly convex quantum Jensen divergences}}, doi = {10.1016/j.laa.2018.03.002}, volume = {576}, year = {2019}, } @article{429, abstract = {We consider real symmetric or complex hermitian random matrices with correlated entries. We prove local laws for the resolvent and universality of the local eigenvalue statistics in the bulk of the spectrum. The correlations have fast decay but are otherwise of general form. The key novelty is the detailed stability analysis of the corresponding matrix valued Dyson equation whose solution is the deterministic limit of the resolvent.}, author = {Ajanki, Oskari H and Erdös, László and Krüger, Torben H}, issn = {1432-2064}, journal = {Probability Theory and Related Fields}, number = {1-2}, pages = {293–373}, publisher = {Springer}, title = {{Stability of the matrix Dyson equation and random matrices with correlations}}, doi = {10.1007/s00440-018-0835-z}, volume = {173}, year = {2019}, } @article{175, abstract = {An upper bound sieve for rational points on suitable varieties isdeveloped, together with applications tocounting rational points in thin sets,to local solubility in families, and to the notion of “friable” rational pointswith respect to divisors. In the special case of quadrics, sharper estimates areobtained by developing a version of the Selberg sieve for rational points.}, author = {Browning, Timothy D and Loughran, Daniel}, issn = {1088-6850}, journal = {Transactions of the American Mathematical Society}, number = {8}, pages = {5757--5785}, publisher = {American Mathematical Society}, title = {{Sieving rational points on varieties}}, doi = {10.1090/tran/7514}, volume = {371}, year = {2019}, } @inproceedings{7576, abstract = {We present the results of a friendly competition for formal verification of continuous and hybrid systems with nonlinear continuous dynamics. The friendly competition took place as part of the workshop Applied Verification for Continuous and Hybrid Systems (ARCH) in 2019. In this year, 6 tools Ariadne, CORA, DynIbex, Flow*, Isabelle/HOL, and JuliaReach (in alphabetic order) participated. They are applied to solve reachability analysis problems on four benchmark problems, one of them with hybrid dynamics. We do not rank the tools based on the results, but show the current status and discover the potential advantages of different tools.}, author = {Immler, Fabian and Althoff, Matthias and Benet, Luis and Chapoutot, Alexandre and Chen, Xin and Forets, Marcelo and Geretti, Luca and Kochdumper, Niklas and Sanders, David P. and Schilling, Christian}, booktitle = {EPiC Series in Computing}, issn = {2398-7340}, location = {Montreal, Canada}, pages = {41--61}, publisher = {EasyChair}, title = {{ARCH-COMP19 Category Report: Continuous and hybrid systems with nonlinear dynamics}}, doi = {10.29007/m75b}, volume = {61}, year = {2019}, } @inproceedings{7606, abstract = {We derive a tight lower bound on equivocation (conditional entropy), or equivalently a tight upper bound on mutual information between a signal variable and channel outputs. The bound is in terms of the joint distribution of the signals and maximum a posteriori decodes (most probable signals given channel output). As part of our derivation, we describe the key properties of the distribution of signals, channel outputs and decodes, that minimizes equivocation and maximizes mutual information. This work addresses a problem in data analysis, where mutual information between signals and decodes is sometimes used to lower bound the mutual information between signals and channel outputs. Our result provides a corresponding upper bound.}, author = {Hledik, Michal and Sokolowski, Thomas R and Tkačik, Gašper}, booktitle = {IEEE Information Theory Workshop, ITW 2019}, isbn = {9781538669006}, location = {Visby, Sweden}, publisher = {IEEE}, title = {{A tight upper bound on mutual information}}, doi = {10.1109/ITW44776.2019.8989292}, year = {2019}, } @inproceedings{7639, abstract = {Deep neural networks (DNNs) have become increasingly important due to their excellent empirical performance on a wide range of problems. However, regularization is generally achieved by indirect means, largely due to the complex set of functions defined by a network and the difficulty in measuring function complexity. There exists no method in the literature for additive regularization based on a norm of the function, as is classically considered in statistical learning theory. In this work, we study the tractability of function norms for deep neural networks with ReLU activations. We provide, to the best of our knowledge, the first proof in the literature of the NP-hardness of computing function norms of DNNs of 3 or more layers. We also highlight a fundamental difference between shallow and deep networks. In the light on these results, we propose a new regularization strategy based on approximate function norms, and show its efficiency on a segmentation task with a DNN.}, author = {Rannen-Triki, Amal and Berman, Maxim and Kolmogorov, Vladimir and Blaschko, Matthew B.}, booktitle = {Proceedings of the 2019 International Conference on Computer Vision Workshop}, isbn = {9781728150239}, location = {Seoul, South Korea}, publisher = {IEEE}, title = {{Function norms for neural networks}}, doi = {10.1109/ICCVW.2019.00097}, year = {2019}, } @inproceedings{7640, abstract = {We propose a new model for detecting visual relationships, such as "person riding motorcycle" or "bottle on table". This task is an important step towards comprehensive structured mage understanding, going beyond detecting individual objects. Our main novelty is a Box Attention mechanism that allows to model pairwise interactions between objects using standard object detection pipelines. The resulting model is conceptually clean, expressive and relies on well-justified training and prediction procedures. Moreover, unlike previously proposed approaches, our model does not introduce any additional complex components or hyperparameters on top of those already required by the underlying detection model. We conduct an experimental evaluation on two datasets, V-COCO and Open Images, demonstrating strong quantitative and qualitative results.}, author = {Kolesnikov, Alexander and Kuznetsova, Alina and Lampert, Christoph and Ferrari, Vittorio}, booktitle = {Proceedings of the 2019 International Conference on Computer Vision Workshop}, isbn = {9781728150239}, location = {Seoul, South Korea}, publisher = {IEEE}, title = {{Detecting visual relationships using box attention}}, doi = {10.1109/ICCVW.2019.00217}, year = {2019}, } @unpublished{7950, abstract = {The input to the token swapping problem is a graph with vertices v1, v2, . . . , vn, and n tokens with labels 1,2, . . . , n, one on each vertex. The goal is to get token i to vertex vi for all i= 1, . . . , n using a minimum number of swaps, where a swap exchanges the tokens on the endpoints of an edge.Token swapping on a tree, also known as “sorting with a transposition tree,” is not known to be in P nor NP-complete. We present some partial results: 1. An optimum swap sequence may need to perform a swap on a leaf vertex that has the correct token (a “happy leaf”), disproving a conjecture of Vaughan. 2. Any algorithm that fixes happy leaves—as all known approximation algorithms for the problem do—has approximation factor at least 4/3. Furthermore, the two best-known 2-approximation algorithms have approximation factor exactly 2. 3. A generalized problem—weighted coloured token swapping—is NP-complete on trees, but solvable in polynomial time on paths and stars. In this version, tokens and vertices have colours, and colours have weights. The goal is to get every token to a vertex of the same colour, and the cost of a swap is the sum of the weights of the two tokens involved.}, author = {Biniaz, Ahmad and Jain, Kshitij and Lubiw, Anna and Masárová, Zuzana and Miltzow, Tillmann and Mondal, Debajyoti and Naredla, Anurag Murty and Tkadlec, Josef and Turcotte, Alexi}, booktitle = {arXiv}, title = {{Token swapping on trees}}, doi = {10.48550/arXiv.1903.06981}, year = {2019}, } @article{8, abstract = {Despite their different origins, Drosophila glia and hemocytes are related cell populations that provide an immune function. Drosophila hemocytes patrol the body cavity and act as macrophages outside the nervous system whereas glia originate from the neuroepithelium and provide the scavenger population of the nervous system. Drosophila glia are hence the functional orthologs of vertebrate microglia, even though the latter are cells of immune origin that subsequently move into the brain during development. Interestingly, the Drosophila immune cells within (glia) and outside the nervous system (hemocytes) require the same transcription factor Glide/Gcm for their development. This raises the issue of how do glia specifically differentiate in the nervous system and hemocytes in the procephalic mesoderm. The Repo homeodomain transcription factor and pan-glial direct target of Glide/Gcm is known to ensure glial terminal differentiation. Here we show that Repo also takes center stage in the process that discriminates between glia and hemocytes. First, Repo expression is repressed in the hemocyte anlagen by mesoderm-specific factors. Second, Repo ectopic activation in the procephalic mesoderm is sufficient to repress the expression of hemocyte-specific genes. Third, the lack of Repo triggers the expression of hemocyte markers in glia. Thus, a complex network of tissue-specific cues biases the potential of Glide/Gcm. These data allow us to revise the concept of fate determinants and help us understand the bases of cell specification. Both sexes were analyzed.SIGNIFICANCE STATEMENTDistinct cell types often require the same pioneer transcription factor, raising the issue of how does one factor trigger different fates. In Drosophila, glia and hemocytes provide a scavenger activity within and outside the nervous system, respectively. While they both require the Glide/Gcm transcription factor, glia originate from the ectoderm, hemocytes from the mesoderm. Here we show that tissue-specific factors inhibit the gliogenic potential of Glide/Gcm in the mesoderm by repressing the expression of the homeodomain protein Repo, a major glial-specific target of Glide/Gcm. Repo expression in turn inhibits the expression of hemocyte-specific genes in the nervous system. These cell-specific networks secure the establishment of the glial fate only in the nervous system and allow cell diversification.}, author = {Trébuchet, Guillaume and Cattenoz, Pierre B and Zsámboki, János and Mazaud, David and Siekhaus, Daria E and Fanto, Manolis and Giangrande, Angela}, journal = {Journal of Neuroscience}, number = {2}, pages = {238--255}, publisher = {Society for Neuroscience}, title = {{The Repo homeodomain transcription factor suppresses hematopoiesis in Drosophila and preserves the glial fate}}, doi = {10.1523/JNEUROSCI.1059-18.2018}, volume = {39}, year = {2019}, } @article{80, abstract = {We consider an interacting, dilute Bose gas trapped in a harmonic potential at a positive temperature. The system is analyzed in a combination of a thermodynamic and a Gross–Pitaevskii (GP) limit where the trap frequency ω, the temperature T, and the particle number N are related by N∼ (T/ ω) 3→ ∞ while the scattering length is so small that the interaction energy per particle around the center of the trap is of the same order of magnitude as the spectral gap in the trap. We prove that the difference between the canonical free energy of the interacting gas and the one of the noninteracting system can be obtained by minimizing the GP energy functional. We also prove Bose–Einstein condensation in the following sense: The one-particle density matrix of any approximate minimizer of the canonical free energy functional is to leading order given by that of the noninteracting gas but with the free condensate wavefunction replaced by the GP minimizer.}, author = {Deuchert, Andreas and Seiringer, Robert and Yngvason, Jakob}, journal = {Communications in Mathematical Physics}, number = {2}, pages = {723--776}, publisher = {Springer}, title = {{Bose–Einstein condensation in a dilute, trapped gas at positive temperature}}, doi = {10.1007/s00220-018-3239-0}, volume = {368}, year = {2019}, } @inproceedings{8175, abstract = {We study edge asymptotics of poissonized Plancherel-type measures on skew Young diagrams (integer partitions). These measures can be seen as generalizations of those studied by Baik--Deift--Johansson and Baik--Rains in resolving Ulam's problem on longest increasing subsequences of random permutations and the last passage percolation (corner growth) discrete versions thereof. Moreover they interpolate between said measures and the uniform measure on partitions. In the new KPZ-like 1/3 exponent edge scaling limit with logarithmic corrections, we find new probability distributions generalizing the classical Tracy--Widom GUE, GOE and GSE distributions from the theory of random matrices.}, author = {Betea, Dan and Bouttier, Jérémie and Nejjar, Peter and Vuletíc, Mirjana}, booktitle = {Proceedings on the 31st International Conference on Formal Power Series and Algebraic Combinatorics}, location = {Ljubljana, Slovenia}, publisher = {Formal Power Series and Algebraic Combinatorics}, title = {{New edge asymptotics of skew Young diagrams via free boundaries}}, year = {2019}, } @unpublished{8182, abstract = {Suppose that $n\neq p^k$ and $n\neq 2p^k$ for all $k$ and all primes $p$. We prove that for any Hausdorff compactum $X$ with a free action of the symmetric group $\mathfrak S_n$ there exists an $\mathfrak S_n$-equivariant map $X \to {\mathbb R}^n$ whose image avoids the diagonal $\{(x,x\dots,x)\in {\mathbb R}^n|x\in {\mathbb R}\}$. Previously, the special cases of this statement for certain $X$ were usually proved using the equivartiant obstruction theory. Such calculations are difficult and may become infeasible past the first (primary) obstruction. We take a different approach which allows us to prove the vanishing of all obstructions simultaneously. The essential step in the proof is classifying the possible degrees of $\mathfrak S_n$-equivariant maps from the boundary $\partial\Delta^{n-1}$ of $(n-1)$-simplex to itself. Existence of equivariant maps between spaces is important for many questions arising from discrete mathematics and geometry, such as Kneser's conjecture, the Square Peg conjecture, the Splitting Necklace problem, and the Topological Tverberg conjecture, etc. We demonstrate the utility of our result applying it to one such question, a specific instance of envy-free division problem.}, author = {Avvakumov, Sergey and Kudrya, Sergey}, booktitle = {arXiv}, title = {{Vanishing of all equivariant obstructions and the mapping degree}}, doi = {10.48550/arXiv.1910.12628}, year = {2019}, } @unpublished{8184, abstract = {Denote by ∆N the N-dimensional simplex. A map f : ∆N → Rd is an almost r-embedding if fσ1∩. . .∩fσr = ∅ whenever σ1, . . . , σr are pairwise disjoint faces. A counterexample to the topological Tverberg conjecture asserts that if r is not a prime power and d ≥ 2r + 1, then there is an almost r-embedding ∆(d+1)(r−1) → Rd. This was improved by Blagojevi´c–Frick–Ziegler using a simple construction of higher-dimensional counterexamples by taking k-fold join power of lower-dimensional ones. We improve this further (for d large compared to r): If r is not a prime power and N := (d+ 1)r−r l d + 2 r + 1 m−2, then there is an almost r-embedding ∆N → Rd. For the r-fold van Kampen–Flores conjecture we also produce counterexamples which are stronger than previously known. Our proof is based on generalizations of the Mabillard–Wagner theorem on construction of almost r-embeddings from equivariant maps, and of the Ozaydin theorem on existence of equivariant maps. }, author = {Avvakumov, Sergey and Karasev, R. and Skopenkov, A.}, booktitle = {arXiv}, title = {{Stronger counterexamples to the topological Tverberg conjecture}}, doi = {10.48550/arXiv.1908.08731}, year = {2019}, } @unpublished{8185, abstract = {In this paper we study envy-free division problems. The classical approach to some of such problems, used by David Gale, reduces to considering continuous maps of a simplex to itself and finding sufficient conditions when this map hits the center of the simplex. The mere continuity is not sufficient for such a conclusion, the usual assumption (for example, in the Knaster--Kuratowski--Mazurkiewicz and the Gale theorem) is a certain boundary condition. We follow Erel Segal-Halevi, Fr\'ed\'eric Meunier, and Shira Zerbib, and replace the boundary condition by another assumption, which has the economic meaning of possibility for a player to prefer an empty part in the segment partition problem. We solve the problem positively when $n$, the number of players that divide the segment, is a prime power, and we provide counterexamples for every $n$ which is not a prime power. We also provide counterexamples relevant to a wider class of fair or envy-free partition problems when $n$ is odd and not a prime power.}, author = {Avvakumov, Sergey and Karasev, Roman}, booktitle = {arXiv}, title = {{Envy-free division using mapping degree}}, doi = {10.48550/arXiv.1907.11183}, year = {2019}, } @inbook{8281, abstract = {We review the history of population genetics, starting with its origins a century ago from the synthesis between Mendel and Darwin's ideas, through to the recent development of sophisticated schemes of inference from sequence data, based on the coalescent. We explain the close relation between the coalescent and a diffusion process, which we illustrate by their application to understand spatial structure. We summarise the powerful methods available for analysis of multiple loci, when linkage equilibrium can be assumed, and then discuss approaches to the more challenging case, where associations between alleles require that we follow genotype, rather than allele, frequencies. Though we can hardly cover the whole of population genetics, we give an overview of the current state of the subject, and future challenges to it.}, author = {Barton, Nicholas H and Etheridge, Alison}, booktitle = {Handbook of statistical genomics}, editor = {Balding, David and Moltke, Ida and Marioni, John}, isbn = {9781119429142}, pages = {115--144}, publisher = {Wiley}, title = {{Mathematical models in population genetics}}, doi = {10.1002/9781119487845.ch4}, year = {2019}, } @unpublished{8305, abstract = {In this paper, we present the first fully asynchronous distributed key generation (ADKG) algorithm as well as the first distributed key generation algorithm that can create keys with a dual (f,2f+1)−threshold that are necessary for scalable consensus (which so far needs a trusted dealer assumption). In order to create a DKG with a dual (f,2f+1)− threshold we first answer in the affirmative the open question posed by Cachin et al. how to create an AVSS protocol with recovery thresholds f+1