Search

We study the reachability problem for one-counter automata in which transitions can carry disequality tests. A disequality test is a guard that prohibits a specified counter value. This reachability problem has been known to be NP-hard and in PSPACE, and characterising its computational complexity has been left as a challenging open question by Almagor, Cohen, P\'erez, Shirmohammadi, and Worrell (2020). We reduce the complexity gap, placing the problem into the second level of the polynomial hierarchy, namely into the class $\mathsf{coNP}^{\mathsf{NP}}$. In the presence of both equality and disequality tests, our upper bound is at the third level, $\mathsf{P}^{\mathsf{NP}^{\mathsf{NP}}}$. To prove this result, we show that non-reachability can be witnessed by a pair of invariants (forward and backward). These invariants are almost inductive. They aim to over-approximate only a "core" of the reachability set instead of the entire set. The invariants are also leaky: it is possible to escape the set. We complement this with separate checks as the leaks can only occur in a controlled way., Comment: Extended version of CONCUR 2024 paper

This paper presents a comprehensive study and implementations onto FPGA device of an Expectation Propagation (EP)-based receiver for QPSK, 8-PSK, and 16-QAM. To the best of our knowledge, this is the first for this kind of receiver. The receiver implements a Frequency Domain (FD) Self-Iterated Linear Equalizer (SILE), where EP is used to approximate the true posterior distribution of the transmitted symbols with a simpler distribution. Analytical approximations for the EP feedback generation process and the three constellations are applied to lessen the complexity of the soft mapper/demapper architectures. The simulation results demonstrate that the fixed-point version performs comparably to the floating-point. Moreover, implementation results show the efficiency in terms of FPGA resource usage of the proposed architecture.

Predicting the timing and occurrence of events is a major focus of data science applications, especially in the context of biomedical research. Performance for models estimating these outcomes, often referred to as time-to-event or survival outcomes, is frequently summarized using measures of discrimination, in particular time-dependent AUC and concordance. Many estimators for these quantities have been proposed which can be broadly categorized as either semi-parametric estimators or non-parametric estimators. In this paper, we review various estimators' mathematical construction and compare the behavior of the two classes of estimators. Importantly, we identify a previously unknown feature of the class of semi-parametric estimators that can result in vastly over-optimistic out-of-sample estimation of discriminative performance in common applied tasks. Although these semi-parametric estimators are popular in practice, the phenomenon we identify here suggests this class of estimators may be inappropriate for use in model assessment and selection based on out-of-sample evaluation criteria. This is due to the semi-parametric estimators' bias in favor of models that are overfit when using out-of-sample prediction criteria (e.g., cross validation). Non-parametric estimators, which do not exhibit this behavior, are highly variable for local discrimination. We propose to address the high variability problem through penalized regression splines smoothing. The behavior of various estimators of time-dependent AUC and concordance are illustrated via a simulation study using two different mechanisms that produce over-optimistic out-of-sample estimates using semi-parametric estimators. Estimators are further compared using a case study using data from the National Health and Nutrition Examination Survey (NHANES) 2011-2014.

Mitigating bias in machine learning models is a critical endeavor for ensuring fairness and equity. In this paper, we propose a novel approach to address bias by leveraging pixel image attributions to identify and regularize regions of images containing significant information about bias attributes. Our method utilizes a model-agnostic approach to extract pixel attributions by employing a convolutional neural network (CNN) classifier trained on small image patches. By training the classifier to predict a property of the entire image using only a single patch, we achieve region-based attributions that provide insights into the distribution of important information across the image. We propose utilizing these attributions to introduce targeted noise into datasets with confounding attributes that bias the data, thereby constraining neural networks from learning these biases and emphasizing the primary attributes. Our approach demonstrates its efficacy in enabling the training of unbiased classifiers on heavily biased datasets., Comment: Accepted to the 2024 IEEE CVPR Workshop on Fair, Data-efficient, and Trusted Computer Vision

