title: MSPP: A Highly Efficient and Scalable Algorithm for Mining Similar Pairs of Points

abstract: The closest pair of points problem or closest pair problem (CPP) is an important problem in computational geometry where we have to find a pair of points from a set of points in metric space with the smallest distance between them. This problem arises in a number of applications, such as but not limited to clustering, graph partitioning, image processing, patterns identification, and intrusion detection. For example, in air-traffic control, we must monitor aircrafts that come too close together, since this may potentially indicate a possible collision. Numerous algorithms have been presented for solving the CPP. The algorithms that are employed in practice have a worst case quadratic run time complexity. In this article we present an elegant approximation algorithm for the CPP called MSPP: Mining Similar Pairs of Points. It is faster than currently best known algorithms while maintaining a very good accuracy. The proposed algorithm also detects a set of closely similar pairs of points in Euclidean and Pearson metric spaces and can be adapted in numerous real world applications, such as clustering, dimension reduction, constructing and analyzing gene/transcript co-expression network, among others.


title: Neural Architecture Search as Sparse Supernet

abstract: This paper aims at enlarging the problem of Neural Architecture Search (NAS) from Single-Path and Multi-Path Search to automated Mixed-Path Search. In particular, we model the NAS problem as a sparse supernet using a new continuous architecture representation with a mixture of sparsity constraints. The sparse supernet enables us to automatically achieve sparsely-mixed paths upon a compact set of nodes. To optimize the proposed sparse supernet, we exploit a hierarchical accelerated proximal gradient algorithm within a bi-level optimization framework. Extensive experiments on Convolutional Neural Network and Recurrent Neural Network search demonstrate that the proposed method is capable of searching for compact, general and powerful neural architectures.


title: Nucleon Gluon Distribution Function from 2+1+1-Flavor Lattice QCD

abstract: The parton distribution functions (PDFs) provide process-independent information about the quarks and gluons inside hadrons. Although the gluon PDF can be obtained from a global fit to experimental data, it is not constrained well in the large-$x$ region. Theoretical gluon-PDF studies are much fewer than those of the quark PDFs. In this work, we present the first lattice-QCD results that access the $x$-dependence of the gluon unpolarized PDF of the nucleon. The lattice calculation is carried out with nucleon momenta up to 2.16 GeV, lattice spacing $a\approx0.12$ fm, with valence pion masses of 310 and 690 MeV. We use reduced Ioffe-time distributions to cancel the renormalization and implement a one-loop perturbative pseudo-PDF matching to the lightcone distribution. Our matrix element results in coordinate space are consistent with those obtained from the global PDF fits of CT18 NNLO and NNPDF3.1 NNLO. Our fitted gluon PDF extrapolated to the physical pion mass gives consistent results in the $x > 0.3$ region.


title: Quasi-Interpolant Operators and the Solution of Fractional Differential Problems

abstract: Nowadays, fractional differential equations are a well established tool to model phenomena from the real world. Since the analytical solution is rarely available, there is a great effort in constructing efficient numerical methods for their solution. In this paper we are interested in solving boundary value problems having space derivative of fractional order. To this end, we present a collocation method in which the solution of the fractional problem is approximated by a spline quasi-interpolant operator. This allows us to construct the numerical solution in an easy way. We show through some numerical tests that the proposed method is efficient and accurate.


title: Fast Generation and Detection of Spatial Modes of Light using an Acousto-Optic Modulator

abstract: Spatial modes of light provide a high-dimensional space that can be used to encode both classical and quantum information. Current approaches for dynamically generating and measuring these modes are slow, due to the need to reconfigure a high-resolution phase mask such as a spatial light modulator or digital micromirror device. The process of updating the spatial mode of light can be greatly accelerated by multiplexing a set of static phase masks with a fast, image-preserving optical switch, such as an acousto-optic modulator (AOM). We experimentally realize this approach, using a double-pass AOM to generate one of five orbital angular momentum states with a switching rate of up to 500 kHz. We then apply this system to perform fast quantum state tomography of spatial modes of light in a 2-dimensional Hilbert space, by projecting the unknown state onto six spatial modes comprising three mutually unbiased bases. We are able to reconstruct arbitrary states in under 1 ms with an average fidelity of 96.9%.


title: Patterns of galaxy spin directions in SDSS and Pan-STARRS show parity violation and multipoles

abstract: The distribution of spin directions of $\sim6.4\cdot10^4$ SDSS spiral galaxies with spectra was examined, and compared to the distribution of $\sim3.3\cdot10^4$ Pan-STARRS galaxies. The analysis shows a statistically significant asymmetry between the number of SDSS galaxies with opposite spin directions, and the magnitude and direction of the asymmetry changes with the direction of observation and with the redshift. The redshift dependence shows that the distribution of the spin direction of SDSS galaxies becomes more asymmetric as the redshift gets higher. Fitting the distribution of the galaxy spin directions to a quadrupole alignment provides fitness with statistical significance >5$\sigma$, which grows to >8$\sigma$ when just galaxies with z>0.15 are used. Similar analysis with Pan-STARRS galaxies provides dipole and quadrupole alignments nearly identical to the analysis of SDSS galaxies, showing that the source of the asymmetry is not necessarily a certain unknown flaw in a specific telescope system. While these observations are clearly provocative, there is no known error that could exhibit itself in such form. The data analysis process is fully automatic, and uses deterministic and symmetric algorithms with defined rules. It does not involve either manual analysis that can lead to human perceptual bias, or machine learning that can capture human biases or other subtle differences that are difficult to identify due to the complex nature of machine learning processes. Also, an error in the galaxy annotation process is expected to show consistent bias in all parts of the sky, rather than change with the direction of observation to form a clear and definable pattern.


title: Predictability and Fairness in Social Sensing

abstract: We consider the design of distributed algorithms that govern the manner in which agents contribute to a social sensing platform. Specifically, we are interested in situations where fairness among the agents contributing to the platform is needed. A notable example are platforms operated by public bodies, where fairness is a legal requirement. The design of such distributed systems is challenging due to the fact that we wish to simultaneously realise an efficient social sensing platform, but also deliver a predefined quality of service to the agents (for example, a fair opportunity to contribute to the platform). In this paper, we introduce iterated function systems (IFS) as a tool for the design and analysis of systems of this kind. We show how the IFS framework can be used to realise systems that deliver a predictable quality of service to agents, can be used to underpin contracts governing the interaction of agents with the social sensing platform, and which are efficient. To illustrate our design via a use case, we consider a large, high-density network of participating parked vehicles. When awoken by an administrative centre, this network proceeds to search for moving missing entities of interest using RFID-based techniques. We regulate which vehicles are actively searching for the moving entity of interest at any point in time. In doing so, we seek to equalise vehicular energy consumption across the network. This is illustrated through simulations of a search for a missing Alzheimer's patient in Melbourne, Australia. Experimental results are presented to illustrate the efficacy of our system and the predictability of access of agents to the platform independent of initial conditions.


title: Physical Adversarial Attack on Vehicle Detector in the Carla Simulator

abstract: In this paper, we tackle the issue of physical adversarial examples for object detectors in the wild. Specifically, we proposed to generate adversarial patterns to be applied on vehicle surface so that it's not recognizable by detectors in the photo-realistic Carla simulator. Our approach contains two main techniques, an Enlarge-and-Repeat process and a Discrete Searching method, to craft mosaic-like adversarial vehicle textures without access to neither the model weight of the detector nor a differential rendering procedure. The experimental results demonstrate the effectiveness of our approach in the simulator.


title: Lookahead and Hybrid Sample Allocation Procedures for Multiple Attribute Selection Decisions

abstract: Attributes provide critical information about the alternatives that a decision-maker is considering. When their magnitudes are uncertain, the decision-maker may be unsure about which alternative is truly the best, so measuring the attributes may help the decision-maker make a better decision. This paper considers settings in which each measurement yields one sample of one attribute for one alternative. When given a fixed number of samples to collect, the decision-maker must determine which samples to obtain, make the measurements, update prior beliefs about the attribute magnitudes, and then select an alternative. This paper presents the sample allocation problem for multiple attribute selection decisions and proposes two sequential, lookahead procedures for the case in which discrete distributions are used to model the uncertain attribute magnitudes. The two procedures are similar but reflect different quality measures (and loss functions), which motivate different decision rules: (1) select the alternative with the greatest expected utility and (2) select the alternative that is most likely to be the truly best alternative. We conducted a simulation study to evaluate the performance of the sequential procedures and hybrid procedures that first allocate some samples using a uniform allocation procedure and then use the sequential, lookahead procedure. The results indicate that the hybrid procedures are effective; allocating many (but not all) of the initial samples with the uniform allocation procedure not only reduces overall computational effort but also selects alternatives that have lower average opportunity cost and are more often truly best.


title: Reciprocal Recommender Systems: Analysis of State-of-Art Literature, Challenges and Opportunities towards Social Recommendation

abstract: There exist situations of decision-making under information overload in the Internet, where people have an overwhelming number of available options to choose from, e.g. products to buy in an e-commerce site, or restaurants to visit in a large city. Recommender systems arose as a data-driven personalized decision support tool to assist users in these situations: they are able to process user-related data, filtering and recommending items based on the users preferences, needs and/or behaviour. Unlike most conventional recommender approaches where items are inanimate entities recommended to the users and success is solely determined upon the end users reaction to the recommendation(s) received, in a Reciprocal Recommender System (RRS) users become the item being recommended to other users. Hence, both the end user and the user being recommended should accept the 'matching' recommendation to yield a successful RRS performance. The operation of an RRS entails not only predicting accurate preference estimates upon user interaction data as classical recommenders do, but also calculating mutual compatibility between (pairs of) users, typically by applying fusion processes on unilateral user-to-user preference information. This paper presents a snapshot-style analysis of the extant literature that summarizes the state-of-the-art RRS research to date, focusing on the algorithms, fusion processes and fundamental characteristics of RRS, both inherited from conventional user-to-item recommendation models and those inherent to this emerging family of approaches. Representative RRS models are likewise highlighted. Following this, we discuss the challenges and opportunities for future research on RRSs, with special focus on (i) fusion strategies to account for reciprocity and (ii) emerging application domains related to social recommendation.


