title: Bounded solutions of KdV: uniqueness and the loss of almost periodicity

abstract: We address two pressing questions in the theory of the Korteweg--de Vries (KdV) equation. First, we show the uniqueness of solutions to KdV that are merely bounded, without any further decay, regularity, periodicity, or almost periodicity assumptions. The second question, emphasized by Deift, regards whether almost periodic initial data leads to almost periodic solutions to KdV. Building on the new observation that this is false for the Airy equation, we construct an example of almost periodic initial data whose KdV evolution remains bounded, but fails to be almost periodic at a later time. Our uniqueness result ensures that the solution constructed is the unique development of this initial data.


title: A Brezis-Nirenberg type result for mixed local and nonlocal operators

abstract: We study a critical problem for an operator of mixed order obtained by the superposition of a Laplacian with a fractional Laplacian. In particular, we investigate the corresponding Sobolev inequality, detecting the optimal constant, which we show that is never achieved. Moreover, we present an existence (and nonexistence) theory for the corresponding subcritical perturbation problem.


title: Robust Locomotion on Legged Robots through Planning on Motion Primitive Graphs

abstract: The functional demands of robotic systems often require completing various tasks or behaviors under the effect of disturbances or uncertain environments. Of increasing interest is the autonomy for dynamic robots, such as multirotors, motor vehicles, and legged platforms. Here, disturbances and environmental conditions can have significant impact on the successful performance of the individual dynamic behaviors, referred to as "motion primitives". Despite this, robustness can be achieved by switching to and transitioning through suitable motion primitives. This paper contributes such a method by presenting an abstraction of the motion primitive dynamics and a corresponding "motion primitive transfer function". From this, a mixed discrete and continuous "motion primitive graph" is constructed, and an algorithm capable of online search of this graph is detailed. The result is a framework capable of realizing holistic robustness on dynamic systems. This is experimentally demonstrated for a set of motion primitives on a quadrupedal robot, subject to various environmental and intentional disturbances.


title: Computing mixed Schatten norm of completely positive maps

abstract: Computing $p \rightarrow q$ norm for matrices is a classical problem in computational mathematics and power iteration is a well-known method for computing $p \rightarrow q $ norm for a matrix with nonnegative entries. Here we define an equivalent iteration method for computing $ S_p \rightarrow S_q $ norm for completely positive maps where $S_p$ is the Schatten $p$ norm. We generalize almost all of the definitions, properties, lemmas, etc. in the matrix setting to completely positive maps and prove an important theorem in this setting.


title: Temporal, structural, and functional heterogeneities extend criticality and antifragility in random Boolean networks

abstract: Most models of complex systems have been homogeneous, i.e., all elements have the same properties (spatial, temporal, structural, functional). However, most natural systems are heterogeneous: few elements are more relevant, larger, stronger, or faster than others. In homogeneous systems, criticality -- a balance between change and stability, order and chaos -- is usually found for a very narrow region in the parameter space, close to a phase transition. Using random Boolean networks -- a general model of discrete dynamical systems -- we show that heterogeneity -- in time, structure, and function -- can broaden additively the parameter region where criticality is found. Moreover, parameter regions where antifragility is found are also increased with heterogeneity. However, maximum antifragility is found for particular parameters in homogeneous networks. Our work suggests that the "optimal" balance between homogeneity and heterogeneity is non-trivial, context-dependent, and in some cases, dynamic.

categories: nlin.AO cs.DM cs.IT math.DS math.IT q-bio.QM


title: Kerr effects in tilted multi-Weyl semimetals

abstract: We calculate the optical conductivity of type-I and type-II multi-Weyl semimetals(m-WSMs) in time-reversal(TR) broken case at finite doping. It is found that both longitudinal and Hall conductivities are renormalized by J(monopole charge) perpendicular to Weyl nodes separation and longitudal conductivity along nodes has non-trivial dependence on J. The Kerr rotations in thin films and bulk have different dependence on system parameters. The Kerr rotation in ultra-thin films is independent of monopole charge J and depends only on Fermi velocity v F while in bulk it dependent on monopole charge J, Fermi velocity and material parameters.


title: Bidirectional Learning for Offline Infinite-width Model-based Optimization

abstract: In offline model-based optimization, we strive to maximize a black-box objective function by only leveraging a static dataset of designs and their scores. This problem setting arises in numerous fields including the design of materials, robots, DNA sequences, and proteins. Recent approaches train a deep neural network (DNN) on the static dataset to act as a proxy function, and then perform gradient ascent on the existing designs to obtain potentially high-scoring designs. This methodology frequently suffers from the out-of-distribution problem where the proxy function often returns poor designs. To mitigate this problem, we propose BiDirectional learning for offline Infinite-width model-based optimization (BDI). BDI consists of two mappings: the forward mapping leverages the static dataset to predict the scores of the high-scoring designs, and the backward mapping leverages the high-scoring designs to predict the scores of the static dataset. The backward mapping, neglected in previous work, can distill more information from the static dataset into the high-scoring designs, which effectively mitigates the out-of-distribution problem. For a finite-width DNN model, the loss function of the backward mapping is intractable and only has an approximate form, which leads to a significant deterioration of the design quality. We thus adopt an infinite-width DNN model, and propose to employ the corresponding neural tangent kernel to yield a closed-form loss for more accurate design updates. Experiments on various tasks verify the effectiveness of BDI. The code is available at https://github.com/GGchen1997/BDI.


title: Information Theoretic Measures of Causal Influences during Transient Neural Events

abstract: Transient phenomena play a key role in coordinating brain activity at multiple scales, however,their underlying mechanisms remain largely unknown. A key challenge for neural data science is thus to characterize the network interactions at play during these events. Using the formalism of Structural Causal Models and their graphical representation, we investigate the theoretical and empirical properties of Information Theory based causal strength measures in the context of recurring spontaneous transient events. After showing the limitations of Transfer Entropy and Dynamic Causal Strength in such a setting, we introduce a novel measure, relative Dynamic Causal Strength, and provide theoretical and empirical support for its benefits. These methods are applied to simulated and experimentally recorded neural time series, and provide results in agreement with our current understanding of the underlying brain circuits.


title: Random initialisations performing above chance and how to find them

abstract: Neural networks trained with stochastic gradient descent (SGD) starting from different random initialisations typically find functionally very similar solutions, raising the question of whether there are meaningful differences between different SGD solutions. Entezari et al.\ recently conjectured that despite different initialisations, the solutions found by SGD lie in the same loss valley after taking into account the permutation invariance of neural networks. Concretely, they hypothesise that any two solutions found by SGD can be permuted such that the linear interpolation between their parameters forms a path without significant increases in loss. Here, we use a simple but powerful algorithm to find such permutations that allows us to obtain direct empirical evidence that the hypothesis is true in fully connected networks. Strikingly, we find that two networks already live in the same loss valley at the time of initialisation and averaging their random, but suitably permuted initialisation performs significantly above chance. In contrast, for convolutional architectures, our evidence suggests that the hypothesis does not hold. Especially in a large learning rate regime, SGD seems to discover diverse modes.


title: Report of the Topical Group on Higgs Physics for Snowmass 2021: The Case for Precision Higgs Physics

abstract: A future Higgs Factory will provide improved precision on measurements of Higgs couplings beyond those obtained by the LHC, and will enable a broad range of investigations across the fields of fundamental physics, including the mechanism of electroweak symmetry breaking, the origin of the masses and mixing of fundamental particles, the predominance of matter over antimatter, and the nature of dark matter. Future colliders will measure Higgs couplings to a few per cent, giving a window to beyond the Standard Model (BSM) physics in the 1-10 TeV range. In addition, they will make precise measurements of the Higgs width, and characterize the Higgs self-coupling. This report details the work of the EF01 and EF02 working groups for the Snowmass 2021 study.


title: Test-Time Prompt Tuning for Zero-Shot Generalization in Vision-Language Models

abstract: Pre-trained vision-language models (e.g., CLIP) have shown promising zero-shot generalization in many downstream tasks with properly designed text prompts. Instead of relying on hand-engineered prompts, recent works learn prompts using the training data from downstream tasks. While effective, training on domain-specific data reduces a model's generalization capability to unseen new domains. In this work, we propose test-time prompt tuning (TPT), a method that can learn adaptive prompts on the fly with a single test sample. For image classification, TPT optimizes the prompt by minimizing the entropy with confidence selection so that the model has consistent predictions across different augmented views of each test sample. In evaluating generalization to natural distribution shifts, TPT improves the zero-shot top-1 accuracy of CLIP by 3.6% on average, surpassing previous prompt tuning approaches that require additional task-specific training data. In evaluating cross-dataset generalization with unseen categories, TPT performs on par with the state-of-the-art approaches that use additional training data. Project page: https://azshue.github.io/TPT.


title: Rank-expanding satellites, Whitehead doubles, and Heegaard Floer homology

abstract: We show that a large class of satellite operators are rank-expanding; that is, they map some rank-one subgroup of the concordance group onto an infinite linearly independent set. Our work constitutes the first systematic study of this property in the literature and partially affirms a conjecture of the second author and Pinz\'on-Caicedo. More generally, we establish a Floer-theoretic condition for a family of companion knots to have infinite-rank image under satellites from this class. The methods we use are amenable to patterns which act trivially in topological concordance and are capable of handling a surprisingly wide variety of companions. For instance, we give an infinite linearly independent family of Whitehead doubles whose companion knots all have negative $\tau$-invariant. Our also results recover and extend several theorems in this area established using instanton Floer homology.


title: On the complexity of finding stationary points of smooth functions in one dimension