Motivated by the problem of compressing point sets into as few bits as possible while maintaining information about approximate distances between points, we construct random nonlinear maps $\varphi_\ell$ that compress point sets in the following way. For a point set $S$, the map $\varphi_\ell:\mathbb{R}^d \to N^{-1/2}\{-1,1\}^N$ has the property that storing $\varphi_\ell(S)$ (a \emph{sketch} of $S$) allows one to report pairwise squared distances between points in $S$ up to some multiplicative $(1\pm \epsilon)$ error with high probability as long as the minimum distance is not too small compared to $\epsilon$. The maps $\varphi_\ell$ are the $\ell$-fold composition of a certain type of random feature mapping. Moreover, we determine how large $N$ needs to be as a function of $\epsilon$ and other parameters of the point set. Compared to existing techniques, our maps offer several advantages. The standard method for compressing point sets by random mappings relies on the Johnson-Lindenstrauss lemma which implies that if a set of $n$ points is mapped by a Gaussian random matrix to $\mathbb{R}^k$ with $k =\Theta(\epsilon^{-2}\log n)$, then pairwise distances between points are preserved up to a multiplicative $(1\pm \epsilon)$ error with high probability. The main advantage of our maps $\varphi_\ell$ over random linear maps is that ours map point sets directly into the discrete cube $N^{-1/2}\{-1,1\}^N$ and so there is no additional step needed to convert the sketch to bits. For some range of parameters, our maps $\varphi_\ell$ produce sketches which require fewer bits of storage space.

Symbolic regression (SR) searches for analytical expressions representing the relationship between a set of explanatory and response variables. Current SR methods assume a single dataset extracted from a single experiment. Nevertheless, frequently, the researcher is confronted with multiple sets of results obtained from experiments conducted with different setups. Traditional SR methods may fail to find the underlying expression since the parameters of each experiment can be different. In this work we present Multi-View Symbolic Regression (MvSR), which takes into account multiple datasets simultaneously, mimicking experimental environments, and outputs a general parametric solution. This approach fits the evaluated expression to each independent dataset and returns a parametric family of functions f(x; theta) simultaneously capable of accurately fitting all datasets. We demonstrate the effectiveness of MvSR using data generated from known expressions, as well as real-world data from astronomy, chemistry and economy, for which an a priori analytical expression is not available. Results show that MvSR obtains the correct expression more frequently and is robust to hyperparameters change. In real-world data, it is able to grasp the group behavior, recovering known expressions from the literature as well as promising alternatives, thus enabling the use of SR to a large range of experimental scenarios., Comment: Accepted to GECCO-2024. 11 pages, 5 figures

With the increased energy demands of the 21st century, there is a clear need for developing a more sustainable method of energy generation, distribution, and transmission. The popularity of Smart Grid continues to grow as it presents its benefits, including interconnectivity, improved efficiency, the ability to integrate renewable energy sources, and many more. However, it is not without its challenges. This survey aims to provide an introductory background of smart grids, detail some of the main aspects and current challenges, and review the most recent papers and proposed solutions. It will also highlight the current state of implementation of the smart grid by describing various prototypes, as well as various countries and continents implementation plans and projects., Comment: Paper has been submitted for review to the journal Energy Reports (January 23, 2024). 58 pages, 7 figures, 7 tables

We present highly sampled photometry of the supernova (SN) 2023ixf, a Type II SN in M101, beginning 2 days before its first known detection. To gather these data, we enlisted the global Unistellar Network of citizen scientists. These 252 observations from 115 telescopes show the SN's rising brightness associated with shock emergence followed by gradual decay. We measure a peak $M_{V}$ = -18.18 $\pm$ 0.09 mag at 2023-05-25 21:37 UTC in agreement with previously published analyses., Comment: 4 pages, 1 figure

The alignment of autonomous agents with human values is a pivotal challenge when deploying these agents within physical environments, where safety is an important concern. However, defining the agent's objective as a reward and/or cost function is inherently complex and prone to human errors. In response to this challenge, we present a novel approach that leverages one-class decision trees to facilitate learning from expert demonstrations. These decision trees provide a foundation for representing a set of constraints pertinent to the given environment as a logical formula in disjunctive normal form. The learned constraints are subsequently employed within an oracle constrained reinforcement learning framework, enabling the acquisition of a safe policy. In contrast to other methods, our approach offers an interpretable representation of the constraints, a vital feature in safety-critical environments. To validate the effectiveness of our proposed method, we conduct experiments in synthetic benchmark domains and a realistic driving environment., Comment: accepted for AAAI 2024 Workshop on Neuro-Symbolic Learning and Reasoning in the Era of Large Language Models (NucLeaR)