title: Reweighting of Binaural Localization Cues Induced by Lateralization Training

abstract: Normal-hearing listeners adapt to alterations in sound localization cues. This adaptation can result from the establishment of a new spatial map of the altered cues or from a stronger relative weighting of unaltered compared to altered cues. Such reweighting has been shown for monaural vs. binaural cues. However, studies attempting to reweight the two binaural cues, interaural differences in time and level, yielded inconclusive results. In this study we investigated whether binaural cue reweighting can be induced by a lateralization training in a virtual audio-visual environment. 20 normal-hearing participants, divided into two groups, completed the experiment consisting of a seven-day lateralization training in a virtual audio-visual environment, preceded and followed by a test measuring the binaural cue weights. During testing, the participants task was to lateralize 500-ms bandpass-filtered (2-4 kHz) noise bursts containing various combinations of spatially consistent and inconsistent ITDs and ILDs. During training, the task was extended by visual cues reinforcing ITDs in one group and ILDs in the other group as well as manipulating the azimuthal ranges of the two cues. In both groups, the weight given to the reinforced cue increased significantly from pre- to posttest, suggesting that participants reweighted the binaural cues in the expected direction. This reweighting occurred predominantly within the first training session. The present results are relevant as binaural cue reweighting is, for example, likely to occur when normal-hearing listeners adapt to new acoustic environments. Similarly, binaural cue reweighting might be a factor underlying the low contribution of ITDs to sound localization of cochlear-implant listeners as they typically do not experience reliable ITD cues with their clinical devices.


title: COLD: Towards the Next Generation of Pre-Ranking System

abstract: Multi-stage cascade architecture exists widely in many industrial systems such as recommender systems and online advertising, which often consists of sequential modules including matching, pre-ranking, ranking, etc. For a long time, it is believed pre-ranking is just a simplified version of the ranking module, considering the larger size of the candidate set to be ranked. Thus, efforts are made mostly on simplifying ranking model to handle the explosion of computing power for online inference. In this paper, we rethink the challenge of the pre-ranking system from an algorithm-system co-design view. Instead of saving computing power with restriction of model architecture which causes loss of model performance, here we design a new pre-ranking system by joint optimization of both the pre-ranking model and the computing power it costs. We name it COLD (Computing power cost-aware Online and Lightweight Deep pre-ranking system). COLD beats SOTA in three folds: (i) an arbitrary deep model with cross features can be applied in COLD under a constraint of controllable computing power cost. (ii) computing power cost is explicitly reduced by applying optimization tricks for inference acceleration. This further brings space for COLD to apply more complex deep models to reach better performance. (iii) COLD model works in an online learning and severing manner, bringing it excellent ability to handle the challenge of the data distribution shift. Meanwhile, the fully online pre-ranking system of COLD provides us with a flexible infrastructure that supports efficient new model developing and online A/B testing.Since 2019, COLD has been deployed in almost all products involving the pre-ranking module in the display advertising system in Alibaba, bringing significant improvements.


title: On Package Freshness in Linux Distributions

abstract: The open-source Linux operating system is available through a wide variety of distributions, each containing a collection of installable software packages. It can be important to keep these packages as fresh as possible to benefit from new features, bug fixes and security patches. However, not all distributions place the same emphasis on package freshness. We conducted a survey in the first half of 2020 with 170 Linux users to gauge their perception of package freshness in the distributions they use, the value they place on package freshness and the reasons why they do so, and the methods they use to update packages. The results of this survey reveal that, for the aforementioned reasons, keeping packages up to date is an important concern to Linux users and that they install and update packages through their distribution's official repositories whenever possible, but often resort to third-party repositories and package managers for proprietary software and programming language libraries. Some distributions are perceived to be much quicker in deploying package updates than others. These results are valuable to assess the requirements and expectations of Linux users in terms of package freshness.


title: Exploring Image Enhancement for Salient Object Detection in Low Light Images

abstract: Low light images captured in a non-uniform illumination environment usually are degraded with the scene depth and the corresponding environment lights. This degradation results in severe object information loss in the degraded image modality, which makes the salient object detection more challenging due to low contrast property and artificial light influence. However, existing salient object detection models are developed based on the assumption that the images are captured under a sufficient brightness environment, which is impractical in real-world scenarios. In this work, we propose an image enhancement approach to facilitate the salient object detection in low light images. The proposed model directly embeds the physical lighting model into the deep neural network to describe the degradation of low light images, in which the environment light is treated as a point-wise variate and changes with local content. Moreover, a Non-Local-Block Layer is utilized to capture the difference of local content of an object against its local neighborhood favoring regions. To quantitative evaluation, we construct a low light Images dataset with pixel-level human-labeled ground-truth annotations and report promising results on four public datasets and our benchmark dataset.


title: Automatic Gain Control Design for Dynamic Visible Light Communication Systems

abstract: For dynamic visible light communication (VLC) systems, received optical power fluctuates largely due to the fast movement of VLC terminals. Such fluctuations will cause possible signal clipping and quantization noise at the analog-to-digital converters (ADCs) and thus aggravate signal-to-noise ratio (SNR) and reliability of the communication link. To mitigate this effect, the automatic gain control (AGC) technique is often introduced in the receiver front-end to adaptively adjust the electrical signal strength. In this paper, we provided a VLC front-end analysis considering AGC model. Based on the model, some design principles of AGC are theoretically derivated: the effects of AGC index $m$, AGC maximum gain $g_{max}$ and AGC equilibrium range $DR$. Next, an analog AGC amplifier was carefully implemented and the effectiveness of our AGC modeling was proved through BER experiments. Finally, realtime 25Mb/s on-off-keying (OOK) experiments with AGC function were demonstrated in a dynamic link with different speeds. Experimental results show that the AGC can stabilize the BER performance and improve the system performance in the speed of 1m/s.


title: Functional Tucker approximation using Chebyshev interpolation

abstract: This work is concerned with approximating a trivariate function defined on a tensor-product domain via function evaluations. Combining tensorized Chebyshev interpolation with a Tucker decomposition of low multilinear rank yields function approximations that can be computed and stored very efficiently. The existing Chebfun3 algorithm [Hashemi and Trefethen, SIAM J. Sci. Comput., 39 (2017)]uses a similar format but the construction of the approximation proceeds indirectly, via a so called slice-Tucker decomposition. As a consequence, Chebfun3 sometimes uses unnecessarily many function evaluations and does not fully benefit from the potential of the Tucker decomposition to reduce, sometimes dramatically, the computational cost. We propose a novel algorithm Chebfun3F that utilizes univariate fibers instead of bivariate slices to construct the Tucker decomposition. Chebfun3F reduces the cost for the approximation in terms of the number of function evaluations for nearly all functions considered, typically by 75%, and sometimes by over 98%.


title: Robust Benchmarking for Machine Learning of Clinical Entity Extraction

abstract: Clinical studies often require understanding elements of a patient's narrative that exist only in free text clinical notes. To transform notes into structured data for downstream use, these elements are commonly extracted and normalized to medical vocabularies. In this work, we audit the performance of and indicate areas of improvement for state-of-the-art systems. We find that high task accuracies for clinical entity normalization systems on the 2019 n2c2 Shared Task are misleading, and underlying performance is still brittle. Normalization accuracy is high for common concepts (95.3%), but much lower for concepts unseen in training data (69.3%). We demonstrate that current approaches are hindered in part by inconsistencies in medical vocabularies, limitations of existing labeling schemas, and narrow evaluation techniques. We reformulate the annotation framework for clinical entity extraction to factor in these issues to allow for robust end-to-end system benchmarking. We evaluate concordance of annotations from our new framework between two annotators and achieve a Jaccard similarity of 0.73 for entity recognition and an agreement of 0.83 for entity normalization. We propose a path forward to address the demonstrated need for the creation of a reference standard to spur method development in entity recognition and normalization.


title: Quantum criticality and excitations of a long-range anisotropic $XY$-chain in a transverse field

abstract: The critical breakdown of a one-dimensional quantum magnet with long-range interactions is studied by investigating the high-field polarized phase of the anisotropic XY model in a transverse field for the ferro- and antiferromagnetic case. While for the limiting case of the isotropic long-range XY model we can extract the elementary one quasi-particle dispersion analytically and calculate two quasi-particle excitation energies quantitatively in a numerical fashion, for the long-range Ising limit as well as in the intermediate regime we use perturbative continuous unitary transformations on white graphs in combination with classical Monte Carlo simulations for the graph embedding to extract high-order series expansions in the thermodynamic limit. This enables us to determine the quantum-critical breakdown of the high-field polarized phase by analyzing the gap-closing including associated critical exponents and multiplicative logarithmic corrections. In addition, for the ferromagnetic isotropic XY model we determined the critical exponents $z$ and $\nu$ analytically by a bosonic quantum-field theory.


title: Sensitivity of the Cherenkov Telescope Array to a dark matter signal from the Galactic centre