abstract: We characterize the query complexity of finding stationary points of one-dimensional non-convex but smooth functions. We consider four settings, based on whether the algorithms under consideration are deterministic or randomized, and whether the oracle outputs $1^{\rm st}$-order or both $0^{\rm th}$- and $1^{\rm st}$-order information. Our results show that algorithms for this task provably benefit by incorporating either randomness or $0^{\rm th}$-order information. Our results also show that, for every dimension $d \geq 1$, gradient descent is optimal among deterministic algorithms using $1^{\rm st}$-order queries only.


title: Propagation of a realistic magnetar jet through binary neutron star merger medium and implications for short gamma-ray bursts

abstract: The origin of short gamma-ray bursts (sGRBs) is associated with outflows powered by the remnant of a binary neutron star merger. This remnant can be either a black hole or a highly magnetized, fastly spinning neutron star, also known as a magnetar. Here, we present the results of two relativistic magnetohydrodynamical (RMHD) simulations aimed at investigating the large-scale dynamics and propagation of magnetar collimated outflows through the medium surrounding the remnant. The first simulation evolves a realistic jet by injecting external simulation data, while the second evolves an analytical model jet with similar properties for comparison. We find that both outflows remain collimated and successfully emerge through the static medium surrounding the remnant. However, they fail to attain relativistic velocities and only reach a mean maximum speed of ~0.7c for the realistic jet, and ~0.6c for the analytical jet. We also find that the realistic jet has a much more complex structure. The lack of highly relativistic speeds, that makes these jets unsuitable as short GRB sources, is due to numerical limitations and not general to all possible magnetar outflows. A jet like the one we study, however, could give rise to or augment a blue kilonova component. In addition, it would make the propagation of a relativistic jet easier, should one be launched after the neutron star collapses into a black hole.


title: Medical Image Segmentation using LeViT-UNet++: A Case Study on GI Tract Data

abstract: Gastro-Intestinal Tract cancer is considered a fatal malignant condition of the organs in the GI tract. Due to its fatality, there is an urgent need for medical image segmentation techniques to segment organs to reduce the treatment time and enhance the treatment. Traditional segmentation techniques rely upon handcrafted features and are computationally expensive and inefficient. Vision Transformers have gained immense popularity in many image classification and segmentation tasks. To address this problem from a transformers' perspective, we introduced a hybrid CNN-transformer architecture to segment the different organs from an image. The proposed solution is robust, scalable, and computationally efficient, with a Dice and Jaccard coefficient of 0.79 and 0.72, respectively. The proposed solution also depicts the essence of deep learning-based automation to improve the effectiveness of the treatment


title: Quantum simulation of spin-1/2 XYZ model using solid-state spin centers

abstract: In this work we propose a novel solid-state platform for creating quantum simulators based on implanted spin centers in semiconductors. We show that under the presence of an external magnetic field, an array of $S=1$ spin centers interacting through magnetic dipole-dipole interaction can be mapped into an effective spin-half system equivalent to the XYZ model in an external magnetic field. Interestingly, this system presents a wide range of quantum phases and critical behaviors that can be controlled via magnetic field and orientational arrangement of the spin centers. We demonstrate our interacting spin chain can be tuned to both isotropic Heisenberg model and transverse-field Ising universality class. Notably, our model contains a line where the system is in a critical floating phase that terminates at Berezinskii-Kosterlitz-Thouless and Pokrovsky-Talapov transition points. We propose this system as the first solid-state quantum simulator for the floating phase based on spin centers.


title: Spectral Total-Variation Processing of Shapes: Theory and Applications

abstract: We present an analysis of total-variation (TV) on non-Euclidean parameterized surfaces, a natural representation of the shapes used in 3D graphics. Our work explains recent experimental findings in shape spectral TV [Fumero et al., 2020] and adaptive anisotropic spectral TV [Biton and Gilboa, 2022]. A new way to generalize set convexity from the plane to surfaces is derived by characterizing the TV eigenfunctions on surfaces. Relationships between TV, area, eigenvalue, eigenfunctions and their discontinuities are discovered. Further, we expand the shape spectral TV toolkit to include versatile zero-homogeneous flows demonstrated through smoothing and exaggerating filters. Last but not least, we propose the first TV-based method for shape deformation, characterized by deformations along geometrical bottlenecks. We show these bottlenecks to be aligned with eigenfunction discontinuities. This research advances the field of spectral TV on surfaces and its application in 3D graphics, offering new perspectives for shape filtering and deformation.


title: Distribution Aware Metrics for Conditional Natural Language Generation

abstract: Traditional automated metrics for evaluating conditional natural language generation use pairwise comparisons between a single generated text and the best-matching gold-standard ground truth text. When multiple ground truths are available, scores are aggregated using an average or max operation across references. While this approach works well when diversity in the ground truth data (i.e. dispersion of the distribution of conditional texts) can be ascribed to noise, such as in automated speech recognition, it does not allow for robust evaluation in the case where diversity in the ground truths represents signal for the model. In this work we argue that existing metrics are not appropriate for domains such as visual description or summarization where ground truths are semantically diverse, and where the diversity in those captions captures useful additional information about the context. We propose a novel paradigm for multi-candidate evaluation of conditional language generation models, and a new family of metrics that compare the distributions of reference and model-generated caption sets using small sample sets of each. We demonstrate the utility of our approach with a case study in visual description: where we show that existing models optimize for single-description quality over diversity, and gain some insights into how sampling methods and temperature impact description quality and diversity.


abstract: Beam management is a challenging task for millimeter wave (mmWave) and sub-terahertz communication systems, especially in scenarios with highly-mobile users. Leveraging external sensing modalities such as vision, LiDAR, radar, position, or a combination of them, to address this beam management challenge has recently attracted increasing interest from both academia and industry. This is mainly motivated by the dependency of the beam direction decision on the user location and the geometry of the surrounding environment -- information that can be acquired from the sensory data. To realize the promised beam management gains, such as the significant reduction in beam alignment overhead, in practice, however, these solutions need to account for important aspects. For example, these multi-modal sensing aided beam selection approaches should be able to generalize their learning to unseen scenarios and should be able to operate in realistic dense deployments. The "Multi-Modal Beam Prediction Challenge 2022: Towards Generalization" competition is offered to provide a platform for investigating these critical questions. In order to facilitate the generalizability study, the competition offers a large-scale multi-modal dataset with co-existing communication and sensing data collected across multiple real-world locations and different times of the day. In this paper, along with the detailed descriptions of the problem statement and the development dataset, we provide a baseline solution that utilizes the user position data to predict the optimal beam indices. The objective of this challenge is to go beyond a simple feasibility study and enable necessary research in this direction, paving the way towards generalizable multi-modal sensing-aided beam management for real-world future communication systems.


title: On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs

abstract: Online Contention Resolution Schemes (OCRS's) represent a modern tool for selecting a subset of elements, subject to resource constraints, when the elements are presented to the algorithm sequentially. OCRS's have led to some of the best-known competitive ratio guarantees for online resource allocation problems, with the added benefit of treating different online decisions -- accept/reject, probing, pricing -- in a unified manner. This paper analyzes OCRS's for resource constraints defined by matchings in graphs, a fundamental structure in combinatorial optimization. We consider two dimensions of variants: the elements being presented in adversarial or random order; and the graph being bipartite or general. We improve the state of the art for all combinations of variants, both in terms of algorithmic guarantees and impossibility results. Some of our algorithmic guarantees are best-known even compared to Contention Resolution Schemes that can choose the order of arrival or are offline. All in all, our results for OCRS directly improve the best-known competitive ratios for online accept/reject, probing, and pricing problems on graphs in a unified manner.


title: On-Device Domain Generalization

abstract: We present a systematic study of domain generalization (DG) for tiny neural networks. This problem is critical to on-device machine learning applications but has been overlooked in the literature where research has been merely focused on large models. Tiny neural networks have much fewer parameters and lower complexity and therefore should not be trained the same way as their large counterparts for DG applications. By conducting extensive experiments, we find that knowledge distillation (KD), a well-known technique for model compression, is much better for tackling the on-device DG problem than conventional DG methods. Another interesting observation is that the teacher-student gap on out-of-distribution data is bigger than that on in-distribution data, which highlights the capacity mismatch issue as well as the shortcoming of KD. We further propose a method called out-of-distribution knowledge distillation (OKD) where the idea is to teach the student how the teacher handles out-of-distribution data synthesized via disruptive data augmentation. Without adding any extra parameter to the model -- hence keeping the deployment cost unchanged -- OKD significantly improves DG performance for tiny neural networks in a variety of on-device DG scenarios for image and speech applications. We also contribute a scalable approach for synthesizing visual domain shifts, along with a new suite of DG datasets to complement existing testbeds.


title: Test-Time Training with Masked Autoencoders

abstract: Test-time training adapts to a new test distribution on the fly by optimizing a model for each test input using self-supervision. In this paper, we use masked autoencoders for this one-sample learning problem. Empirically, our simple method improves generalization on many visual benchmarks for distribution shifts. Theoretically, we characterize this improvement in terms of the bias-variance trade-off.


title: Gravitational Contact Interactions -- Does the Jordan Frame Exist?

abstract: Scalar--tensor theories, with Einstein Hilbert and non-minimal interactions, $\sim M^2R/2 -\alpha\phi^2R/12 $, have graviton exchange induced contact interactions. These always pull the theory back into a formal Einstein frame in which $\alpha$ does not exist. In the Einstein frame, contact terms are induced, that are then absorbed back into other couplings to define the effective potential (or equivalently, the renormalization group). We show how these effects manifest themselves in a simple model by computing the effective potential in both frames displaying the discrepancy.


title: $\tilde{O}(n+\mathrm{poly}(k))$-time Algorithm for Bounded Tree Edit Distance

abstract: Computing the edit distance of two strings is one of the most basic problems in computer science and combinatorial optimization. Tree edit distance is a natural generalization of edit distance in which the task is to compute a measure of dissimilarity between two (unweighted) rooted trees with node labels. Perhaps the most notable recent application of tree edit distance is in NoSQL big databases, such as MongoDB, where each row of the database is a JSON document represented as a labeled rooted tree, and finding dissimilarity between two rows is a basic operation. Until recently, the fastest algorithm for tree edit distance ran in cubic time (Demaine, Mozes, Rossman, Weimann; TALG'10); however, Mao (FOCS'21) broke the cubic barrier for the tree edit distance problem using fast matrix multiplication. Given a parameter $k$ as an upper bound on the distance, an $O(n+k^2)$-time algorithm for edit distance has been known since the 1980s due to the works of Myers (Algorithmica'86) and Landau and Vishkin (JCSS'88). The existence of an $\tilde{O}(n+\mathrm{poly}(k))$-time algorithm for tree edit distance has been posed as an open question, e.g., by Akmal and Jin (ICALP'21), who gave a state-of-the-art $\tilde{O}(nk^2)$-time algorithm. In this paper, we answer this question positively.


title: Causal Modifications of Gravity and Their Observational Bounds

abstract: Since general relativity is the unique theory of massless spin 2 particles at large distances, the most reasonable way to have significant modifications is to introduce one or more light scalars that mediate a new long-range force. Most existing studies of such scalars invoke models that exhibit some kind of "screening" at short distances to hide the force from solar system tests. However, as is well known, such modifications also exhibit superluminality, which can be interpreted as a form of acausality. In this work we explore explicitly subluminal and causal scalar field models. In particular, we study a conformally coupled scalar $\phi$, with a small coupling to matter to obey solar system bounds, and a non-canonical kinetic term $K(X)$ ($X=(\partial\phi)^2/2$) that obeys all subluminality constraints and is hyperbolic. We consider $K(X)$ that is canonical for small $X$, but beyond some nonlinear scale enters a new scaling regime of power $p$, with $1/2<p<1$ (the DBI kinetic term is the limit $p=1/2$ and a canonical scalar is $p=1$). As opposed to screening (and superluminality), this new force becomes more and more important in the regime of high densities (and subluminality). We then turn to the densest environments to put bounds on this new interaction. We compute constraints from precession in binary systems such as Hulse-Taylor, we compute corrections to neutron star hydrostatic equilibrium, and we compute power in radiation, both tensor mode corrections and the new scalar mode, which can be important during mergers.


title: OmniVL:One Foundation Model for Image-Language and Video-Language Tasks

abstract: This paper presents OmniVL, a new foundation model to support both image-language and video-language tasks using one universal architecture. It adopts a unified transformer-based visual encoder for both image and video inputs, and thus can perform joint image-language and video-language pretraining. We demonstrate, for the first time, such a paradigm benefits both image and video tasks, as opposed to the conventional one-directional transfer (e.g., use image-language to help video-language). To this end, we propose a decoupled joint pretraining of image-language and video-language to effectively decompose the vision-language modeling into spatial and temporal dimensions and obtain performance boost on both image and video tasks. Moreover, we introduce a novel unified vision-language contrastive (UniVLC) loss to leverage image-text, video-text, image-label (e.g., image classification), video-label (e.g., video action recognition) data together, so that both supervised and noisily supervised pretraining data are utilized as much as possible. Without incurring extra task-specific adaptors, OmniVL can simultaneously support visual only tasks (e.g., image classification, video action recognition), cross-modal alignment tasks (e.g., image/video-text retrieval), and multi-modal understanding and generation tasks (e.g., image/video question answering, captioning). We evaluate OmniVL on a wide range of downstream tasks and achieve state-of-the-art or competitive results with similar model size and data scale.


title: Improved proteasomal cleavage prediction with positive-unlabeled learning

abstract: Accurate in silico modeling of the antigen processing pathway is crucial to enable personalized epitope vaccine design for cancer. An important step of such pathway is the degradation of the vaccine into smaller peptides by the proteasome, some of which are going to be presented to T cells by the MHC complex. While predicting MHC-peptide presentation has received a lot of attention recently, proteasomal cleavage prediction remains a relatively unexplored area in light of recent advancesin high-throughput mass spectrometry-based MHC ligandomics. Moreover, as such experimental techniques do not allow to identify regions that cannot be cleaved, the latest predictors generate decoy negative samples and treat them as true negatives when training, even though some of them could actually be positives. In this work, we thus present a new predictor trained with an expanded dataset and the solid theoretical underpinning of positive-unlabeled learning, achieving a new state-of-the-art in proteasomal cleavage prediction. The improved predictive capabilities will in turn enable more precise vaccine development improving the efficacy of epitope-based vaccines. Pretrained models are available on GitHub


title: A Survey on the application of Data Science And Analytics in the field of Organised Sports

abstract: The application of Data Science and Analytics to optimize or predict outcomes is Ubiquitous in the Modern World. Data Science and Analytics have optimized almost every domain that exists in the market. In our survey, we focus on how the field of Analytics has been adopted in the field of sports, and how it has contributed to the transformation of the game right from the assessment of on-field players and their selection to the prediction of winning team and to the marketing of tickets and business aspects of big sports tournaments. We will present the analytical tools, algorithms, and methodologies adopted in the field of Sports Analytics for different sports and also present our views on the same and we will also compare and contrast these existing approaches. By doing so, we will also present the best tools, algorithms, and analytical methodologies to be considered by anyone who is looking to experiment with sports data and analyze various aspects of the game.


title: On the Soft-Subnetwork for Few-shot Class Incremental Learning

abstract: Inspired by Regularized Lottery Ticket Hypothesis (RLTH), which hypothesizes that there exist smooth (non-binary) subnetworks within a dense network that achieve the competitive performance of the dense network, we propose a few-shot class incremental learning (FSCIL) method referred to as \emph{Soft-SubNetworks (SoftNet)}. Our objective is to learn a sequence of sessions incrementally, where each session only includes a few training instances per class while preserving the knowledge of the previously learned ones. SoftNet jointly learns the model weights and adaptive non-binary soft masks at a base training session in which each mask consists of the major and minor subnetwork; the former aims to minimize catastrophic forgetting during training, and the latter aims to avoid overfitting to a few samples in each new training session. We provide comprehensive empirical validations demonstrating that our SoftNet effectively tackles the few-shot incremental learning problem by surpassing the performance of state-of-the-art baselines over benchmark datasets.


title: MIPI 2022 Challenge on RGBW Sensor Fusion: Dataset and Report

abstract: Developing and integrating advanced image sensors with novel algorithms in camera systems are prevalent with the increasing demand for computational photography and imaging on mobile platforms. However, the lack of high-quality data for research and the rare opportunity for in-depth exchange of views from industry and academia constrain the development of mobile intelligent photography and imaging (MIPI). To bridge the gap, we introduce the first MIPI challenge, including five tracks focusing on novel image sensors and imaging algorithms. In this paper, RGBW Joint Fusion and Denoise, one of the five tracks, working on the fusion of binning-mode RGBW to Bayer, is introduced. The participants were provided with a new dataset including 70 (training) and 15 (validation) scenes of high-quality RGBW and Bayer pairs. In addition, for each scene, RGBW of different noise levels was provided at 24dB and 42dB. All the data were captured using an RGBW sensor in both outdoor and indoor conditions. The final results are evaluated using objective metrics, including PSNR, SSIM}, LPIPS, and KLD. A detailed description of all models developed in this challenge is provided in this paper. More details of this challenge and the link to the dataset can be found at https://github.com/mipi-challenge/MIPI2022.


title: Research on the spectral reconstruction of a low-dimensional filter array micro-spectrometer based on a truncated singular value decomposition-convex optimization algorithm

abstract: Currently, the engineering of miniature spectrometers mainly faces three problems: the mismatch between the number of filters at the front end of the detector and the spectral reconstruction accuracy; the lack of a stable spectral reconstruction algorithm; and the lack of a spectral reconstruction evaluation method suitable for engineering. Therefore, based on 20 sets of filters, this paper classifies and optimizes the filter array by the K-means algorithm and particle swarm algorithm, and obtains the optimal filter combination under different matrix dimensions. Then, the truncated singular value decomposition-convex optimization algorithm is used for high-precision spectral reconstruction, and the detailed spectral reconstruction process of two typical target spectra is described. In terms of spectral evaluation, due to the strong randomness of the target detected during the working process of the spectrometer, the standard value of the target spectrum cannot be obtained. Therefore, for the first time, we adopt the method of joint cross-validation of multiple sets of data for spectral evaluation. The results show that when the random error of positive or negative 2 code values is applied multiple times for reconstruction, the spectral angle cosine value between the reconstructed curves becomes more than 0.995, which proves that the spectral reconstruction under this algorithm has high stability. At the same time, the spectral angle cosine value of the spectral reconstruction curve and the standard curve can reach above 0.99, meaning that it realizes a high-precision spectral reconstruction effect. A high-precision spectral reconstruction algorithm based on truncated singular value-convex optimization, which is suitable for engineering applications, is established in this paper, providing important scientific research value for the engineering application of micro-spectrometers.


title: Competitive equilibrium and the double auction

abstract: In this paper, we revisit the common claim that double auctions necessarily generate competitive equilibria. We begin by observing that competitive equilibrium has some counterintuitive implications: specifically, it predicts that monotone shifts in the value distribution can leave prices unchanged. Using experiments, we then test whether these implications are borne out by the data. We find that in double auctions with stationary value distributions, the resulting prices can be far from competitive equilibria. We also show that the effectiveness of our counterexamples is blunted when traders can leave without replacement as time progresses. Taken together, these findings suggest that the `Marshallian path' is crucial for generating equilibrium prices in double auctions.


title: Not As Easy As You Think -- Experiences and Lessons Learnt from Trying to Create a Bottom-Up Visualization Image Typology

abstract: We present and discuss the results of a two-year qualitative analysis of images published in IEEE Visualization (VIS) papers. Specifically, we derive a typology of 13 visualization image types, coded to distinguish visualizations and several image characteristics. The categorization process required much more time and was more difficult than we initially thought. The resulting typology and image analysis may serve a number of purposes: to study the evolution of the community and its research output over time, to facilitate the categorization of visualization images for the purpose of teaching, to identify visual designs for evaluation purposes, or to enable progress towards standardization in visualization. In addition to the typology and image characterization, we provide a dataset of 6,833 tagged images and an online tool that can be used to explore and analyze the large set of tagged images. We thus facilitate a discussion of the diverse visualizations used and how they are published and communicated in our community.


title: Improving Robust Fairness via Balance Adversarial Training

abstract: Adversarial training (AT) methods are effective against adversarial attacks, yet they introduce severe disparity of accuracy and robustness between different classes, known as the robust fairness problem. Previously proposed Fair Robust Learning (FRL) adaptively reweights different classes to improve fairness. However, the performance of the better-performed classes decreases, leading to a strong performance drop. In this paper, we observed two unfair phenomena during adversarial training: different difficulties in generating adversarial examples from each class (source-class fairness) and disparate target class tendencies when generating adversarial examples (target-class fairness). From the observations, we propose Balance Adversarial Training (BAT) to address the robust fairness problem. Regarding source-class fairness, we adjust the attack strength and difficulties of each class to generate samples near the decision boundary for easier and fairer model learning; considering target-class fairness, by introducing a uniform distribution constraint, we encourage the adversarial example generation process for each class with a fair tendency. Extensive experiments conducted on multiple datasets (CIFAR-10, CIFAR-100, and ImageNette) demonstrate that our method can significantly outperform other baselines in mitigating the robust fairness problem (+5-10\% on the worst class accuracy)


title: RAPOC : the Rosseland and Planck opacity converter. A user-friendly and fast opacity program for Python

abstract: RAPOC (Rosseland and Planck Opacity Converter) is a Python 3 code that calculates Rosseland and Planck mean opacities (RPMs) from wavelength-dependent opacities for a given temperature, pressure, and wavelength range. In addition to being user-friendly and rapid, RAPOC can interpolate between discrete data points, making it flexible and widely applicable to the astrophysical and Earth-sciences fields, as well as in engineering. For the input data, RAPOC can use ExoMol and DACE data, or any user-defined data, provided that it is in a readable format. In this paper, we present the RAPOC code and compare its calculated Rosseland and Planck mean opacities with other values found in the literature. The RAPOC code is open-source and available on Pypi and GitHub.


title: Wilson loops for 5d and 3d conformal linear quivers

abstract: Within the electrostatic formulation of holographic duals to (balanced) conformal quivers in five and three dimensions, we study Wilson loops in antisymmetric representations. We derive general expressions for various quantities participating in the formalism (VEV of Wilson loops, representation, gauge-node) and apply these to examples, connecting some results present in the bibliography. In the case of three dimensional quivers, we present a relation between Wilson loops in an 'electric' and in the 'magnetic/mirror' descriptions. In a very detailed appendix, we relate the electrostatic and holomorphic description of the holographic duals to these SCFTS.


title: The binary system of the spinning-top Be star Achernar

abstract: Achernar, the closest and brightest classical Be star, presents rotational flattening, gravity darkening, occasional emission lines due to a gaseous disk, and an extended polar wind. It is also a member of a close binary system with an early A-type dwarf companion. We aim to determine the orbital parameters of the Achernar system and to estimate the physical properties of the components. We monitored the relative position of Achernar B using a broad range of high angular resolution instruments of the VLT/VLTI (VISIR, NACO, SPHERE, AMBER, PIONIER, GRAVITY, and MATISSE) over a period of 13 years (2006-2019). These astrometric observations are complemented with a series of more than 700 optical spectra for the period from 2003 to 2016. We determine that Achernar B orbits the Be star on a seven-year period, eccentric orbit (e = 0.7255 +/- 0.0014) which brings the two stars within 2 au at periastron. The mass of the Be star is found to be mA = 6.0 +/- 0.6 Msun for a secondary mass of mB = 2.0 +/- 0.1 Msun. We find a good agreement of the parameters of Achernar A with the evolutionary model of a critically rotating star of 6.4 Msun at an age of 63 million years. We also identify a resolved comoving low-mass star, which leads us to propose that Achernar is a member of the Tucana-Horologium moving group. Achernar A is presently in a short-lived phase of its evolution following the turn-off, during which its geometrical flattening ratio is the most extreme. Considering the orbital parameters, no significant interaction occurred between the two components, demonstrating that Be stars may form through a direct, single-star evolution path without mass transfer. Since component A will enter the instability strip in a few hundred thousand years, Achernar appears to be a promising progenitor of the Cepheid binary systems.


title: Live to die another day: the rebrightening of AT2018fyk as a repeating partial tidal disruption event

abstract: Stars that interact with supermassive black holes (SMBHs) can either be completely or partially destroyed by tides. In a partial tidal disruption event (TDE) the high-density core of the star remains intact, and the low-density, outer envelope of the star is stripped and feeds a luminous accretion episode. The TDE AT2018fyk, with an inferred black hole mass of $10^{7.7\pm0.4}$ M$_{\odot}$, experienced an extreme dimming event at X-ray (factor of $>$6000) and UV (factor $\sim$15) wavelengths $\sim$500--600 days after discovery. Here we report on the re-emergence of these emission components roughly 1200 days after discovery. We find that the source properties are similar to those of the pre-dimming accretion state, suggesting that the accretion flow was rejuvenated to a similar state. We propose that a repeating partial TDE, where the partially disrupted star is on a $\sim 1200$ day orbit about the SMBH and is periodically stripped of mass during each pericenter passage, powers its unique lightcurve. This scenario provides a plausible explanation for AT2018fyk's overall properties, including the rapid dimming event and the rebrightening at late times. We also provide testable predictions for the behavior of the accretion flow in the future: if the second encounter was also a partial disruption then we predict another strong dimming event around day 1800 (August 2023), and a subsequent rebrightening around day 2400 (March 2025). This source provides strong evidence of the partial disruption of a star by a SMBH.


title: Origin and evolution of ultra-diffuse galaxies in different environments

abstract: We study the formation of ultra-diffuse galaxies (UDGs) using the cosmological hydrodynamical simulation TNG50 of the Illustris-TNG suite. We define UDGs as dwarf galaxies in the stellar mass range $\rm{7.5 \leq log (M_{\star} / M_{\odot}) \leq 9 }$ that are in the $5\%$ most extended tail of the simulated mass-size relation. This results in a sample of UDGs with half-mass radii $\rm{r_{h \star } \gtrsim 2 \ kpc}$ and surface brightness between $\rm{24.5}$ and $\rm{28 \ mag \ arcsec^{-2}}$, similar to definitions of UDGs in observations. The large cosmological volume in TNG50 allows for a comparison of UDGs properties in different environments, from the field to galaxy clusters with virial mass $\rm{M_{200} \sim 2 \times 10^{14} ~ M_{\odot}}$. All UDGs in our sample have dwarf-mass haloes ($\rm{M_{200}\sim 10^{11} ~ M_{\odot} }$) and show the same environmental trends as normal dwarfs: field UDGs are star-forming and blue while satellite UDGs are typically quiescent and red. The TNG50 simulation predicts UDGs that populate preferentially higher spin haloes and more massive haloes at fixed $\rm{M_{\star}}$ compared to non-UDG dwarfs. This applies also to most satellite UDGs, which are actually ``born" UDGs in the field and infall into groups and clusters without significant changes to their size. We find, however, a small subset of satellite UDGs ($\lesssim 10 \%$) with present-day stellar size a factor $\geq 1.5$ larger than at infall, confirming that tidal effects, particularly in the lower mass dwarfs, are also a viable formation mechanism for some of these dwarfs, although subdominant in this simulation.


title: Performance characterization and near-realtime monitoring of MUSE adaptive optics modes at Paranal

abstract: The Multi Unit Spectroscopic Explorer (MUSE) is an integral field spectrograph on the Very Large Telescope Unit Telescope 4, capable of laser guide star assisted and tomographic adaptive optics using the GALACSI module. Its observing capabilities include a wide field (1 square arcmin), ground layer AO mode (WFM-AO) and a narrow field (7.5"x7.5"), laser tomography AO mode (NFM-AO). The latter has had several upgrades in the 4 years since commissioning, including an optimisation of the control matrices for the AO system and a new sub-electron noise detector for its infra-red low order wavefront sensor. We set out to quantify the NFM-AO system performance by analysing $\sim$230 spectrophotometric standard star observations taken over the last 3 years. To this end we expand upon previous work, designed to facilitate analysis of the WFM-AO system performance. We briefly describe the framework that will provide a user friendly, semi-automated way for system performance monitoring during science operations. We provide the results of our performance analysis, chiefly through the measured Strehl ratio and full width at half maximum (FWHM) of the core of the point spread function (PSF) using two PSF models, and correlations with atmospheric conditions. These results will feed into a range of applications, including providing a more accurate prediction of the system performance as implemented in the exposure time calculator, and the associated optimization of the scientific output for a given set of limiting atmospheric conditions.


title: Improved Constraints on Dark Matter Annihilations Around Primordial Black Holes

abstract: Cosmology may give rise to appreciable populations of both particle dark matter and primordial black holes (PBH) with the combined mass density providing the observationally inferred value $\Omega_{\rm DM}\approx0.26$. However, previous studies have highlighted that scenarios with both particle dark matter and PBH are strongly excluded by $\gamma$-ray limits for particle dark matter with a velocity independent thermal cross section $\langle\sigma v\rangle\sim3\times10^{-26}{\rm cm}^3/{\rm s}$, as is the case for classic WIMP dark matter. Here we extend these existing studies on $s$-wave annihilating particle dark matter to ascertain the limits from diffuse $\gamma$-rays on velocity dependent annihilations which are $p$-wave with $\langle\sigma v \rangle\propto v^2$ or $d$-wave with $\langle\sigma v \rangle\propto v^4$, which we find to be considerably less constraining. Furthermore, we highlight that even if the freeze-out process is $p$-wave it is relatively common for (loop/phase-space) suppressed $s$-wave processes to actually provide the leading contributions to the experimentally constrained $\gamma$-ray flux from the PBH halo. This work also utilyses a refined treatment of the PBH dark matter density profile and outlines an improved application of extra-galactic $\gamma$-ray bounds.


title: Understanding of the properties of neural network approaches for transient light curve approximations

abstract: Modern-day time-domain photometric surveys collect a lot of observations of various astronomical objects and the coming era of large-scale surveys will provide even more information on their properties. Spectroscopic follow-ups are especially crucial for transients such as supernovae and most of these objects have not been subject to such studies. }{Flux time series are actively used as an affordable alternative for photometric classification and characterization, for instance, peak identifications and luminosity decline estimations. However, the collected time series are multidimensional and irregularly sampled, while also containing outliers and without any well-defined systematic uncertainties. This paper presents a search for the best-performing methods to approximate the observed light curves over time and wavelength for the purpose of generating time series with regular time steps in each passband.}{We examined several light curve approximation methods based on neural networks such as multilayer perceptrons, Bayesian neural networks, and normalizing flows to approximate observations of a single light curve. Test datasets include simulated PLAsTiCC and real Zwicky Transient Facility Bright Transient Survey light curves of transients.}{The tests demonstrate that even just a few observations are enough to fit the networks and improve the quality of approximation, compared to state-of-the-art models. The methods described in this work have a low computational complexity and are significantly faster than Gaussian processes. Additionally, we analyzed the performance of the approximation techniques from the perspective of further peak identification and transients classification. The study results have been released in an open and user-friendly Fulu Python library available on GitHub for the scientific community.


title: Interferometer Response to Geontropic Fluctuations

abstract: We model vacuum fluctuations in quantum gravity with a scalar field, characterized by a high occupation number, coupled to the metric. The occupation number of the scalar is given by a thermal density matrix, whose form is motivated by fluctuations in the vacuum energy, which have been shown to be conformal near a light-sheet horizon. For the experimental measurement of interest in an interferometer, the size of the energy fluctuations is fixed by the area of a surface bounding the volume of spacetime being interrogated by an interferometer. We compute the interferometer response to these "geontropic" scalar-metric fluctuations, and apply our results to current and future interferometer measurements, such as LIGO and the proposed GQuEST experiment.


title: Resonant Production of Light Sterile Neutrinos in Compact Binary Merger Remnants

abstract: The existence of eV-mass sterile neutrinos is not ruled out because of persistent experimental anomalies. Upcoming multi-messenger detections of neutron-star merger remnants could provide indirect constraints on the existence of these particles. We explore the active-sterile flavor conversion phenomenology in a two-flavor scenario (1 active + 1 sterile species) as a function of the sterile neutrino mixing parameters, neutrino emission angle from the accretion torus, and temporal evolution of the merger remnant. The torus geometry and the neutron richness of the remnant are responsible for the occurrence of multiple resonant active-sterile conversions. The number of resonances strongly depends on the neutrino emission direction above or inside the remnant torus and leads to large production of sterile neutrinos (and no antineutrinos) in the proximity of the polar axis as well as more sterile antineutrinos than neutrinos in the equatorial region. As the black hole torus evolves in time, the shallower baryon density is responsible for more adiabatic flavor conversion, leading to larger regions of the mass-mixing parameter space being affected by flavor mixing. Our findings imply that the production of sterile states could have indirect implications on the disk cooling rate, its outflows, and related electromagnetic observables which remain to be assessed.


title: Large Field Polynomial Inflation: Parameter Space, Predictions and (Double) Eternal Nature

abstract: Simple monomial inflationary scenarios have been ruled out by recent observations. In this work we revisit the next simplest scenario, a single--field model where the scalar potential is a polynomial of degree four which features a concave ``almost'' saddle point. We focus on trans--Planckian field values. We reparametrize the potential, which greatly simplifies the procedure for finding acceptbale model parameters. This allows for the first comprehensive scan of parameter space consistent with recent Planck and BICEP/Keck 2018 measurements. Even for trans--Planckian field values the tensor--to--scalar ratio $r$ can be as small as $\mathcal{O}(10^{-8})$, but the model can also saturate the current upper bound. In contrast to the small--field version of this model, radiative stability does not lead to strong constraints on the parameters of the inflaton potential. For very large field values the potential can be approximated by the quartic term; as well known, this allows eternal inflation even for field energy well below the reduced Planck mass $M_{\rm Pl}$, with Hubble parameter $H \sim 10^{-2} M_{\rm Pl}$. More interestingly, we find a region of parameter space that even supports {\em two phases of eternal inflation}. The second epoch only occurs if the slope at the would--be saddle point is very small, and has $H \sim 10^{-5} M_{\rm Pl}$; it can only be realized if $r \sim 10^{-2}$, within the sensitivity range of next--generation CMB observations.


title: WIMPs during Reheating

abstract: Weakly Interacting Massive Particles (WIMPs) are among the best-motivated dark matter candidates. In the standard scenario where the freeze-out occurs well after the end of inflationary reheating, they are in tension with the severe experimental constraints. Here, we investigate the thermal freeze-out of WIMPs occurring {\it during} reheating, while the inflaton $\phi$ coherently oscillates in a generic potential $\propto \phi^n$. Depending on the value of $n$ and the spin of the inflaton decaying products, the evolution of the radiation and inflaton energy densities can show distinct features, therefore, having a considerable impact on the freeze-out behavior of WIMPs. As a result of the injection of entropy during reheating, the parameter space compatible with the observed DM relic abundance is enlarged. In particular, the WIMP thermally averaged annihilation cross-section can be several magnitudes lower than that in the standard case. Finally, we discuss the current bounds from dark matter indirect detection experiments, and explore future challenges and opportunities.


title: One-Shot Synthesis of Images and Segmentation Masks

abstract: Joint synthesis of images and segmentation masks with generative adversarial networks (GANs) is promising to reduce the effort needed for collecting image data with pixel-wise annotations. However, to learn high-fidelity image-mask synthesis, existing GAN approaches first need a pre-training phase requiring large amounts of image data, which limits their utilization in restricted image domains. In this work, we take a step to reduce this limitation, introducing the task of one-shot image-mask synthesis. We aim to generate diverse images and their segmentation masks given only a single labelled example, and assuming, contrary to previous models, no access to any pre-training data. To this end, inspired by the recent architectural developments of single-image GANs, we introduce our OSMIS model which enables the synthesis of segmentation masks that are precisely aligned to the generated images in the one-shot regime. Besides achieving the high fidelity of generated masks, OSMIS outperforms state-of-the-art single-image GAN models in image synthesis quality and diversity. In addition, despite not using any additional data, OSMIS demonstrates an impressive ability to serve as a source of useful data augmentation for one-shot segmentation applications, providing performance gains that are complementary to standard data augmentation techniques. Code is available at https://github.com/ boschresearch/one-shot-synthesis


title: Open Set Recognition For Music Genre Classification

abstract: We explore segmentation of known and unknown genre classes using the open source GTZAN and FMA datasets. For each, we begin with best-case closed set genre classification, then we apply open set recognition methods. We offer an algorithm for the music genre classification task using OSR. We demonstrate the ability to retrieve known genres and as well identification of aural patterns for novel genres (not appearing in a training set). We conduct four experiments, each containing a different set of known and unknown classes, using the GTZAN and the FMA datasets to establish a baseline capacity for novel genre detection. We employ grid search on both OpenMax and softmax to determine the optimal total classification accuracy for each experimental setup, and illustrate interaction between genre labelling and open set recognition accuracy.


title: Magnetostatic boson stars

abstract: We solve the Einstein-Maxwell-Klein-Gordon system of equations and derive a compact, static axially symmetric magnetized object which is electrically neutral and made of two complex massive charged scalar fields. We describe several properties of such solution, including the torus form of the matter density and the expected dipolar distribution of the magnetic field, with some peculiar features in the central regions. The solution shows no divergencies in any of the field and metric functions. A discussion is presented on a case where the gravitational and magnetic fields in the external region are similar to those of neutron stars.


title: Human-level Atari 200x faster

abstract: The task of building general agents that perform well over a wide range of tasks has been an important goal in reinforcement learning since its inception. The problem has been subject of research of a large body of work, with performance frequently measured by observing scores over the wide range of environments contained in the Atari 57 benchmark. Agent57 was the first agent to surpass the human benchmark on all 57 games, but this came at the cost of poor data-efficiency, requiring nearly 80 billion frames of experience to achieve. Taking Agent57 as a starting point, we employ a diverse set of strategies to achieve a 200-fold reduction of experience needed to out perform the human baseline. We investigate a range of instabilities and bottlenecks we encountered while reducing the data regime, and propose effective solutions to build a more robust and efficient agent. We also demonstrate competitive performance with high-performing methods such as Muesli and MuZero. The four key components to our approach are (1) an approximate trust region method which enables stable bootstrapping from the online network, (2) a normalisation scheme for the loss and priorities which improves robustness when learning a set of value functions with a wide range of scales, (3) an improved architecture employing techniques from NFNets in order to leverage deeper networks without the need for normalization layers, and (4) a policy distillation method which serves to smooth out the instantaneous greedy policy overtime.


title: Three-wave mixing traveling-wave parametric amplifier with periodic variation of the circuit parameters

abstract: We report the implementation of a near-quantum-limited, traveling-wave parametric amplifier that uses three-wave mixing (3WM). To favor amplification by 3WM, we use the superconducting nonlinear asymmetric inductive element (SNAIL) loops, biased with a dc magnetic flux. In addition, we equip the device with dispersion engineering features to create a stop-band at the second harmonic of the pump and suppress the propagation of the higher harmonics that otherwise degrade the amplification. With a chain of 440 SNAILs, the amplifier provides up to 20 dB gain and a 3-dB bandwidth of 1 GHz. The added noise by the amplifier is found to be less than one photon.


title: MSREP: A Fast yet Light Sparse Matrix Framework for Multi-GPU Systems

abstract: Sparse linear algebra kernels play a critical role in numerous applications, covering from exascale scientific simulation to large-scale data analytics. Offloading linear algebra kernels on one GPU will no longer be viable in these applications, simply because the rapidly growing data volume may exceed the memory capacity and computing power of a single GPU. Multi-GPU systems nowadays being ubiquitous in supercomputers and data-centers present great potentials in scaling up large sparse linear algebra kernels. In this work, we design a novel sparse matrix representation framework for multi-GPU systems called MSREP, to scale sparse linear algebra operations based on our augmented sparse matrix formats in a balanced pattern. Different from dense operations, sparsity significantly intensifies the difficulty of distributing the computation workload among multiple GPUs in a balanced manner. We enhance three mainstream sparse data formats -- CSR, CSC, and COO, to enable fine-grained data distribution. We take sparse matrix-vector multiplication (SpMV) as an example to demonstrate the efficiency of our MSREP framework. In addition, MSREP can be easily extended to support other sparse linear algebra kernels based on the three fundamental formats (i.e., CSR, CSC and COO).


title: 3D-Patterned Inverse-Designed Mid-Infrared Metaoptics

abstract: Modern imaging systems can be enhanced in efficiency, compactness, and application through introduction of multilayer nanopatterned structures for manipulation of light based on its fundamental properties. High transmission efficiency multispectral imaging is surprisingly elusive due to the commonplace use of filter arrays which discard most of the incident light. Further, most cameras do not leverage the wealth of information in polarization and spatial degrees of freedom. Optical metamaterials can respond to these electromagnetic properties but have been explored primarily in single-layer geometries, limiting their performance and multifunctional capacity. Here we use advanced two-photon lithography to realize multilayer scattering structures that achieve highly nontrivial optical transformations intended to process light just before it reaches a focal plane array. Computationally optimized multispectral and polarimetric sorting devices are fabricated with submicron feature sizes and experimentally validated in the mid-infrared. A final structure shown in simulation redirects light based on its angular momentum. These devices demonstrate that with precise 3-dimensional nanopatterning, one can directly modify the scattering properties of a sensor array to create advanced imaging systems.


title: Detecting Planted Partition in Sparse Multi-Layer Networks

abstract: Multilayer networks are used to represent the interdependence between the relational data of individuals interacting with each other via different types of relationships. To study the information-theoretic phase transitions in detecting the presence of planted partition among the nodes of a multi-layer network with additional nodewise covariate information and diverging average degree, Ma and Nandy (2023) introduced Multi-Layer Contextual Stochastic Block Model. In this paper, we consider the problem of detecting planted partitions in the Multi-Layer Contextual Stochastic Block Model, when the average node degrees for each network is greater than $1$. We establish the sharp phase transition threshold for detecting the planted bi-partition. Above the phase-transition threshold testing the presence of a bi-partition is possible, whereas below the threshold no procedure to identify the planted bi-partition can perform better than random guessing. We further establish that the derived detection threshold coincides with the threshold for weak recovery of the partition and provide a quasi-polynomial time algorithm to estimate it.


title: Odd-parity perturbations in the most general scalar-vector-tensor theory

abstract: In the context of the most general scalar-vector-tensor theory, we study the stability of static spherically symmetric black holes under linear odd-parity perturbations. We calculate the action to second order in the linear perturbations to derive a master equation for these perturbations. For this general class of models, we obtain the conditions of no-ghost and Laplacian instability. Then, we study in detail the generalized Regge-Wheeler potential of particular cases to find their stability conditions.


title: ZeroEGGS: Zero-shot Example-based Gesture Generation from Speech

abstract: We present ZeroEGGS, a neural network framework for speech-driven gesture generation with zero-shot style control by example. This means style can be controlled via only a short example motion clip, even for motion styles unseen during training. Our model uses a Variational framework to learn a style embedding, making it easy to modify style through latent space manipulation or blending and scaling of style embeddings. The probabilistic nature of our framework further enables the generation of a variety of outputs given the same input, addressing the stochastic nature of gesture motion. In a series of experiments, we first demonstrate the flexibility and generalizability of our model to new speakers and styles. In a user study, we then show that our model outperforms previous state-of-the-art techniques in naturalness of motion, appropriateness for speech, and style portrayal. Finally, we release a high-quality dataset of full-body gesture motion including fingers, with speech, spanning across 19 different styles.


title: On Optimal Coverage of a Tree with Multiple Robots

abstract: We study the algorithmic problem of optimally covering a tree with $k$ mobile robots. The tree is known to all robots, and our goal is to assign a walk to each robot in such a way that the union of these walks covers the whole tree. We assume that the edges have the same length, and that traveling along an edge takes a unit of time. Two objective functions are considered: the cover time and the cover length. The cover time is the maximum time a robot needs to finish its assigned walk and the cover length is the sum of the lengths of all the walks. We also consider a variant in which the robots must rendezvous periodically at the same vertex in at most a certain number of moves. We show that the problem is different for the two cost functions. For the cover time minimization problem, we prove that the problem is NP-hard when $k$ is part of the input, regardless of whether periodic rendezvous are required or not. For the cover length minimization problem, we show that it can be solved in polynomial time when periodic rendezvous are not required, and it is NP-hard otherwise.


title: Fixed-Order H-Infinity Controller Design for Port-Hamiltonian Systems

abstract: We present a new fixed-order H-infinity controller design method for potentially large-scale port-Hamiltonian (pH) plants. Our method computes controllers that are also pH (and thus passive) such that the resulting closed-loop systems is again passive, which ensures closed-loop stability simply from the structure of the plant and controller matrices. In this way, we can avoid computationally expensive eigenvalue computations that would otherwise be necessary. In combination with a sample-based objective function which allows us to avoid multiple evaluations of the H-infinity norm (which is typically the main computational burden in fixed-order H-infinity controller synthesis), this makes our method well-suited for plants with a high state-space dimension. In our numerical experiments, we show that applying a passivity-enforcing post-processing step after using well-established H-infinity synthesis methods often leads to a deteriorated H-infinity performance. In constrast to that, our method computes pH controllers, that are automatically passive and simultaneously aim to minimize the H-infinity norm of the closed-loop transfer function. Moreover, our experiments show that for large-scale plants, our method is significantly faster than the well-established fixed-order H-infinity controller synthesis methods.


title: Snowmass 2021 Computational Frontier CompF03 Topical Group Report: Machine Learning

abstract: The rapidly-developing intersection of machine learning (ML) with high-energy physics (HEP) presents both opportunities and challenges to our community. Far beyond applications of standard ML tools to HEP problems, genuinely new and potentially revolutionary approaches are being developed by a generation of talent literate in both fields. There is an urgent need to support the needs of the interdisciplinary community driving these developments, including funding dedicated research at the intersection of the two fields, investing in high-performance computing at universities and tailoring allocation policies to support this work, developing of community tools and standards, and providing education and career paths for young researchers attracted by the intellectual vitality of machine learning for high energy physics.

categories: physics.comp-ph cs.AI hep-ex hep-lat hep-th


title: Event-Triggered Control for Discrete-Time Delay Systems

abstract: This study focuses on event-triggered control of nonlinear discrete-time systems with time delays. Based on a Lyapunov-Krasovskii type input-to-state stability result, we propose a novel event-triggered control algorithm that works as follows. The control inputs are updated only when a certain measurement error surpasses a dynamical threshold depending on both the system states and the evolution time. Sufficient conditions are established to ensure that the closed-loop system maintains its asymptotic stability. It is shown that the time-dependent portion in the dynamical threshold is essential to derive the lower bound of the times between two consecutive control updates. As a special case of our results, we demonstrate the performance of the designed event-triggering algorithm for a class of linear control systems with time delays. Numerical simulations are provided to demonstrate the effectiveness of our algorithm and theoretical results.


title: Multi-Pose Fusion for Sparse-View CT Reconstruction Using Consensus Equilibrium

abstract: CT imaging works by reconstructing an object of interest from a collection of projections. Traditional methods such as filtered-back projection (FBP) work on projection images acquired around a fixed rotation axis. However, for some CT problems, it is desirable to perform a joint reconstruction from projection data acquired from multiple rotation axes. In this paper, we present Multi-Pose Fusion, a novel algorithm that performs a joint tomographic reconstruction from CT scans acquired from multiple poses of a single object, where each pose has a distinct rotation axis. Our approach uses multi-agent consensus equilibrium (MACE), an extension of plug-and-play, as a framework for integrating projection data from different poses. We apply our method on simulated data and demonstrate that Multi-Pose Fusion can achieve a better reconstruction result than single pose reconstruction.


title: TwHIN-BERT: A Socially-Enriched Pre-trained Language Model for Multilingual Tweet Representations at Twitter

abstract: Pre-trained language models (PLMs) are fundamental for natural language processing applications. Most existing PLMs are not tailored to the noisy user-generated text on social media, and the pre-training does not factor in the valuable social engagement logs available in a social network. We present TwHIN-BERT, a multilingual language model productionized at Twitter, trained on in-domain data from the popular social network. TwHIN-BERT differs from prior pre-trained language models as it is trained with not only text-based self-supervision, but also with a social objective based on the rich social engagements within a Twitter heterogeneous information network (TwHIN). Our model is trained on 7 billion tweets covering over 100 distinct languages, providing a valuable representation to model short, noisy, user-generated text. We evaluate our model on various multilingual social recommendation and semantic understanding tasks and demonstrate significant metric improvement over established pre-trained language models. We open-source TwHIN-BERT and our curated hashtag prediction and social engagement benchmark datasets to the research community.


title: The emergence of a virus variant: dynamics of a competition model with cross-immunity time-delay validated by wastewater surveillance data for COVID-19

abstract: We consider the dynamics of a virus spreading through a population that produces a mutant strain with the ability to infect individuals that were infected with the established strain. Temporary cross-immunity is included using a time delay, but is found to be a harmless delay. We provide some sufficient conditions that guarantee local and global asymptotic stability of the disease-free equilibrium and the two boundary equilibria when the two strains outcompete one another. It is shown that, due to the immune evasion of the emerging strain, the reproduction number of the emerging strain must be significantly lower than that of the established strain for the local stability of the established-strain-only boundary equilibrium. To analyze the unique coexistence equilibrium we apply a quasi steady-state argument to reduce the full model to a two-dimensional one that exhibits a global asymptotically stable established-strain-only equilibrium or global asymptotically stable coexistence equilibrium. Our results indicate that the basic reproduction numbers of both strains govern the overall dynamics, but in nontrivial ways due to the inclusion of cross-immunity. The model is applied to study the emergence of the SARS-CoV-2 Delta variant in the presence of the Alpha variant using wastewater surveillance data from the Deer Island Treatment Plant in Massachusetts, USA.


title: Direct vs Indirect Methods for Behavior-based Attack Detection

abstract: We study the problem of data-driven attack detection for unknown LTI systems using only input-output behavioral data. In contrast with model-based detectors that use errors from an output predictor to detect attacks, we study behavior-based data-driven detectors. We construct a behavior-based chi-squared detector that uses a sequence of inputs and outputs and their covariance. The covariance of the behaviors is estimated using data by two methods. The first (direct) method employs the sample covariance as an estimate of the covariance of behaviors. The second (indirect) method uses a lower dimensional generative model identified from data to estimate the covariance of behaviors. We prove the consistency of the two methods of estimation and provide finite sample error bounds. Finally, we numerically compare the performance and establish a tradeoff between the methods at different regimes of the size of the data set and the length of the detection horizon. Our numerical study indicates that neither method is invariable superior, and reveals the existence of two regimes for the performance of the two methods, wherein the direct method is superior in cases with large data sets relative to the length of the detection horizon, while the indirect method is superior in cases with small data sets.


title: Probing a light dark sector at future lepton colliders via invisible decays of the SM-like and dark Higgs bosons

abstract: A renormalizable UV model for Axion-Like Particles (ALPs) or hidden photons, that may explain the dark matter usually involves a dark Higgs field which is a singlet under the standard model (SM) gauge group. The dark sector can couple to the SM particles via the portal coupling between the SM-like Higgs and dark Higgs fields. Through this coupling, the dark sector particles can be produced in either the early universe or the collider experiments. Interestingly, not only the SM-like Higgs boson can decay into the light dark bosons, but also a light dark Higgs boson may be produced and decay into the dark bosons in a collider. In this paper, we perform the first collider search for invisible decays by taking both the Higgs bosons into account. We use a multivariate technique to best discriminate the signal from the background. We find that a large parameter region can be {probed} at the International Linear Collider (ILC) operating at the center-of-mass energy of 250 GeV. In particular, even when the SM-like Higgs invisible decay is a few orders of magnitude below the planned sensitivity reaches of the ILC and the high luminosity LHC (HL-LHC), the scenario can be probed by the invisible decay of the dark Higgs boson produced via a similar diagram. Measuring the dark Higgs boson decay into the dark sector will be a smoking gun signal of the light dark sector. A similar search of the dark sector would be expected in, e.g., Cool Copper Collider (C$^3$), Circular Electron Positron Collider (CEPC), Compact Linear Collider (CLIC) and {Future Circular electron-positron Collider (FCC-ee).


title: Variability due to climate and chemistry in observations of oxygenated Earth-analogue exoplanets

abstract: The Great Oxidation Event was a period during which Earth's atmospheric oxygen (O$_2$) concentrations increased from $\sim 10^{-5}$ times its present atmospheric level (PAL) to near modern levels, marking the start of the Proterozoic geological eon 2.4 billion years ago. Using WACCM6, an Earth System Model, we simulate the atmosphere of Earth-analogue exoplanets with O$_2$ mixing ratios between 0.1% and 150% PAL. Using these simulations, we calculate the reflection/emission spectra over multiple orbits using the Planetary Spectrum Generator. We highlight how observer angle, albedo, chemistry, and clouds affect the simulated observations. We show that inter-annual climate variations, as well short-term variations due to clouds, can be observed in our simulated atmospheres with a telescope concept such as LUVOIR or HabEx. Annual variability and seasonal variability can change the planet's reflected flux (including the reflected flux of key spectral features such as O$_2$ and H$_2$O) by up to factors of 5 and 20, respectively, for the same orbital phase. This variability is best observed with a high-throughput coronagraph. For example, HabEx (4 m) with a starshade performs up to a factor of two times better than a LUVOIR B (6 m) style telescope. The variability and signal-to-noise ratio of some spectral features depends non-linearly on atmospheric O$_2$ concentration. This is caused by temperature and chemical column depth variations, as well as generally increased liquid and ice cloud content for atmospheres with O$_2$ concentrations of $<$1% PAL.


title: Prediction of $\textrm{CO}_2$ Adsorption in Nano-Pores with Graph Neural Networks

abstract: We investigate the graph-based convolutional neural network approach for predicting and ranking gas adsorption properties of crystalline Metal-Organic Framework (MOF) adsorbents for application in post-combustion capture of $\textrm{CO}_2$. Our model is based solely on standard structural input files containing atomistic descriptions of the adsorbent material candidates. We construct novel methodological extensions to match the prediction accuracy of classical machine learning models that were built with hundreds of features at much higher computational cost. Our approach can be more broadly applied to optimize gas capture processes at industrial scale.


title: Physically Constrained Generative Adversarial Networks for Improving Precipitation Fields from Earth System Models

abstract: Precipitation results from complex processes across many scales, making its accurate simulation in Earth system models (ESMs) challenging. Existing post-processing methods can improve ESM simulations locally, but cannot correct errors in modelled spatial patterns. Here we propose a framework based on physically constrained generative adversarial networks (GANs) to improve local distributions and spatial structure simultaneously. We apply our approach to the computationally efficient ESM CM2Mc-LPJmL. Our method outperforms existing ones in correcting local distributions, and leads to strongly improved spatial patterns especially regarding the intermittency of daily precipitation. Notably, a double-peaked Intertropical Convergence Zone, a common problem in ESMs, is removed. Enforcing a physical constraint to preserve global precipitation sums, the GAN can generalize to future climate scenarios unseen during training. Feature attribution shows that the GAN identifies regions where the ESM exhibits strong biases. Our method constitutes a general framework for correcting ESM variables and enables realistic simulations at a fraction of the computational costs.


title: FlexER: Flexible Entity Resolution for Multiple Intents

abstract: Entity resolution, a longstanding problem of data cleaning and integration, aims at identifying data records that represent the same real-world entity. Existing approaches treat entity resolution as a universal task, assuming the existence of a single interpretation of a real-world entity and focusing only on finding matched records, separating corresponding from non-corresponding ones, with respect to this single interpretation. However, in real-world scenarios, where entity resolution is part of a more general data project, downstream applications may have varying interpretations of real-world entities relating, for example, to various user needs. In what follows, we introduce the problem of multiple intents entity resolution (MIER), an extension to the universal (single intent) entity resolution task. As a solution, we propose FlexER, utilizing contemporary solutions to universal entity resolution tasks to solve multiple intents entity resolution. FlexER addresses the problem as a multi-label classification problem. It combines intent-based representations of tuple pairs using a multiplex graph representation that serves as an input to a graph neural network (GNN). FlexER learns intent representations and improves the outcome to multiple resolution problems. A large-scale empirical evaluation introduces a new benchmark and, using also two well-known benchmarks, shows that FlexER effectively solves the MIER problem and outperforms the state-of-the-art for a universal entity resolution.


title: Non-perturbative Solution of the 1d Schrodinger Equation Describing Photoemission from a Sommerfeld model Metal by an Oscillating Field

abstract: We analyze non-perturbatively the one-dimensional Schr\"odinger equation describing the emission of electrons from a model metal surface by a classical oscillating electric field. Placing the metal in the half-space $x\leqslant 0$, the Schr\"odinger equation of the system is $i\partial_t\psi=-\frac12\partial_x^2\psi+\Theta(x) (U-E x \cos\omega t)\psi$, $t>0$, $x\in\mathbb R$, where $\Theta(x)$ is the Heaviside function and $U>0$ is the effective confining potential (we choose units so that $m=e=\hbar=1$). The amplitude $E$ of the external electric field and the frequency $\omega$ are arbitrary. We prove existence and uniqueness of classical solutions of this equation for general initial conditions $\psi(x,0)=f(x)$, $x\in\mathbb R$. When the initial condition is in $L^2$ the evolution is unitary and the wave function goes to zero at any fixed $x$ as $t\to\infty$. To show this we prove a RAGE type theorem and show that the discrete spectrum of the quasienergy operator is empty. To obtain positive electron current we consider non-$L^2$ initial conditions containing an incoming beam from the left. The beam is partially reflected and partially transmitted for all $t>0$. For these we show that the solution approaches in the large $t$ limit a periodic state that satisfies an infinite set of equations formally derived by Faisal, et. al. Due to a number of pathological features of the Hamiltonian (among which unboundedness in the physical as well as the spatial Fourier domain) the existing methods to prove such results do not apply, and we introduce new, more general ones. The actual solution exhibits a very complex behavior. It shows a steep increase in the current as the frequency passes a threshold value $\omega=\omega_c$, with $\omega_c$ depending on the strength of the electric field. For small $E$, $\omega_c$ represents the threshold in the classical photoelectric effect.


title: Formulating Oscillator-Inspired Dynamical Systems to Solve Boolean Satisfiability

abstract: Dynamical systems can offer a novel non-Boolean approach to computing. Specifically, the natural minimization of energy in the system is a valuable property for minimizing the objective functions of combinatorial optimization problems, many of which are still challenging to solve using conventional digital solvers. In this work, we formulate two oscillator-inspired dynamical systems to solve quintessential computationally intractable problems in Boolean satisfiability (SAT). The system dynamics are engineered such that they facilitate solutions to two different flavors of the SAT problem. We formulate the first dynamical system to compute the solution to the 3-SAT problem, while for the second system, we show that its dynamics map to the solution of the Max-NAE-3-SAT problem. Our work advances understanding of how this physics-inspired approach can be used to address challenging problems in computing.


title: Power to the People? Opportunities and Challenges for Participatory AI

abstract: Participatory approaches to artificial intelligence (AI) and machine learning (ML) are gaining momentum: the increased attention comes partly with the view that participation opens the gateway to an inclusive, equitable, robust, responsible and trustworthy AI.Among other benefits, participatory approaches are essential to understanding and adequately representing the needs, desires and perspectives of historically marginalized communities. However, there currently exists lack of clarity on what meaningful participation entails and what it is expected to do. In this paper we first review participatory approaches as situated in historical contexts as well as participatory methods and practices within the AI and ML pipeline. We then introduce three case studies in participatory AI.Participation holds the potential for beneficial, emancipatory and empowering technology design, development and deployment while also being at risk for concerns such as cooptation and conflation with other activities. We lay out these limitations and concerns and argue that as participatory AI/ML becomes in vogue, a contextual and nuanced understanding of the term as well as consideration of who the primary beneficiaries of participatory activities ought to be constitute crucial factors to realizing the benefits and opportunities that participation brings.


title: Evolution of electronic and magnetic properties of Sr$\mathbf{_2}$IrO$\mathbf{_4}$ under strain

abstract: Motivated by properties-controlling potential of the strain, we investigate strain dependence of structure, electronic and magnetic properties of Sr$_2$IrO$_4$ using complementary theoretical tools: {\it ab-initio} calculations, analytical approaches (rigid octahedra picture, Slater-Koster integrals), and extended $t-{\mathcal{J}}$ model. We find that strain affects both Ir-Ir distance and Ir-O-Ir angle, and the rigid octahedra picture is not relevant. Second, we find fundamentally different behavior for compressive and tensile strain. One remarkable feature is the formation of two subsets of bond- and orbital- dependent carriers, a compass-like model, under compression. This originates from the strain-induced renormalization of the Ir-O-Ir superexchange and O on-site energy. We also show that under compressive (tensile) strain, Fermi surface becomes highly dispersive (relatively flat). Already at a tensile strain of $1.5\%$, we observe spectral weight redistribution, with the low-energy band acquiring almost purely singlet character. These results can be directly compared with future experiments.


title: Towards a Better Microcredit Decision

abstract: Reject inference comprises techniques to infer the possible repayment behavior of rejected cases. In this paper, we model credit in a brand new view by capturing the sequential pattern of interactions among multiple stages of loan business to make better use of the underlying causal relationship. Specifically, we first define 3 stages with sequential dependence throughout the loan process including credit granting(AR), withdrawal application(WS) and repayment commitment(GB) and integrate them into a multi-task architecture. Inside stages, an intra-stage multi-task classification is built to meet different business goals. Then we design an Information Corridor to express sequential dependence, leveraging the interaction information between customer and platform from former stages via a hierarchical attention module controlling the content and size of the information channel. In addition, semi-supervised loss is introduced to deal with the unobserved instances. The proposed multi-stage interaction sequence(MSIS) method is simple yet effective and experimental results on a real data set from a top loan platform in China show the ability to remedy the population bias and improve model generalization ability.


title: A Nested Genetic Algorithm for Explaining Classification Data Sets with Decision Rules

abstract: Our goal in this paper is to automatically extract a set of decision rules (rule set) that best explains a classification data set. First, a large set of decision rules is extracted from a set of decision trees trained on the data set. The rule set should be concise, accurate, have a maximum coverage and minimum number of inconsistencies. This problem can be formalized as a modified version of the weighted budgeted maximum coverage problem, known to be NP-hard. To solve the combinatorial optimization problem efficiently, we introduce a nested genetic algorithm which we then use to derive explanations for ten public data sets.


title: Open-Full-Jaw: An open-access dataset and pipeline for finite element models of human jaw

abstract: Developing computational models of the human jaw acquired from cone-beam computed tomography (CBCT) scans is time-consuming and labor-intensive. Besides, a quantitative comparison is not attainable in the literature due to the involved manual tasks and the lack of surface/volumetric meshes. We share an open-access repository of 17 patient-specific finite-element (FE) models of human jaws acquired from CBCT scans and the utilized pipeline for generating them. The proposed pipeline minimizes model generation time and potential errors caused by human interventions. It gets dense surface meshes and provides reduced conformal surface/volumetric meshes suitable for FE analysis. We have quantified the geometrical variations of developed models and assessed models' accuracy from different aspects; (1) the maximum deviations from the input meshes, (2) the mesh quality, and (3) the simulation results. Our results indicate that the developed computational models are precise and have quality meshes suitable for various FE scenarios. Therefore, we believe this dataset will pave the way for future population studies.


title: Experimental verification of the quantum nature of a neural network

abstract: Neural networks are being used to improve the probing of the state spaces of many particle systems as approximations to wavefunctions and in order to avoid the recurring sign problem of quantum monte-carlo. One may ask whether the usual classical neural networks have some actual hidden quantum properties that make them such suitable tools for a highly coupled quantum problem. I discuss here what makes a system quantum and to what extent we can interpret a neural network as having quantum remnants. I suggest that a system can be quantum both due to its fundamental quantum constituents and due to the rules of its functioning, therefore, we can obtain entanglement both due to the quantum constituents' nature and due to the functioning rules, or, in category theory terms, both due to the quantum nature of the objects of a category and of the maps. From a practical point of view, I suggest a possible experiment that could extract entanglement from the quantum functioning rules (maps) of an otherwise classical (from the point of view of the constituents) neural network.


title: Pixel-wise classification in graphene-detection with tree-based machine learning algorithms

abstract: Mechanical exfoliation of graphene and its identification by optical inspection is one of the milestones in condensed matter physics that sparked the field of 2D materials. Finding regions of interest from the entire sample space and identification of layer number is a routine task potentially amenable to automatization. We propose supervised pixel-wise classification methods showing a high performance even with a small number of training image datasets that require short computational time without GPU. We introduce four different tree-based machine learning algorithms -- decision tree, random forest, extreme gradient boost, and light gradient boosting machine. We train them with five optical microscopy images of graphene, and evaluate their performances with multiple metrics and indices. We also discuss combinatorial machine learning models between the three single classifiers and assess their performances in identification and reliability. The code developed in this paper is open to the public and will be released at github.com/gjung-group/Graphene_segmentation.


title: On the Edges of Characteristic Imset Polytopes

abstract: The edges of the characteristic imset polytope, $\operatorname{CIM}_p$, were recently shown to have strong connections to causal discovery as many algorithms could be interpreted as greedy restricted edge-walks, even though only a strict subset of the edges are known. To better understand the general edge structure of the polytope we describe the edge structure of faces with a clear combinatorial interpretation: for any undirected graph $G$ we have the face $\operatorname{CIM}_G$, the convex hull of the characteristic imsets of DAGs with skeleton $G$. We give a full edge-description of $\operatorname{CIM}_G$ when $G$ is a tree, leading to interesting connections to other polytopes. In particular the well-studied stable set polytope can be recovered as a face of $\operatorname{CIM}_G$ when $G$ is a tree. Building on this connection we are also able to give a description of all edges of $\operatorname{CIM}_G$ when $G$ is a cycle, suggesting possible inroads for generalization. We then introduce an algorithm for learning directed trees from data, utilizing our newly discovered edges, that outperforms classical methods on simulated Gaussian data.


title: Exploring the Tradeoff between Competitive Ratio and Variance in Online-Matching Markets

abstract: In this paper, we propose an online-matching-based model to study the assignment problems arising in a wide range of online-matching markets, including online recommendations, ride-hailing platforms, and crowdsourcing markets. It features that each assignment can request a random set of resources and yield a random utility, and the two (cost and utility) can be arbitrarily correlated with each other. We present two linear-programming-based parameterized policies to study the tradeoff between the \emph{competitive ratio} (CR) on the total utilities and the \emph{variance} on the total number of matches (unweighted version). The first one (SAMP) is to sample an edge according to the distribution extracted from the clairvoyant optimal, while the second (ATT) features a time-adaptive attenuation framework that leads to an improvement over the state-of-the-art competitive-ratio result. We also consider the problem under a large-budget assumption and show that SAMP achieves asymptotically optimal performance in terms of competitive ratio.