The amount of Adaptive Optics (AO) telemetry generated by VIS/NIR ground-based observatories is ever greater, leading to a growing need for a standardised data exchange format to support performance analysis and AO research and development activities that involve large-scale telemetry mining, processing, and curation. This paper introduces the Adaptive Optics Telemetry (AOT) data exchange format as a standard for sharing AO telemetry from visible/infrared ground-based observatories. AOT is based on the Flexible Image Transport System (FITS) and aims to provide unambiguous and consistent data access across various systems and configurations, including natural and single/multiple laser guide-star AO systems. We designed AOT focused on two key use cases: atmospheric turbulence parameter estimation and point-spread function reconstruction (PSF-R). We prototyped and tested the design using existing AO telemetry datasets from multiple systems: single conjugate with natural and laser guide stars, tomographic systems with multi-channel wavefront sensors, single and multi wavefront correctors in systems featuring either a Shack-Hartmann or Pyramid as main wavefront sensors. The AOT file structure has been thoroughly defined, specifying data fields, descriptions, data types, units, and expected dimensions. To support this format, we have developed a Python package that enables data conversion, reading, writing and exploration of AOT files, which has been made publicly available and compatible with a general-purpose Python package manager. We demonstrate the flexibility of the AOT format by packaging data from five different instruments, installed on different telescopes.

Between 2011 and 2014 NHANES collected objectively measured physical activity data using wrist-worn accelerometers for tens of thousands of individuals for up to seven days. Here we analyze the minute-level indicators of being active, which can be viewed as binary (because there is an active indicator at every minute), multilevel (because there are multiple days of data for each study participant), functional (because within-day data can be viewed as a function of time) data. To extract within- and between-participant directions of variation in the data, we introduce Generalized Multilevel Functional Principal Component Analysis (GM-FPCA), an approach based on the dimension reduction of the linear predictor. Scores associated with specific patterns of activity are shown to be strongly associated with time to death. Extensive simulation studies indicate that GM-FPCA provides accurate estimation of model parameters, is computationally stable, and is scalable in the number of study participants, visits, and observations within visits. R code for implementing the method is provided.

We investigate the dimension-parametric complexity of the reachability problem in vector addition systems with states (VASS) and its extension with pushdown stack (pushdown VASS). Up to now, the problem is known to be $\mathcal{F}_k$-hard for VASS of dimension $3k+2$ (the complexity class $\mathcal{F}_k$ corresponds to the $k$th level of the fast-growing hierarchy), and no essentially better bound is known for pushdown VASS. We provide a new construction that improves the lower bound for VASS: $\mathcal{F}_k$-hardness in dimension $2k+3$. Furthermore, building on our new insights we show a new lower bound for pushdown VASS: $\mathcal{F}_k$-hardness in dimension $\frac k 2 + 4$. This dimension-parametric lower bound is strictly stronger than the upper bound for VASS, which suggests that the (still unknown) complexity of the reachability problem in pushdown VASS is higher than in plain VASS (where it is Ackermann-complete).

We consider the problem of predicting an individual's identity from accelerometry data collected during walking. In a previous paper we introduced an approach that transforms the accelerometry time series into an image by constructing its complete empirical autocorrelation distribution. Predictors derived by partitioning this image into grid cells were used in logistic regression to predict individuals. Here we: (1) implement machine learning methods for prediction using the grid cell-derived predictors; (2) derive inferential methods to screen for the most predictive grid cells; and (3) develop a novel multivariate functional regression model that avoids partitioning of the predictor space into cells. Prediction methods are compared on two open source data sets: (1) accelerometry data collected from $32$ individuals walking on a $1.06$ kilometer path; and (2) accelerometry data collected from six repetitions of walking on a $20$ meter path on two separate occasions at least one week apart for $153$ study participants. In the $32$-individual study, all methods achieve at least $95$% rank-1 accuracy, while in the $153$-individual study, accuracy varies from $41$% to $98$%, depending on the method and prediction task. Methods provide insights into why some individuals are easier to predict than others., Comment: 37 pages, 6 figures, 2 tables. Submitted to Journal of the American Statistical Association