abstract: We provide an updated assessment of the power of the Cherenkov Telescope Array (CTA) to search for thermally produced dark matter at the TeV scale, via the associated gamma-ray signal from pair-annihilating dark matter particles in the region around the Galactic centre. We find that CTA will open a new window of discovery potential, significantly extending the range of robustly testable models given a standard cuspy profile of the dark matter density distribution. Importantly, even for a cored profile, the projected sensitivity of CTA will be sufficient to probe various well-motivated models of thermally produced dark matter at the TeV scale. This is due to CTA's unprecedented sensitivity, angular and energy resolutions, and the planned observational strategy. The survey of the inner Galaxy will cover a much larger region than corresponding previous observational campaigns with imaging atmospheric Cherenkov telescopes. CTA will map with unprecedented precision the large-scale diffuse emission in high-energy gamma rays, constituting a background for dark matter searches for which we adopt state-of-the-art models based on current data. Throughout our analysis, we use up-to-date event reconstruction Monte Carlo tools developed by the CTA consortium, and pay special attention to quantifying the level of instrumental systematic uncertainties, as well as background template systematic errors, required to probe thermally produced dark matter at these energies. "Full likelihood tables complementing our analysis are provided here [ https://doi.org/10.5281/zenodo.4057987 ]"


title: Quantum monitoring the metabolism of individual yeast mutant strain cells when aged, stressed or treated with antioxidant

abstract: Free radicals play a key role in the ageing process. The strongly debated free radical theory of ageing even states that damage caused by free radicals is the main cause of aging on a cellular level. However, free radicals are small, reactive and short lived and thus challenging to measure. We utilize a new technique called diamond magnetometry for this purpose. We make use of nitrogen vacancy centers in nanodiamonds. Via a quantum effect these defects convert a magnetic resonance signal into an optical signal. While this method is increasingly popular for its unprecedented sensitivity in physics, we use this technique here for the first time to measure free radicals in living cells. Our signals are equivalent to T1 signals in conventional MRI but from nanoscale voxels from single cells with sub-cellular resolution. With this powerful tool we are able to follow free radical generation after chemically inducing stress. In addition, we can observe free radical reduction in presence of an antioxidant. We were able to clearly differentiate between mutant strains with altered metabolism. Finally, the excellent stability of our diamond particles allowed us to follow the ageing process and differentiate between young and old cells. We could confirm the expected increase of free radical load in old wild type and sod1{\Delta} mutants. We further applied this new technique to investigate tor1{\Delta} and pex19{\Delta} cells. For these mutants an increased lifespan has been reported but the exact mechanism is unclear. We find a decreased free radical load in, which might offer an explanation for the increased lifespan in these cells.


title: Covariant Formulation of Non-linear Langevin Theory with Multiplicative Gaussian White Noises

abstract: The multi-dimensional non-linear Langevin equation with multiplicative Gaussian white noises in Ito's sense is made covariant with respect to non-linear transform of variables. The formalism involves no metric or affine connection, works for systems with or without detailed balance, and is substantially simpler than previous theories. Its relation with deterministic theory is clarified. The unitary limit and Hermitian limit of the theory are examined. Some implications on the choices of stochastic calculus are also discussed.


title: Bell polynomials in the series expansions of the Ising model

abstract: Through applying Bell polynomials to the integral representation of the free energy of the Ising model for the triangular and hexagonal lattices we obtain the exact combinatorial formulas for the number of spin configurations at a given energy (i.e. low-temperature series expansion of the partition function or, alternatively, the number of states). We also generalize this approach to the wider class of the (chequered) Utiyama graphs. Apart from the presented exact formulas, our technique allows one to establish the correspondence between the perfect gas of clusters and the Ising model on the lattices which have positive coefficients in the low-temperature expansion (e.g. square lattice, hexagonal lattice). However it is not always the case -- we present that for the triangular lattice the coefficients could be negative and the perfect gas of clusters interpretation is problematic.


title: Computer-aided Tumor Diagnosis in Automated Breast Ultrasound using 3D Detection Network

abstract: Automated breast ultrasound (ABUS) is a new and promising imaging modality for breast cancer detection and diagnosis, which could provide intuitive 3D information and coronal plane information with great diagnostic value. However, manually screening and diagnosing tumors from ABUS images is very time-consuming and overlooks of abnormalities may happen. In this study, we propose a novel two-stage 3D detection network for locating suspected lesion areas and further classifying lesions as benign or malignant tumors. Specifically, we propose a 3D detection network rather than frequently-used segmentation network to locate lesions in ABUS images, thus our network can make full use of the spatial context information in ABUS images. A novel similarity loss is designed to effectively distinguish lesions from background. Then a classification network is employed to identify the located lesions as benign or malignant. An IoU-balanced classification loss is adopted to improve the correlation between classification and localization task. The efficacy of our network is verified from a collected dataset of 418 patients with 145 benign tumors and 273 malignant tumors. Experiments show our network attains a sensitivity of 97.66% with 1.23 false positives (FPs), and has an area under the curve(AUC) value of 0.8720.


title: Numerical Analysis of Backward Subdiffusion Problems

abstract: The aim of this paper is to develop and analyze numerical schemes for approximately solving the backward problem of subdiffusion equation involving a fractional derivative in time with order $\alpha\in(0,1)$. After using quasi-boundary value method to regularize the "mildly" ill-posed problem, we propose a fully discrete scheme by applying finite element method (FEM) in space and convolution quadrature (CQ) in time. We provide a thorough error analysis of the resulting discrete system in both cases of smooth and nonsmooth data. The analysis relies heavily on smoothing properties of (discrete) solution operators, and nonstandard error estimate for the direct problem in terms of problem data regularity. The theoretical results are useful to balance discretization parameters, regularization parameter and noise level. Numerical examples are presented to illustrate the theoretical results.


title: Improved Time Warp Edit Distance -- A Parallel Dynamic Program in Linear Memory

abstract: Edit Distance is a classic family of dynamic programming problems, among which Time Warp Edit Distance refines the problem with the notion of a metric and temporal elasticity. A novel Improved Time Warp Edit Distance algorithm that is both massively parallelizable and requiring only linear storage is presented. This method uses the procession of a three diagonal band to cover the original dynamic program space. Every element of the diagonal update can be computed in parallel. The core method is a feature of the TWED Longest Common Subsequence data dependence and is applicable to dynamic programs that share similar band subproblem structure. The algorithm has been implemented as a CUDA C library with Python bindings. Speedups for challenging problems are phenomenal.


title: Reconstructing Network Structures from Partial Measurements

abstract: The dynamics of systems of interacting agents is determined by the structure of their coupling network. The knowledge of the latter is, therefore, highly desirable, for instance, to develop efficient control schemes, to accurately predict the dynamics, or to better understand inter-agent processes. In many important and interesting situations, the network structure is not known, however, and previous investigations have shown how it may be inferred from complete measurement time series on each and every agent. These methods implicitly presuppose that, even though the network is not known, all its nodes are. Here, we investigate the different problem of inferring network structures within the observed/measured agents. For symmetrically coupled dynamical systems close to a stable equilibrium, we establish analytically and illustrate numerically that velocity signal correlators encode not only direct couplings, but also geodesic distances in the coupling network within the subset of measurable agents. When dynamical data are accessible for all agents, our method is furthermore algorithmically more efficient than the traditional ones because it does not rely on matrix inversion.


title: Continuous Adaptive Cross Approximation for Ill-posed Problems with Chebfun

abstract: The analysis of linear ill-posed problems often is carried out in function spaces using tools from functional analysis. However, the numerical solution of these problems typically is computed by first discretizing the problem and then applying tools from (finite-dimensional) linear algebra. The present paper explores the feasibility of applying the Chebfun package to solve ill-posed problems. This approach allows a user to work with functions instead of matrices. The solution process therefore is much closer to the analysis of ill-posed problems than standard linear algebra-based solution methods.


title: A Compositional Model of Consciousness based on Consciousness-Only

abstract: Scientific studies of consciousness rely on objects whose existence is assumed to be independent of any consciousness. On the contrary, we assume consciousness to be fundamental, and that one of the main features of consciousness is characterized as being other-dependent. We set up a framework which naturally subsumes this feature by defining a compact closed category where morphisms represent conscious processes. These morphisms are a composition of a set of generators, each being specified by their relations with other generators, and therefore co-dependent. The framework is general enough and fits well into a compositional model of consciousness. Interestingly, we also show how our proposal may become a step towards avoiding the hard problem of consciousness, and thereby address the combination problem of conscious experiences.


title: Scattering theory for Dirac fields inside a Reissner-Nordstr\"om-type black hole

abstract: We show asymptotic completeness for the massive charged Dirac equation between the black hole and Cauchy horizons of a sub-extremal ((Anti-) De Sitter) Reissner-Nordstr\"om black hole.


title: Chaotic dynamics in a simple predator-prey model with discrete delay

abstract: A discrete delay is included to model the time between the capture of the prey and its conversion to viable biomass in the simplest classical Gause type predator-prey model that has equilibrium dynamics without delay. As the delay increases from zero, the coexistence equilibrium undergoes a supercritical Hopf bifurcation, two saddle-node bifurcations of limit cycles, and a cascade of period doublings, eventu1ally leading to chaos. The resulting periodic orbits and the strange attractor resemble their counterparts for the Mackey-Glass equation. Due to the global stability of the system without delay, these complicated dynamics can be solely attributed to the introduction of the delay. Since many models include predator-prey like interactions as submodels, this study emphasizes the importance of understanding the implications of overlooking delay in such models on the reliability of the model-based predictions, especially since the temperature is known to have an effect on the length of certain delays.


title: Linear stability of Israel-Stewart theory in the presence of net-charge diffusion

abstract: In this paper, we perform a linear stability analysis of Israel-Stewart theory around a global equilibrium state, including the effects of shear-stress tensor, net-baryon diffusion current and diffusion-viscous coupling. We find all the relevant modes of this theory and derive necessary conditions that these modes must satisfy in order to be stable and subluminal. With these conditions, we then derive constraints for the shear and diffusion relaxation times and the transport coefficients related to diffusion-viscous coupling.


title: Two-phase crystallisation in a carpet of inertial spinners