Let $\mu$ be a probability distribution on $\mathbb{R}^d$ which assigns measure zero to every hyperplane and $S$ a set of points sampled independently from $\mu$. What can be said about the expected combinatorial structure of the convex hull of $S$? These polytopes are simplicial with probability one, but not much else is known except when more restrictive assumptions are imposed on $\mu$. In this paper we show that, with probability close to one, the convex hull of $S$ has a high degree of neighborliness no matter the underlying distribution $\mu$ as long as $n$ is not much bigger than $d$. As a concrete example, our result implies that if for each $d$ in $\mathbb{N}$ we choose a probability distribution $\mu_d$ on $\mathbb{R}^d$ which assigns measure zero to every hyperplane and then set $P_n$ to be the convex hull of an i.i.d. sample of $n \le 5d/4$ random points from $\mu_d$, the probability that $P_n$ is $k$-neighborly approaches one as $d \to \infty$ for all $k\le d/20$. We also give a simple example of a family of distributions which essentially attain our lower bound on the $k$-neighborliness of a random polytope.

Gaussian random polytopes have received a lot of attention especially in the case where the dimension is fixed and the number of points goes to infinity. Our focus is on the less studied case where the dimension goes to infinity and the number of points is proportional to the dimension $d$. We study several natural quantities associated to Gaussian random polytopes in this setting. First, we show that the expected number of facets is equal to $C(\alpha)^{d+o(d)}$ where $C(\alpha)$ is some constant which depends on the constant of proportionality $\alpha$. We also extend this result to the expected number of $k$-facets. We then consider the more difficult problem of the asymptotics of the expected number of pairs of $\textit{estranged facets}$ of a Gaussian random polytope. When $n=2d$, we determined the constant $C$ so that the expected number of pairs of estranged facets is equal to $C^{d+o(d)}$.

The Isogeny to Endomorphism Ring Problem (IsERP) asks to compute the endomorphism ring of the codomain of an isogeny between supersingular curves in characteristic $p$ given only a representation for this isogeny, i.e. some data and an algorithm to evaluate this isogeny on any torsion point. This problem plays a central role in isogeny-based cryptography; it underlies the security of pSIDH protocol (ASIACRYPT 2022) and it is at the heart of the recent attacks that broke the SIDH key exchange. Prior to this work, no efficient algorithm was known to solve IsERP for a generic isogeny degree, the hardest case seemingly when the degree is prime. In this paper, we introduce a new quantum polynomial-time algorithm to solve IsERP for isogenies whose degrees are odd and have $O(\log\log p)$ many prime factors. As main technical tools, our algorithm uses a quantum algorithm for computing hidden Borel subgroups, a group action on supersingular isogenies from EUROCRYPT 2021, various algorithms for the Deuring correspondence and a new algorithm to lift arbitrary quaternion order elements modulo an odd integer $N$ with $O(\log\log p)$ many prime factors to powersmooth elements. As a main consequence for cryptography, we obtain a quantum polynomial-time key recovery attack on pSIDH. The technical tools we use may also be of independent interest.

When deploying artificial agents in real-world environments where they interact with humans, it is crucial that their behavior is aligned with the values, social norms or other requirements of that environment. However, many environments have implicit constraints that are difficult to specify and transfer to a learning agent. To address this challenge, we propose a novel method that utilizes the principle of maximum causal entropy to learn constraints and an optimal policy that adheres to these constraints, using demonstrations of agents that abide by the constraints. We prove convergence in a tabular setting and provide an approximation which scales to complex environments. We evaluate the effectiveness of the learned policy by assessing the reward received and the number of constraint violations, and we evaluate the learned cost function based on its transferability to other agents. Our method has been shown to outperform state-of-the-art approaches across a variety of tasks and environments, and it is able to handle problems with stochastic dynamics and a continuous state-action space.

We propose a new fast generalized functional principal components analysis (fast-GFPCA) algorithm for dimension reduction of non-Gaussian functional data. The method consists of: (1) binning the data within the functional domain; (2) fitting local random intercept generalized linear mixed models in every bin to obtain the initial estimates of the person-specific functional linear predictors; (3) using fast functional principal component analysis to smooth the linear predictors and obtain their eigenfunctions; and (4) estimating the global model conditional on the eigenfunctions of the linear predictors. An extensive simulation study shows that fast-GFPCA performs as well or better than existing state-of-the-art approaches, it is orders of magnitude faster than existing general purpose GFPCA methods, and scales up well with both the number of observed curves and observations per curve. Methods were motivated by and applied to a study of active/inactive physical activity profiles obtained from wearable accelerometers in the NHANES 2011-2014 study. The method can be implemented by any user familiar with mixed model software, though the R package fastGFPCA is provided for convenience.