abstract: We study the dynamics of torque driven spherical spinners settled on a surface, and demonstrate that hydrodynamic interactions at finite Reynolds numbers can lead to a concentration dependent and non-uniform crystallisation. At semi-dilute concentrations, we observe a rapid formation of a uniform hexagonal structure in the spinner monolayer. We attribute this to repulsive hydrodynamic interactions created by the secondary flow of the spinning particles. Increasing the surface coverage leads to a state with two co-existing spinner densities. The uniform hexagonal structure deviates into a high density crystalline structure surrounded by a continuous lower density hexatically ordered state. We show that this phase separation occurs due to a non-monotonic hydrodynamic repulsion, arising from a concentration dependent spinning frequency.


title: The nature of point source fringes in mid-infrared spectra acquired with the James Webb Space Telescope

abstract: The constructive and destructive interference in different layers of the James Webb Space Telescope (JWST) Mid-Infrared Instrument (MIRI) detector arrays modulate the detected signal as a function of wavelength. Additionally, sources of different spatial profiles show different fringe patterns. Dividing by a static fringe flat could hamper the scientific interpretation of sources whose fringes do not match that of the fringe flat. We find point source fringes measured by the MIRI Medium-Resolution Spectrometer (MRS) to be reproducible under similar observing conditions. We want, thus, to identify the variables, if they exist, that would allow for a parametrization of the signal variations induced by point source fringe modulations. We do this by analyzing MRS detector plane images acquired on the ground. We extracted the fringe profile of multiple point source observations and studied the amplitude and phase of the fringes as a function of field position and pixel sampling of the point spread function of the optical chain. A systematic variation in the amplitude and phase of the point source fringes is found over the wavelength range covered by the test sources (4.9-5.8 $\mu$m). The variation depends on the fraction of the point spread function seen by the detector pixel. We identify the non-uniform pixel illumination as the root cause of the reported systematic variation. We report an improvement after correction of 50% on the 1$\sigma$ standard deviation of the spectral continuum. A 50% improvement is also reported in line sensitivity for a benchmark test with a spectral continuum of 100 mJy. The improvement in the shape of weak lines is illustrated using a T Tauri model spectrum. Consequently, we verify that fringes of extended sources and potentially semi-extended sources and crowded fields can be simulated by combining multiple point source fringe transmissions.


title: On the Two-Dimensional Knapsack Problem for Convex Polygons

abstract: We study the two-dimensional geometric knapsack problem for convex polygons. Given a set of weighted convex polygons and a square knapsack, the goal is to select the most profitable subset of the given polygons that fits non-overlappingly into the knapsack. We allow to rotate the polygons by arbitrary angles. We present a quasi-polynomial time $O(1)$-approximation algorithm for the general case and a polynomial time $O(1)$-approximation algorithm if all input polygons are triangles, both assuming polynomially bounded integral input data. Also, we give a quasi-polynomial time algorithm that computes a solution of optimal weight under resource augmentation, i.e., we allow to increase the size of the knapsack by a factor of $1+\delta$ for some $\delta>0$ but compare ourselves with the optimal solution for the original knapsack. To the best of our knowledge, these are the first results for two-dimensional geometric knapsack in which the input objects are more general than axis-parallel rectangles or circles and in which the input polygons can be rotated by arbitrary angles.


title: Informationally restricted correlations: a general framework for classical and quantum systems

abstract: We introduce new methods and tools to study and characterise classical and quantum correlations emerging from prepare-and-measure experiments with informationally restricted communication. We consider the most general kind of informationally restricted correlations, namely the ones formed when the sender is allowed to prepare statistical mixtures of mixed states, showing that contrary to what happens in Bell nonlocality, mixed states can outperform pure ones. We then leverage these tools to derive device-independent witnesses of the information content of quantum communication, witnesses for different quantum information resources, and demonstrate that these methods can be used to develop a new avenue for semi-device independent random number generators.


title: Device-independent quantum key distribution with asymmetric CHSH inequalities

abstract: The simplest device-independent quantum key distribution protocol is based on the Clauser-Horne-Shimony-Holt (CHSH) Bell inequality and allows two users, Alice and Bob, to generate a secret key if they observe sufficiently strong correlations. There is, however, a mismatch between the protocol, in which only one of Alice's measurements is used to generate the key, and the CHSH expression, which is symmetric with respect to Alice's two measurements. We therefore investigate the impact of using an extended family of Bell expressions where we give different weights to Alice's measurements. Using this family of asymmetric Bell expressions improves the robustness of the key distribution protocol for certain experimentally-relevant correlations. As an example, the tolerable error rate improves from 7.15% to about 7.42% for the depolarising channel. Adding random noise to Alice's key before the postprocessing pushes the threshold further to more than 8.34%. The main technical result of our work is a tight bound on the von Neumann entropy of one of Alice's measurement outcomes conditioned on a quantum eavesdropper for the family of asymmetric CHSH expressions we consider and allowing for an arbitrary amount of noise preprocessing.


title: Computer and Network Security

abstract: In the era of Internet of Things and with the explosive worldwide growth of electronic data volume, and associated need of processing, analysis and storage of such humongous volume of data, several new challenges are faced in protecting privacy of sensitive data and securing systems by designing novel schemes for secure authentication, integrity protection, encryption and non-repudiation. Lightweight symmetric key cryptography and adaptive network security algorithms are in demand for mitigating these challenges. This book presents some of the state-of-the-art research work in the field of cryptography and security in computing and communications. It is a valuable source of knowledge for researchers, engineers, practitioners, graduate and doctoral students who are working in the field of cryptography, network security and security and privacy issues in the Internet of Things (IoT), and machine learning application in security. It will also be useful for faculty members of graduate schools and universities.


title: Realization of tropical curves in abelian surfaces

abstract: We construct algebraic curves in abelian surfaces starting from tropical curves in real tori. We give a necessary and sufficient condition for a tropical curve in a real torus to be realizable by an algebraic curve in an abelian surface. When the condition is satisfied, the number of algebraic curves can be computed by a combinatorial formula. This gives us an algebraic-tropical correspondence theorem for abelian surfaces analogous to Mikhalkin's correspondence theorem for toric surfaces. In other words, the number of algebraic curves passing through generic points in an abelian surface can be computed purely combinatorially via tropical curves.


title: HMCNAS: Neural Architecture Search using Hidden Markov Chains and Bayesian Optimization

abstract: Neural Architecture Search has achieved state-of-the-art performance in a variety of tasks, out-performing human-designed networks. However, many assumptions, that require human definition, related with the problems being solved or the models generated are still needed: final model architectures, number of layers to be sampled, forced operations, small search spaces, which ultimately contributes to having models with higher performances at the cost of inducing bias into the system. In this paper, we propose HMCNAS, which is composed of two novel components: i) a method that leverages information about human-designed models to autonomously generate a complex search space, and ii) an Evolutionary Algorithm with Bayesian Optimization that is capable of generating competitive CNNs from scratch, without relying on human-defined parameters or small search spaces. The experimental results show that the proposed approach results in competitive architectures obtained in a very short time. HMCNAS provides a step towards generalizing NAS, by providing a way to create competitive models, without requiring any human knowledge about the specific task.


title: Network connectivity optimization: An evaluation of heuristics applied to complex networks and a transportation case study

abstract: Network optimization has generally been focused on solving network flow problems, but recently there have been investigations into optimizing network characteristics. Optimizing network connectivity to maximize the number of nodes within a given distance to a focal node and then minimizing the number and length of additional connections has not been as thoroughly explored, yet is important in several domains including transportation planning, telecommunications networks, and geospatial analysis. We compare several heuristics to explore this network connectivity optimization problem with the use of random networks, including the introduction of two planar random networks that are useful for spatial network simulation research, and a real-world case study from urban planning and public health. We observe significant variation between nodal characteristics and optimal connections across network types. This result along with the computational costs of the search for optimal solutions highlights the difficulty of finding effective heuristics. A novel genetic algorithm is proposed and we find this optimization heuristic outperforms existing techniques and describe how it can be applied to other combinatorial and dynamic problems.


title: Optimal periodic closure for minimizing risk in emerging disease outbreaks

abstract: Without vaccines and treatments, societies must rely on non-pharmaceutical intervention strategies to control the spread of emerging diseases such as COVID-19. Though complete lockdown is epidemiologically effective, because it eliminates infectious contacts, it comes with significant costs. Several recent studies have suggested that a plausible compromise strategy for minimizing epidemic risk is periodic closure, in which populations oscillate between wide-spread social restrictions and relaxation. However, no underlying theory has been proposed to predict and explain optimal closure periods as a function of epidemiological and social parameters. In this work we develop such an analytical theory for SEIR-like model diseases, showing how characteristic closure periods emerge that minimize the total outbreak, and increase predictably with the reproductive number and incubation periods of a disease, as long as both are within predictable limits. Using our approach we demonstrate a sweet-spot effect in which optimal periodic closure is maximally effective for diseases with similar incubation and recovery periods. Our results compare well to numerical simulations, including in COVID-19 models where infectivity and recovery show significant variability.


title: Paying Per-label Attention for Multi-label Extraction from Radiology Reports

abstract: Training medical image analysis models requires large amounts of expertly annotated data which is time-consuming and expensive to obtain. Images are often accompanied by free-text radiology reports which are a rich source of information. In this paper, we tackle the automated extraction of structured labels from head CT reports for imaging of suspected stroke patients, using deep learning. Firstly, we propose a set of 31 labels which correspond to radiographic findings (e.g. hyperdensity) and clinical impressions (e.g. haemorrhage) related to neurological abnormalities. Secondly, inspired by previous work, we extend existing state-of-the-art neural network models with a label-dependent attention mechanism. Using this mechanism and simple synthetic data augmentation, we are able to robustly extract many labels with a single model, classified according to the radiologist's reporting (positive, uncertain, negative). This approach can be used in further research to effectively extract many labels from medical text.


title: Euclid: Forecast constraints on the cosmic distance duality relation with complementary external probes

abstract: In metric theories of gravity with photon number conservation, the luminosity and angular diameter distances are related via the Etherington relation, also known as the distance-duality relation (DDR). A violation of this relation would rule out the standard cosmological paradigm and point at the presence of new physics. We quantify the ability of Euclid, in combination with contemporary surveys, to improve the current constraints on deviations from the DDR in the redshift range $0<z<1.6$. We start by an analysis of the latest available data, improving previously reported constraints by a factor of 2.5. We then present a detailed analysis of simulated Euclid and external data products, using both standard parametric methods (relying on phenomenological descriptions of possible DDR violations) and a machine learning reconstruction using Genetic Algorithms. We find that for parametric methods Euclid can (in combination with external probes) improve current constraints by approximately a factor of six, while for non-parametric methods Euclid can improve current constraints by a factor of three. Our results highlight the importance of surveys like Euclid in accurately testing the pillars of the current cosmological paradigm and constraining physics beyond the standard cosmological model.


title: Role of hyperfine interaction in Land\'{e} $g$-factors of $^3\!P^o_0$ clock states

abstract: In the weak-magnetic-field approximation, we derived a general expression of hyperfine-induced Land\'{e} $g$-factors. By using this formula and the multi-configuration Dirac-Hartree-Fock theory, the $g$-factors were calculated for the $3s3p~^3\!P^o_0$ clock state in $^{27}$Al$^+$ and $5s5p~^3\!P^o_0$ in $^{87}$Sr. The present results, $\delta g^{(1)}_{\rm hfs}(^3\!P^o_0) = -1.183(6) \times 10^{-3}$ for $^{27}$Al$^+$ and $\delta g^{(1)}_{\rm hfs}(^3\!P^o_0) = 7.78(30) \times 10^{-5}$ for $^{87}$Sr agree with experimental values very well. Our theory is also useful to predict hyperfine-induced Land\'e $g$-factors for other atomic systems.


title: Renormalization groupoids in algebraic topology

abstract: Continuing work begin in arXiv:1910.12609, we interpret the Hurewicz homomorphism for Baker and Richter's noncommutative complex cobordism spectrum $M\xi$ in terms of characteristic numbers (indexed by quasi-symmetric functions) for complex-oriented quasitoric manifolds, and show that automorphisms or cohomology operations on this representation are defined by a `renormalization' Hopf algebra of formal diffeomorphisms at the origin of the noncommutative line, previously considered (over $Q$) in quantum electrodynamics. The resulting structure can be presented in purely algebraic terms, as a groupoid scheme over $Z$ defined by a coaction of this Hopf algebra on the ring of noncommutative symmetric functions. We sketch some applications to symplectic toric manifolds, combinatorics of simplicial spheres, and statistical mechanics.


title: Structural investigation of doubly-dehydrogenated pyrene cations

abstract: The vibrationally resolved spectra of the pyrene cation and doubly-dehydrogenated pyrene cation (C$_{16}$H$_{10}$$^{.+}$; Py$^+$ and C$_{16}$H$_{8}$$^{.+}$; ddPy$^+$) are presented. Infrared predissociation spectroscopy is employed to measure the vibrational spectrum of both species using a cryogenically cooled 22-pole ion trap. The spectrum of Py$^+$ allows a detailed comparison with harmonic and anharmonic density functional theory (DFT) calculated normal mode frequencies. The spectrum of ddPy$^+$ is dominated by absorption features from two isomers (4,5-ddPy$^+$ and 1,2-ddPy$^+$) with, at most, minor contributions from other isomers. These findings can be extended to explore the release of hydrogen from interstellar PAH species. Our results suggest that this process favours the loss of adjacent hydrogen atoms.


title: Surface localization of plasmons in three dimensions and convexity

abstract: The Neumann--Poincar\'e operator defined on a smooth surface has a sequence of eigenvalues converging to zero, and the single layer potentials of the corresponding eigenfunctions, called plasmons, decay to zero, i.e., are localized on the surface, as the index of the sequence $j$ tends to infinity. We investigate quantitatively the surface localization of the plasmons in three dimensions. The results are threefold. We first prove that on smooth bounded domains of general shape the sequence of plasmons converges to zero off the boundary surface almost surely at the rate of $j^{-1/2}$. We then prove that if the domain is strictly convex, then the convergence rate becomes $j^{-\infty}$, namely, it is faster than $j^{-N}$ for any integer $N$. As a consequence, we prove that cloaking by anomalous localized resonance does not occur on three-dimensional strictly convex smooth domains. We then look into the surface localization of the plasmons on the Clifford torus by numerical computations. The Clifford torus is taken as an example of non-convex surfaces. The computational results show that the torus exhibits the spectral property completely different from strictly convex domains. In particular, they suggest that there is a subsequence of plasmons on the torus which has much slower decay than other entries of the sequence.


title: Einstein-Cartan gravity, matter, and scale-invariant generalization

abstract: We study gravity coupled to scalar and fermion fields in the Einstein-Cartan framework. We discuss the most general form of the action that contains terms of mass dimension not bigger than four, leaving out only contributions quadratic in curvature. By resolving the theory explicitly for torsion, we arrive at an equivalent metric theory containing additional six-dimensional operators. This lays the groundwork for cosmological studies of the theory. We also perform the same analysis for a no-scale scenario in which the Planck mass is eliminated at the cost of adding an extra scalar degree of freedom. Finally, we outline phenomenological implications of the resulting theories, in particular to inflation and dark matter production.


title: Non-vanishing of vector-valued Poincar\'e series

abstract: We prove a vector-valued version of Mui\'c's integral non-vanishing criterion for Poincar\'e series on the upper half-plane $ \mathcal H $. Moreover, we give an accompanying result on the construction of vector-valued modular forms in the form of Poincar\'e series. As an application of these results, we construct and study the non-vanishing of the classical and elliptic vector-valued Poincar\'e series.


title: Quantum computational advantage with string order parameters of 1D symmetry-protected topological order

abstract: Nonlocal games with advantageous quantum strategies give arguably the most fundamental demonstration of the power of quantum resources over their classical counterparts. Recently, certain multiplayer generalizations of nonlocal games have been used to prove unconditional separations between small computational complexity classes of shallow-depth circuits. Here, we show advantageous strategies for these nonlocal games for generic ground states of one-dimensional symmetry-protected topological orders (SPTOs), when a discrete invariant of a SPTO known as a twist phase is nontrivial and -1. Our construction demonstrates that sufficiently large string order parameters of such SPTOs are indicative of globally constrained correlations useful for the unconditional computational separation.


title: Coinductive proof search for polarized logic with applications to full intuitionistic propositional logic

abstract: The approach to proof search dubbed "coinductive proof search", and previously developed by the authors for implicational intuitionistic logic, is in this paper extended to LJP, a focused sequent-calculus presentation of polarized intuitionistic logic, including an array of positive and negative connectives. As before, this includes developing a coinductive description of the search space generated by a sequent, an equivalent inductive syntax describing the same space, and decision procedures for inhabitation problems in the form of predicates defined by recursion on the inductive syntax. We prove the decidability of existence of focused inhabitants, and of finiteness of the number of focused inhabitants for polarized intuitionistic logic, by means of such recursive procedures. Moreover, the polarized logic can be used as a platform from which proof search for other logics is understood. We illustrate the technique with LJT, a focused sequent calculus for full intuitionistic propositional logic (including disjunction). For that, we have to work out the "negative translation" of LJT into LJP (that sees all intuitionistic types as negative types), and verify that the translation gives a faithful representation of proof search in LJT as proof search in the polarized logic. We therefore inherit decidability of both problems studied for LJP and thus get new proofs of these results for LJT.


title: Imitative Planning using Conditional Normalizing Flow

abstract: A popular way to plan trajectories in dynamic urban scenarios for Autonomous Vehicles is to rely on explicitly specified and hand crafted cost functions, coupled with random sampling in the trajectory space to find the minimum cost trajectory. Such methods require a high number of samples to find a low-cost trajectory and might end up with a highly suboptimal trajectory given the planning time budget. We explore the application of normalizing flows for improving the performance of trajectory planning for autonomous vehicles (AVs). Our key insight is to learn a sampling policy in a low-dimensional latent space of expert-like trajectories, out of which the best sample is selected for execution. By modeling the trajectory planner's cost manifold as an energy function, we learn a scene conditioned mapping from the prior to a Boltzmann distribution over the AV control space. Finally, we demonstrate the effectiveness of our approach on real-world datasets over IL and hand-constructed trajectory sampling techniques.


title: The Stellar Population and Orbit of the Galactic Globular Cluster Palomar 3

abstract: Deep stellar photometry of one of the most distant Galactic globular clusters, Palomar 3, based on frames taken with the VLT in Johnson-Cousins broadband V and Ifilters is presented, together with medium-resolution stellar spectroscopy in the central region of the cluster obtained with the CARELEC spectrograph of the Observatoire de Haute Provence and measurements of the Lick spectral indices for the integrated spectrum. Computations of the orbital parameters of Palomar 3 and nine Galactic globular clusters with similar metallicities and ages are also presented. The orbital parameters, age, metallicity, and distance of Palomar 3 are estimated. The interstellar absorption is consistent with and supplements values from the literature. The need to obtain more accurate data on the proper motions, ages, and chemical compositions of the cluster stars to elucidate the origin of this globular cluster is emphasized.


title: Existence of Embeddings of Smooth Varieties into Linear Algebraic Groups

abstract: We prove that every smooth affine variety of dimension $d$ embeds into every simple algebraic group of dimension at least $2d+2$. We do this by establishing the existence of embeddings of smooth affine varieties into the total space of certain principal bundles. For the latter we employ and build upon parametric transversality results for flexible affine varieties due to Kaliman. By adapting a Chow-group-based argument due to Bloch, Murthy, and Szpiro, we show that our result is optimal up to a possible improvement of the bound to $2d+1$. In order to study the limits of our embedding method, we use rational homology group calculations of homogeneous spaces and we establish a domination result for rational homology of complex smooth varieties.


title: Classification of large N superconformal gauge theories with a dense spectrum

abstract: We classify the large $N$ limits of four-dimensional supersymmetric gauge theories with simple gauge groups that flow to superconformal fixed points. We restrict ourselves to the ones without a superpotential and with a fixed flavor symmetry. We find 35 classes in total, with 8 having a dense spectrum of chiral gauge-invariant operators. The central charges $a$ and $c$ for the dense theories grow linearly in $N$ in contrast to the $N^2$ growth for the theories with a sparse spectrum. The difference between the central charges $a-c$ can have both signs, and it does not vanish in the large $N$ limit for the dense theories. We find that there can be multiple bands separated by a gap, or a discrete spectrum above the band. We also find a criterion on the matter content for the fixed point theory to possess either a dense or sparse spectrum. We discover a few curious aspects regarding supersymmetric RG flows and $a$-maximization along the way. For all the theories with the dense spectrum, the AdS version of the Weak Gravity Conjecture (including the convex hull condition for the cases with multiple $U(1)$'s) holds for large enough $N$ even though they do not have weakly-coupled gravity duals.


title: Baryonic feedback measurement from KV450 cosmic shear analysis

abstract: While baryonic feedback is one of the most important astrophysical systematics that we need to address in order to achieve precision cosmology, few weak lensing studies have directly measured its impact on the matter power spectrum. We report measurement of the baryonic feedback parameter with the constraints on its lower and upper limits from cosmic shear. We use the public data from the Kilo-Degree Survey and the VISTA Kilo-Degree Infrared Galaxy Survey spanning 450 deg$^2$. Estimating both cosmological and feedback parameters simultaneously, we obtain $A_{\rm b}=1.01_{-0.85}^{+0.80}$, which shows a consistency with the dark matter-only (DMO) case at the $\sim1.2~\sigma$ level and a tendency toward positive feedback; the $A_{\rm b}=0$ ($0.81$) value corresponds to the DMO (OWLS AGN) case. Despite this full constraint of the feedback parameter, our $S_8~(\equiv \sigma_8 \sqrt{\Omega_m / 0.3})$ measurement ($0.739^{+0.036}_{- 0.035}$) shifts by only $\sim6$% of the statistical error, compared to the previous measurement. When we assume the flat $\Lambda$CDM cosmology favored by the Nine-Year Wilkinson Microwave Anisotropy Probe (Planck) result, the feedback parameter is constrained to be $A_{\rm b}=1.21_{-0.54}^{+0.61}$ ($1.60_{-0.52}^{+0.53}$), which excludes the DMO case at the $\sim2.2~\sigma$ ($\sim3.1~\sigma$) level.


title: Searching for surface defect CFTs within AdS$_3$

abstract: We study $\mathrm{AdS}_3\times S^3/\mathbb{Z}_k\times {\tilde S}^3/\mathbb{Z}_{k'}$ solutions to M-theory preserving $\mathcal{N}=(0,4)$ supersymmetries, arising as near-horizon limits of M2-M5 brane intersections ending on M5'-branes, with both types of five-branes placed on A-type singularities. Solutions in this class asymptote locally to $\mathrm{AdS}_7/\mathbb{Z}_k\times {\tilde S}^3/\mathbb{Z}_{k'}$, and can thus be interpreted as holographic duals to surface defect CFTs within the $\mathcal{N}=(1,0)$ 6d CFT dual to this solution. Upon reduction to Type IIA, we obtain a new class of solutions of the form $\mathrm{AdS}_3\times S^3/\mathbb{Z}_k\times S^2 \times \Sigma_2$ preserving (0,4) supersymmetries. We construct explicit 2d quiver CFTs dual to these solutions, describing D2-D4 surface defects embedded within the 6d (1,0) quiver CFT dual to the $\mathrm{AdS}_7/\mathbb{Z}_k$ solution to massless IIA. Finally, in the massive case, we show that the recently constructed $\mathrm{AdS}_3\times S^2\times \mathrm{CY}_2$ solutions with $\mathcal{N}=(0,4)$ supersymmetries gain a defect interpretation when $\mathrm{CY}_2=T^4$ as surface CFTs originating from D2-NS5-D6 defects embedded within the 5d CFT dual to the Brandhuber-Oz $\mathrm{AdS}_6$ background.


title: On the Relationship between Magnetic Expansion Factor and Observed Speed of the Solar Wind from Coronal Pseudostreamers

abstract: For the past 30+ years, the magnetic expansion factor ($f_s$) has been used in empirical relationships to predict solar wind speed ($v_{obs}$) at 1 AU, based on an inverse relationship between these two quantities. Coronal unipolar streamers (i.e. pseudostreamers) undergo limited field line expansion, resulting in $f_s$-dependent relationships to predict fast wind associated with these structures. However, case studies have shown that in situ observed pseudostreamer solar wind was much slower than that derived with $f_s$. To investigate this further, we conduct a statistical analysis to determine if $f_s$ and $v_{obs}$ are inversely correlated for a large sample of periods when pseudostreamer wind was observed at multiple 1 AU spacecraft (i.e. ACE, STEREO-A/B). We use the Wang-Sheeley-Arge (WSA) model driven by Air Force Data Assimilative Photospheric Flux Transport (ADAPT) photospheric field maps to identify 38 periods when spacecraft observe pseudostreamer wind. We compare the expansion factor of the last open field lines on either side of a pseudostreamer cusp with the corresponding in situ measured solar wind speed. We find only slow wind ($v_{obs}$ $<$ 500 km/s) is associated with pseudostreamers, and that there is not a significant correlation between $f_s$ and $v_{obs}$ for these field lines. This suggests that field lines near the open-closed boundary of pseudostreamers are not subject to the steady-state acceleration along continuously open flux tubes assumed in the $f_s$-$v_{obs}$ relationship. In general, dynamics at the boundary between open and closed field lines such as interchange reconnection will invalidate the steady-state assumptions of this relationship.


title: Acylindrical hyperbolicity for Artin groups of dimension 2

abstract: In this paper, we show that every irreducible $2$-dimensional Artin group $A_{\Gamma}$ of rank at least $3$ is acylindrically hyperbolic. We do this by studying the action of $A_{\Gamma}$ on its modified Deligne complex. Along the way, we prove results of independent interests on the geometry of links of this complex.


title: Diet deep generative audio models with structured lottery

abstract: Deep learning models have provided extremely successful solutions in most audio application fields. However, the high accuracy of these models comes at the expense of a tremendous computation cost. This aspect is almost always overlooked in evaluating the quality of proposed models. However, models should not be evaluated without taking into account their complexity. This aspect is especially critical in audio applications, which heavily relies on specialized embedded hardware with real-time constraints. In this paper, we build on recent observations that deep models are highly overparameterized, by studying the lottery ticket hypothesis on deep generative audio models. This hypothesis states that extremely efficient small sub-networks exist in deep models and would provide higher accuracy than larger models if trained in isolation. However, lottery tickets are found by relying on unstructured masking, which means that resulting models do not provide any gain in either disk size or inference time. Instead, we develop here a method aimed at performing structured trimming. We show that this requires to rely on global selection and introduce a specific criterion based on mutual information. First, we confirm the surprising result that smaller models provide higher accuracy than their large counterparts. We further show that we can remove up to 95% of the model weights without significant degradation in accuracy. Hence, we can obtain very light models for generative audio across popular methods such as Wavenet, SING or DDSP, that are up to 100 times smaller with commensurate accuracy. We study the theoretical bounds for embedding these models on Raspberry Pi and Arduino, and show that we can obtain generative models on CPU with equivalent quality as large GPU models. Finally, we discuss the possibility of implementing deep generative audio models on embedded platforms.


title: Reversible Debugging in Logic Programming

abstract: Reversible debugging is becoming increasingly popular for locating the source of errors. This technique proposes a more natural approach to debugging, where one can explore a computation from the observable misbehaviour backwards to the source of the error. In this work, we propose a reversible debugging scheme for logic programs. For this purpose, we define an appropriate instrumented semantics (a so-called Landauer embedding) that makes SLD resolution reversible. An implementation of a reversible debugger for Prolog, rever, has been developed and is publicly available.


title: Patterns of Patient and Caregiver Mutual Support Connections in an Online Health Community

abstract: Online health communities offer the promise of support benefits to users, in particular because these communities enable users to find peers with similar experiences. Building mutually supportive connections between peers is a key motivation for using online health communities. However, a user's role in a community may influence the formation of peer connections. In this work, we study patterns of peer connections between two structural health roles: patient and non-professional caregiver. We examine user behavior in an online health community where finding peers is not explicitly supported. This context lets us use social network analysis methods to explore the growth of such connections in the wild and identify users' peer communication preferences. We investigated how connections between peers were initiated, finding that initiations are more likely between two authors who have the same role and who are close within the broader communication network. Relationships are also more likely to form and be more interactive when authors have the same role. Our results have implications for the design of systems supporting peer communication, e.g. peer-to-peer recommendation systems.


title: Embedding Ranking-Oriented Recommender System Graphs

abstract: Graph-based recommender systems (GRSs) analyze the structural information in the graphical representation of data to make better recommendations, especially when the direct user-item relation data is sparse. Ranking-oriented GRSs that form a major class of recommendation systems, mostly use the graphical representation of preference (or rank) data for measuring node similarities, from which they can infer a recommendation list using a neighborhood-based mechanism. In this paper, we propose PGRec, a novel graph-based ranking-oriented recommendation framework. PGRec models the preferences of the users over items, by a novel graph structure called PrefGraph. This graph is then exploited by an improved embedding approach, taking advantage of both factorization and deep learning methods, to extract vectors representing users, items, and preferences. The resulting embedding are then used for predicting users' unknown pairwise preferences from which the final recommendation lists are inferred. We have evaluated the performance of the proposed method against the state of the art model-based and neighborhood-based recommendation methods, and our experiments show that PGRec outperforms the baseline algorithms up to 3.2% in terms of NDCG@10 in different MovieLens datasets.


title: Short-term stability of particles in the WD J0914+1914 white dwarf planetary system

abstract: Nearly all known white dwarf planetary systems contain detectable rocky debris in the stellar photosphere. A glaring exception is the young and still evolving white dwarf WD J0914+1914, which instead harbours a giant planet and a disc of pure gas. The stability boundaries of this disc and the future prospects for this white dwarf to be polluted with rocks depend upon the mass and orbit of the planet, which are only weakly constrained. Here we combine an ensemble of plausible planet orbits and masses to determine where observers should currently expect to find the outer boundary of the gas disc. We do so by performing a sweep of the entire plausible phase space with short-term numerical integrations. We also demonstrate that particle-star collisional trajectories, which would lead to the (unseen) signature of rocky metal pollution, occupy only a small fraction of the phase space, mostly limited to particle eccentricities above 0.75. Our analysis reveals that a highly inflated planet on a near-circular orbit is the type of planet which is most consistent with the current observations.


title: Hardware/Software Obfuscation against Timing Side-channel Attack on a GPU

abstract: GPUs are increasingly being used in security applications, especially for accelerating encryption/decryption. While GPUs are an attractive platform in terms of performance, the security of these devices raises a number of concerns. One vulnerability is the data-dependent timing information, which can be exploited by adversary to recover the encryption key. Memory system features are frequently exploited since they create detectable timing variations. In this paper, our attack model is a coalescing attack, which leverages a critical GPU microarchitectural feature -- the coalescing unit. As multiple concurrent GPU memory requests can refer to the same cache block, the coalescing unit collapses them into a single memory transaction. The access time of an encryption kernel is dependent on the number of transactions. Correlation between a guessed key value and the associated timing samples can be exploited to recover the secret key. In this paper, a series of hardware/software countermeasures are proposed to obfuscate the memory timing side channel, making the GPU more resilient without impacting performance. Our hardware-based approach attempts to randomize the width of the coalescing unit to lower the signal-to-noise ratio. We present a hierarchical Miss Status Holding Register (MSHR) design that can merge transactions across different warps. This feature boosts performance, while, at the same time, secures the execution. We also present a software-based approach to permute the organization of critical data structures, significantly changing the coalescing behavior and introducing a high degree of randomness. Equipped with our new protections, the effort to launch a successful attack is increased up to 1433X . 178X, while also improving encryption/decryption performance up to 7%.


title: A Polynomial Approach to the Spectrum of Dirac-Weyl Polygonal Billiards

abstract: The Schr\"odinger equation in a square or rectangle with hard walls is solved in every introductory quantum mechanics course. Solutions for other polygonal enclosures only exist in a very restricted class of polygons, and are all based on a result obtained by Lam\'e in 1852. Any enclosure can, of course, be addressed by finite element methods for partial differential equations. In this paper, we present a variational method to approximate the low-energy spectrum and wave-functions for arbitrary convex polygonal enclosures, developed initially for the study of vibrational modes of plates. In view of the recent interest in the spectrum of quantum dots of two dimensional materials, described by effective models with massless electrons, we extend the method to the Dirac-Weyl equation for a spin-1/2 fermion confined in a quantum billiard of polygonal shape, with different types of boundary conditions. We illustrate the method's convergence in cases where the spectrum in known exactly and apply it to cases where no exact solution exists.


title: Screening and evaluation of potential clinically significant HIV drug combinations against SARS-CoV-2 virus

abstract: In this study, we investigated the inhibition of SARS-CoV-2 spike glycoprotein with HIV drugs and their combinations. This glycoprotein is essential for the reproduction of the SARS-COV-2 virus, so its inhibition opens new avenues for the treatment of patients with COVID-19 disease. In doing so, we used the VINI in silico model of cancer, whose high accuracy in finding effective drugs and their combinations was confirmed in vitro by comparison with existing results from NCI-60 bases, and in vivo by comparison with existing clinical trial results. In the first step, the VINI model calculated the inhibition efficiency of SARS-CoV-2 spike glycoprotein with 44 FDA-approved antiviral drugs. Of these drugs, HIV drugs have been shown to be effective, while others mainly have shown weak or no efficiency. Subsequently, the VINI model calculated the inhibition efficiency of all possible double and triple HIV drug combinations, and among them identified ten with the highest inhibition efficiency. These ten combinations were analyzed by Medscape drug-drug interaction software and LexiComp Drug Interactions. All combinations except the combination of cobicistat_abacavir_rilpivirine appear to have serious interactions (risk rating category D) when dosage adjustments/reductions are required for possible toxicity. Finally, the VINI model compared the inhibition efficiency of cobicistat_abacivir_rilpivirine combination with cocktails and individual drugs already used or planned to be tested against SARS-CoV-2. Combination cobicistat_abacivir_rilpivirine demonstrated the highest inhibition of SARS-CoV-2 spike glycoprotein over others. Thus, this combination seems to be a promising candidate for the further in vitro testing and clinical trials.


title: Precise Local Estimates for Differential Equations driven by Fractional Brownian Motion: Elliptic Case

abstract: This article is concerned with stochastic differential equations driven by a $d$ dimensional fractional Brownian motion with Hurst parameter $H>1/4$, understood in the rough paths sense. Whenever the coefficients of the equation satisfy a uniform ellipticity condition, we establish a sharp local estimate on the associated control distance function and a sharp local lower estimate on the density of the solution.


title: Thermal Analysis of a 3D Stacked High-Performance Commercial Microprocessor using Face-to-Face Wafer Bonding Technology

abstract: 3D integration technologies are seeing widespread adoption in the semiconductor industry to offset the limitations and slowdown of two-dimensional scaling. High-density 3D integration techniques such as face-to-face wafer bonding with sub-10 $\mu$m pitch can enable new ways of designing SoCs using all 3 dimensions, like folding a microprocessor design across multiple 3D tiers. However, overlapping thermal hotspots can be a challenge in such 3D stacked designs due to a general increase in power density. In this work, we perform a thorough thermal simulation study on sign-off quality physical design implementation of a state-of-the-art, high-performance, out-of-order microprocessor on a 7nm process technology. The physical design of the microprocessor is partitioned and implemented in a 2-tier, 3D stacked configuration with logic blocks and memory instances in separate tiers (logic-over-memory 3D). The thermal simulation model was calibrated to temperature measurement data from a high-performance, CPU-based 2D SoC chip fabricated on the same 7nm process technology. Thermal profiles of different 3D configurations under various workload conditions are simulated and compared. We find that stacking microprocessor designs in 3D without considering thermal implications can result in maximum die temperature up to 12{\deg}C higher than their 2D counterparts under the worst-case power-indicative workload. This increase in temperature would reduce the amount of time for which a power-intensive workload can be run before throttling is required. However, logic-over-memory partitioned 3D CPU implementation can mitigate this temperature increase by half, which makes the temperature of the 3D design only 6$^\circ$C higher than the 2D baseline. We conclude that using thermal aware design partitioning and improved cooling techniques can overcome the thermal challenges associated with 3D stacking.


title: A characterisation of elementary fibrations

abstract: Grothendieck fibrations provide a unifying algebraic framework that underlies the treatment of various form of logics, such as first order logic, higher order logics and dependent type theories. In the categorical approach to logic proposed by Lawvere, which systematically uses adjoints to describe the logical operations, equality is presented in the form of a left adjoint to reindexing along a diagonal arrows in the base. Taking advantage of the modular perspective provided by category theory, one can look at those Grothendieck fibrations which sustain just the structure of equality, the so-called elementary fibrations, aka fibrations with equality. The present paper provides a characterisation of elementary fibrations based on particular structures in the fibres, called transporters. The characterisation is a substantial generalisation of the one already available for faithful fibrations. There is a close resemblance between transporters and the structures used in the semantics of the identity type of Martin-L\"of type theory. We close the paper by comparing the two.


title: Grassmann geometry of zero sets in reproducing kernel Hilbert spaces

abstract: Let $\mathcal{H}$ be a reproducing kernel Hilbert space of functions on a set $X$. We study the problem of finding a minimal geodesic of the Grassmann manifold of $\mathcal{H}$ that joins two subspaces consisting of functions which vanish on given finite subsets of $X$. We establish a necessary and sufficient condition for existence and uniqueness of geodesics, and we then analyze it in examples. We discuss the relation of the geodesic distance with other known metrics when the mentioned finite subsets are singletons. We find estimates on the upper and lower eigenvalues of the unique self-adjoint operators which define the minimal geodesics, which can be made more precise when the underlying space is the Hardy space. Also for the Hardy space we discuss the existence of geodesics joining subspaces of functions vanishing on infinite subsets of the disk, and we investigate when the product of projections onto this type of subspaces is compact.


title: A branching process with contact tracing

abstract: We consider a supercritical branching process and define a contact tracing mechanism on its genealogical tree. We calculate the growth rate of the post tracing process, and give conditions under which the tracing is strong enough to drive the process to extinction.


title: Nonlocal thermoelectricity in a topological Andreev interferometer

abstract: We discuss the phase dependent nonlocal thermoelectric effect in a topological Josephson junction in contact with a normal-metal probe. We show that, due to the helical nature of topological edge states, nonlocal thermoelectricity is generated by a purely Andreev interferometric mechanism. This response can be tuned by imposing a Josephson phase difference, through the application of a dissipationless current between the two superconductors, even without the need of applying an external magnetic field. We discuss in detail the origin of this effect and we provide also a realistic estimation of the nonlocal Seebeck coefficient that results of the order of few $\mu V/K$.


title: Evidence for the general dominance of proton shells in low-energy fission

abstract: A regular pattern, revealing the leading role of the light-fragment nuclear charge, is found to emerge from a consistent analysis of the experimental information collected recently on low-energy asymmetric fission of neutron-deficient nuclei around lead. The observation is corroborated by a theoretical investigation within a microscopic framework, suggesting the importance of proton configurations driven by quadrupole-octupole correlations. This is in contrast to the earlier theoretical interpretations in terms of dominant neutron shells. The survey of a wider area of the nuclear chart by a semi-empirical approach points to the lack of understanding of the competition between the different underlying macroscopic and microscopic forces in a quantitative manner. Combined with previously identified stabilizing forces, the present finding shows a striking connection between the "old" (actinide) and "new" (pre-actinide) islands of asymmetric fission which could steer the strive for an unified theory of fission.


title: Neural network quantum state tomography in a two-qubit experiment

abstract: We study the performance of efficient quantum state tomography methods based on neural network quantum states using measured data from a two-photon experiment. Machine learning inspired variational methods provide a promising route towards scalable state characterization for quantum simulators. While the power of these methods has been demonstrated on synthetic data, applications to real experimental data remain scarce. We benchmark and compare several such approaches by applying them to measured data from an experiment producing two-qubit entangled states. We find that in the presence of experimental imperfections and noise, confining the variational manifold to physical states, i.e. to positive semi-definite density matrices, greatly improves the quality of the reconstructed states but renders the learning procedure more demanding. Including additional, possibly unjustified, constraints, such as assuming pure states, facilitates learning, but also biases the estimator.


title: The classical double copy of non-singular black holes

abstract: We apply the classical double copy procedure to a class of regular, non-singular black hole solutions. We give several examples, paying particular attention to a string-theory-corrected black hole solution emerging from T-duality. Non-perturbative stringy corrections introduce an ultraviolet (UV) zero-point length cutoff which results in non-singular black hole spacetimes. Apart from the UV regulator, the solution is equivalent to the Bardeen black hole spacetime. We extend this solution to include an asymptotic de Sitter background. All Yang-Mills field theory quantities associated with the double copy are well-behaved and finite for all values of parameters. We present a thorough analysis of the black hole horizon structure, additionally uncovering a simple yet new connection between horizons on the gravity side and electric fields on the gauge theory side of the double copy.


title: Ultra-light deep MIR by trimming lottery tickets

abstract: Current state-of-the-art results in Music Information Retrieval are largely dominated by deep learning approaches. These provide unprecedented accuracy across all tasks. However, the consistently overlooked downside of these models is their stunningly massive complexity, which seems concomitantly crucial to their success. In this paper, we address this issue by proposing a model pruning method based on the lottery ticket hypothesis. We modify the original approach to allow for explicitly removing parameters, through structured trimming of entire units, instead of simply masking individual weights. This leads to models which are effectively lighter in terms of size, memory and number of operations. We show that our proposal can remove up to 90% of the model parameters without loss of accuracy, leading to ultra-light deep MIR models. We confirm the surprising result that, at smaller compression ratios (removing up to 85% of a network), lighter models consistently outperform their heavier counterparts. We exhibit these results on a large array of MIR tasks including audio classification, pitch recognition, chord extraction, drum transcription and onset estimation. The resulting ultra-light deep learning models for MIR can run on CPU, and can even fit on embedded devices with minimal degradation of accuracy.


title: Alternative derivation of the relativistic three-particle quantization condition

abstract: We present a simplified derivation of the relativistic three-particle quantization condition for identical, spinless particles described by a generic relativistic field theory satisfying a $\mathbb Z_2$ symmetry. The simplification is afforded by using a three-particle quasilocal K matrix that is not fully symmetrized, $\widetilde{\mathcal{K}}_{\rm df,3}^{(u,u)}$, and makes extensive use of time-ordered perturbation theory (TOPT). We obtain a new form of the quantization condition. This new form can then be related algebraically to the standard quantization condition, which depends on a fully symmetric three-particle K matrix, $\mathcal{K}_{\rm df,3}$. The new derivation is fully explicit, allowing, for example, a closed-form expression for $\mathcal{K}_{\rm df,3}$ to be given in terms of TOPT amplitudes. The new form of the quantization condition is similar in structure to that obtained in the "finite-volume unitarity" approach, and in a companion paper we make this connection concrete. Our simplified approach should also allow a more straightforward generalization of the quantization condition to nondegenerate particles, and perhaps also to more than three particles.


title: Self-supervised learning through the eyes of a child

abstract: Within months of birth, children develop meaningful expectations about the world around them. How much of this early knowledge can be explained through generic learning mechanisms applied to sensory data, and how much of it requires more substantive innate inductive biases? Addressing this fundamental question in its full generality is currently infeasible, but we can hope to make real progress in more narrowly defined domains, such as the development of high-level visual categories, thanks to improvements in data collecting technology and recent progress in deep learning. In this paper, our goal is precisely to achieve such progress by utilizing modern self-supervised deep learning methods and a recent longitudinal, egocentric video dataset recorded from the perspective of three young children (Sullivan et al., 2020). Our results demonstrate the emergence of powerful, high-level visual representations from developmentally realistic natural videos using generic self-supervised learning objectives.


title: Equivalence of relativistic three-particle quantization conditions

abstract: We show that a recently derived alternative form of the relativistic three-particle quantization condition for identical particles can be rewritten in terms of the R matrix introduced to give a unitary representation of the infinite-volume three-particle scattering amplitude. Combined with earlier work, this shows the equivalence of the relativistic effective field theory approach of Hansen and Sharpe (Refs.[1,2]) and the "finite-volume unitarity" approach of Mai and D\"oring (Refs.[3,4]). It also provides a generalization of the latter approach to arbitrary angular momenta of two-particle subsystems.


title: Opportunities for probing $U(1)_{T3R}$ with light mediators

abstract: We consider strategies for using new datasets to probe scenarios in which light right-handed SM fermions couple to a new gauge group, $U(1)_{T3R}$. This scenario provides a natural explanation for the light flavor sector scale, and a motivation for sub-GeV dark matter. There is parameter space which is currently allowed, but we find that much of it can be probed with future experiments. In particular, cosmological and astrophysical observations, neutrino experiments and experiments which search for displaced visible decay or invisible decay can all play a role. Still, there is a small region of parameter space which even these upcoming experiments will not be able to probe. This model can explain the observed 2.4-3$\sigma$ excess of events at the COHERENT experiment in the parameter space allowed by current laboratory experiments, but the ongoing/upcoming laboratory experiments will decisively probe this possibility.


title: Contiguous Graph Partitioning For Optimal Total Or Bottleneck Communication

abstract: Graph partitioning schedules parallel calculations like sparse matrix-vector multiply (SpMV). We consider contiguous partitions, where the $m$ rows (or columns) of a sparse matrix with $N$ nonzeros are split into $K$ parts without reordering. We propose the first near-linear time algorithms for several graph partitioning problems in the contiguous regime. Traditional objectives such as the simple edge cut, hyperedge cut, or hypergraph connectivity minimize the total cost of all parts under a balance constraint. Our total partitioners use $O(Km + N)$ space. They run in $O((Km\log(m) + N)\log(N))$ time, a significant improvement over prior $O(K(m^2 + N))$ time algorithms due to Kernighan and Grandjean et. al. Bottleneck partitioning minimizes the maximum cost of any part. We propose a new bottleneck cost which reflects the sum of communication and computation on each part. Our bottleneck partitioners use linear space. The exact algorithm runs in linear time when $K^2$ is $O(N^C)$ for $C < 1$. Our $(1 + \epsilon)$-approximate algorithm runs in linear time when $K\log(c_{high}/(c_{low}\epsilon))$ is $O(N^C)$ for $C < 1$, where $c_{high}$ and $c_{low}$ are upper and lower bounds on the optimal cost. We also propose a simpler $(1 + \epsilon)$-approximate algorithm which runs in a factor of $\log(c_{high}/(c_{low}\epsilon))$ from linear time. We empirically demonstrate that our algorithms efficiently produce high-quality contiguous partitions on a test suite of 42 test matrices. When $K = 8$, our hypergraph connectivity partitioner achieved a speedup of $53\times$ (mean $15.1\times$) over prior algorithms. The mean runtime of our bottleneck partitioner was 5.15 SpMVs.


title: SimulEval: An Evaluation Toolkit for Simultaneous Translation

abstract: Simultaneous translation on both text and speech focuses on a real-time and low-latency scenario where the model starts translating before reading the complete source input. Evaluating simultaneous translation models is more complex than offline models because the latency is another factor to consider in addition to translation quality. The research community, despite its growing focus on novel modeling approaches to simultaneous translation, currently lacks a universal evaluation procedure. Therefore, we present SimulEval, an easy-to-use and general evaluation toolkit for both simultaneous text and speech translation. A server-client scheme is introduced to create a simultaneous translation scenario, where the server sends source input and receives predictions for evaluation and the client executes customized policies. Given a policy, it automatically performs simultaneous decoding and collectively reports several popular latency metrics. We also adapt latency metrics from text simultaneous translation to the speech task. Additionally, SimulEval is equipped with a visualization interface to provide better understanding of the simultaneous decoding process of a system. SimulEval has already been extensively used for the IWSLT 2020 shared task on simultaneous speech translation. Code will be released upon publication.