Search

Concept Bottleneck Models (CBMs) have been proposed as a compromise between white-box and black-box models, aiming to achieve interpretability without sacrificing accuracy. The standard training procedure for CBMs is to predefine a candidate set of human-interpretable concepts, extract their values from the training data, and identify a sparse subset as inputs to a transparent prediction model. However, such approaches are often hampered by the tradeoff between enumerating a sufficiently large set of concepts to include those that are truly relevant versus controlling the cost of obtaining concept extractions. This work investigates a novel approach that sidesteps these challenges: BC-LLM iteratively searches over a potentially infinite set of concepts within a Bayesian framework, in which Large Language Models (LLMs) serve as both a concept extraction mechanism and prior. BC-LLM is broadly applicable and multi-modal. Despite imperfections in LLMs, we prove that BC-LLM can provide rigorous statistical inference and uncertainty quantification. In experiments, it outperforms comparator methods including black-box models, converges more rapidly towards relevant concepts and away from spuriously correlated ones, and is more robust to out-of-distribution samples.

Hyperdimensional Computing (HDC), a technique inspired by cognitive models of computation, has garnered significant interest in recent years. For example, HDC has been proposed as a more efficient and robust alternative basis for machine learning. The highly parallel nature of HDC algorithms makes them well-suited for execution on several hardware architectures, including CPUs, GPUs, FPGAs, ASIC-based and Resistive RAM-based accelerators. Traditionally, these diverse architectures are programmed using different languages and programming models, making heterogeneous programming for HDC prohibitively difficult. To make matters worse, currently no compiler framework that enables heterogeneous compilation of HDC programs and generates efficient code for a wide variety of hardware targets exists. We propose an end-to-end heterogeneous programming system for HDC: a novel programming language, HDC++, that enables programmers to write programs using a unified programming model, including a set of high-level, HDC-specific, abstractions to ease programmability; and a heterogeneous compilation framework, HPVM-HDC, that provides an intermediate representation that reflects the parallel character of HDC algorithms and enables compilation of HDC++ programs to a wide array of hardware targets, including a custom HD Digital ASIC and an HD Resistive RAM accelerator. HPVM-HDC can perform HD specific optimizations, which we demonstrate by implementing two domain specific optimizations. Our evaluation shows that HPVM-HDC generates performance competitive code, compared with baseline HD applications. Additionally, HPVM-HDC efficiently targets an HD Digital ASIC and an HD ReRAM accelerator simulator, achieving a geomean 1.28x and 2.15x speed-up over our compiled GPU implementations, respectively.

Dream11 is a fantasy sports platform that allows users to create their own virtual teams for real-life sports events. We host multiple sports and matches for our 200M+ user base. In this RMG (real money gaming) setting, users pay an entry amount to participate in various contest products that we provide to users. In our current work, we discuss the problem of predicting the user's propensity to spend in a gaming round, so it can be utilized for various downstream applications. e.g. Upselling users by incentivizing them marginally as per their spending propensity, or personalizing the product listing based on the user's propensity to spend. We aim to model the spending propensity of each user based on past transaction data. In this paper, we benchmark tree-based and deep-learning models that show good results on structured data, and we propose a new architecture change that is specifically designed to capture the rich interactions among the input features. We show that our proposed architecture outperforms the existing models on the task of predicting the user's propensity to spend in a gaming round. Our new transformer model surpasses the state-of-the-art FT-Transformer, improving MAE by 2.5\% and MSE by 21.8\%., Comment: 6 pages, 3 figures

Given a smooth proper morphism $f\colon X\rightarrow S$, we introduce a certain derived category where morphisms are permitted to be $\mathcal{O}_S$-linear differential operators. We then prove a generalisation of Serre duality that applies to two-term complexes of this type. We apply this to give a new proof of Poincar\'e duality for relative algebraic de Rham cohomology., Comment: 26 pages

Machine Learning (ML) research has increased substantially in recent years, due to the success of predictive modeling across diverse application domains. However, well-known barriers exist when attempting to deploy ML models in high-stakes, clinical settings, including lack of model transparency (or the inability to audit the inference process), large training data requirements with siloed data sources, and complicated metrics for measuring model utility. In this work, we show empirically that including stronger baseline models in healthcare ML evaluations has important downstream effects that aid practitioners in addressing these challenges. Through a series of case studies, we find that the common practice of omitting baselines or comparing against a weak baseline model (e.g. a linear model with no optimization) obscures the value of ML methods proposed in the research literature. Using these insights, we propose some best practices that will enable practitioners to more effectively study and deploy ML models in clinical settings., Comment: 18 pages, 6 figures

We investigate the possibility that for any given reaction rate vector $k$ associated with a network $G$, there exists another network $G'$ with a corresponding reaction rate vector that reproduces the mass-action dynamics generated by $(G,k)$. Our focus is on a particular class of networks for $G$, where the corresponding network $G'$ is weakly reversible. In particular, we show that strongly endotactic two-dimensional networks with a two dimensional stoichiometric subspace, as well as certain endotactic networks under additional conditions, exhibit this property. Additionally, we establish a strong connection between this family of networks and the locus in the space of rate constants of which the corresponding dynamics admits globally stable steady states., Comment: 36 pages, 6 figures

A nontrivial connected graph is matching covered if each edge belongs to some perfect matching. There is extensive theory on these graphs; see Lucchesi and Murty [Perfect Matchings, Springer 2024]. Two edges are mutually dependent if every perfect matching either contains both or neither. This is an equivalence relation and induces a partition of the edges; each part is called an equivalence class. Note that $\frac{n}{2}$ is an upper bound on the size of any equivalence class. We characterize those graphs that attain this upper bound, thus fixing an error in [Discrete Mathematics, 343(8), 2020]. Sch\"onberger (1934) strengthened the famous result of Petersen by proving that every 2-connected cubic graph is matching covered. This immediately begs the question as to which 2-connected cubic graphs have the property that each edge belongs to two or more perfect matchings. An edge is solitary if it belongs to exactly one perfect matching. Note that if any member of an equivalence class is solitary then so is each member; such an equivalence class is called a solitary class. This leads us to the solitary pattern -- the sequence of sizes of solitary classes in nonincreasing order. For instance, $K_4$ has solitary pattern (2,2,2) whereas the Petersen graph has solitary pattern (). Using the theory of Lucchesi and Murty, we prove that every 3-connected cubic graph $G$ has one of the following solitary patterns: (2,2,2), (2,2,1), (2,2), (2,1,1), (2,1), (2), (1,1,1), (1,1), (1) or (); consequently, $G$ has at most six solitary edges. We also provide characterizations of 3-connected cubic graphs that have a given solitary pattern except for (1,1), (1) and (). Finally, we prove that every 2-connected cubic graph, except $\theta, K_4, \overline{C_6}$ and the bicorn, has at most $\frac{n}{2}$ solitary edges, and equality holds if and only if its solitary edges comprise a perfect matching.

Autonomous motorsports aim to replicate the human racecar driver with software and sensors. As in traditional motorsports, Autonomous Racing Vehicles (ARVs) are pushed to their handling limits in multi-agent scenarios at extremely high ($\geq 150mph$) speeds. This Operational Design Domain (ODD) presents unique challenges across the autonomy stack. The Indy Autonomous Challenge (IAC) is an international competition aiming to advance autonomous vehicle development through ARV competitions. While far from challenging what a human racecar driver can do, the IAC is pushing the state of the art by facilitating full-sized ARV competitions. This paper details the MIT-Pitt-RW Team's approach to autonomous racing in the IAC. In this work, we present our modular and fast approach to agent detection, motion planning and controls to create an autonomy stack. We also provide analysis of the performance of the software stack in single and multi-agent scenarios for rapid deployment in a fast-paced competition environment. We also cover what did and did not work when deployed on a physical system the Dallara AV-21 platform and potential improvements to address these shortcomings. Finally, we convey lessons learned and discuss limitations and future directions for improvement., Comment: Published in Journal of Field Robotics

For all $n \geq 1$, there is a notion of $n$-smooth group scheme over any $\mathbb{F}_p$-algebra $R$, which may be thought of as a ``Frobenius analogue" of $n$-truncated Barsotti-Tate groups over $R$. We show that the category of $n$-smooth commutative group schemes over $R$ is equivalent to a certain full subcategory of Dieudonn\'e modules over $R$. As a consequence, we show that the moduli stack $\mathrm{Sm}_n$ of $n$-smooth commutative group schemes is smooth over $\mathbb{F}_p$ and that the natural truncation morphism $\mathrm{Sm}_{n+1} \to \mathrm{Sm}_n$ is smooth and surjective. These results affirmatively answer conjectures of Drinfeld., Comment: 18 pages. Comments welcome!

Quantum error correction provides a path to reach practical quantum computing by combining multiple physical qubits into a logical qubit, where the logical error rate is suppressed exponentially as more qubits are added. However, this exponential suppression only occurs if the physical error rate is below a critical threshold. In this work, we present two surface code memories operating below this threshold: a distance-7 code and a distance-5 code integrated with a real-time decoder. The logical error rate of our larger quantum memory is suppressed by a factor of $\Lambda$ = 2.14 $\pm$ 0.02 when increasing the code distance by two, culminating in a 101-qubit distance-7 code with 0.143% $\pm$ 0.003% error per cycle of error correction. This logical memory is also beyond break-even, exceeding its best physical qubit's lifetime by a factor of 2.4 $\pm$ 0.3. We maintain below-threshold performance when decoding in real time, achieving an average decoder latency of 63 $\mu$s at distance-5 up to a million cycles, with a cycle time of 1.1 $\mu$s. To probe the limits of our error-correction performance, we run repetition codes up to distance-29 and find that logical performance is limited by rare correlated error events occurring approximately once every hour, or 3 $\times$ 10$^9$ cycles. Our results present device performance that, if scaled, could realize the operational requirements of large scale fault-tolerant quantum algorithms., Comment: 10 pages, 4 figures, Supplementary Information

We present shadow Hamiltonian simulation, a framework for simulating quantum dynamics using a compressed quantum state that we call the "shadow state". The amplitudes of this shadow state are proportional to the expectations of a set of operators of interest. The shadow state evolves according to its own Schr\"odinger equation, and under broad conditions can be simulated on a quantum computer. We analyze a number of applications of this framework to quantum simulation problems. This includes simulating the dynamics of exponentially large systems of free fermions, or exponentially large systems of free bosons, the latter example recovering a recent algorithm for simulating exponentially many classical harmonic oscillators. Shadow Hamiltonian simulation can be extended to simulate expectations of more complex operators such as two-time correlators or Green's functions, and to study the evolution of operators themselves in the Heisenberg picture.

The sensitivity and spectral coverage of JWST is enabling us to test our assumptions of ultracool dwarf atmospheric chemistry, especially with regards to the abundances of phosphine (PH$_3$) and carbon dioxide (CO$_2$). In this paper, we use NIRSpec PRISM spectra ($\sim$0.8$-$5.5 $\mu$m, $R\sim$100) of four late T and Y dwarfs to show that standard substellar atmosphere models have difficulty replicating the 4.1$-$4.4 $\mu$m wavelength range as they predict an overabundance of phosphine and an underabundance of carbon dioxide. To help quantify this discrepancy, we generate a grid of models using PICASO based on the Elf Owl chemical and temperature profiles where we include the abundances of these two molecules as parameters. The fits to these PICASO models show a consistent preference for orders of magnitude higher CO$_2$ abundances and a reduction in PH$_3$ abundance as compared to the nominal models. This tendency means that the claimed phosphine detection in UNCOVER$-$BD$-$3 could instead be explained by a CO$_2$ abundance in excess of standard atmospheric model predictions; however the signal-to-noise of the spectrum is not high enough to discriminate between these cases. We discuss atmospheric mechanisms that could explain the observed underabundance of PH$_3$ and overabundance of CO$_2$, including a vertical eddy diffusion coefficient ($K_{\mathrm{zz}}$) that varies with altitude, incorrect chemical pathways, or elements condensing out in forms such as NH$_4$H$_2$PO$_4$. However, our favored explanation for the required CO$_2$ enhancement is that the quench approximation does not accurately predict the CO$_2$ abundance, as CO$_2$ remains in chemical equilibrium with CO after CO quenches., Comment: Accepted, 15 pages, 9 figures

A nontrivial connected graph is matching covered if each edge belongs to some perfect matching. For most problems pertaining to perfect matchings, one may restrict attention to matching covered graphs; thus, there is extensive literature on them. A cornerstone of this theory is an ear decomposition result due to Lov\'asz and Plummer. Their theorem is a fundamental problem-solving tool, and also yields interesting open problems; we discuss two such problems below, and we solve one of them. A subgraph $H$ of a graph $G$ is conformal if $G-V(H)$ has a perfect matching. This notion is intrinsically related to the aforementioned ear decomposition theorem -- which implies that each matching covered graph (apart from $K_2$ and even cycles) contains a conformal bisubdivision of $\theta$, or a conformal bisubdivision of $K_4$, possibly both. (Here, $\theta$ refers to the graph with two vertices joined by three edges.) This immediately leads to two problems: characterize $\theta$-free (likewise, $K_4$-free) matching covered graphs. A characterization of planar $K_4$-free matching covered graphs was obtained by Kothari and Murty [J. Graph Theory, 82 (1), 2016]; the nonplanar case is open. We provide a characterization of $\theta$-free matching covered graphs that immediately implies a poly-time algorithm for the corresponding decision problem. Our characterization relies heavily on a seminal result due to Edmonds, Lov\'asz and Pulleyblank [Combinatorica, 2, 1982] pertaining to the tight cut decomposition theory of matching covered graphs. As corollaries, we provide two upper bounds on the size of a $\theta$-free graph, namely, $m\leq 2n-1$ and $m\leq \frac{3n}{2}+b-1$, where $b$ denotes the number of bricks obtained in any tight cut decomposition of the graph; for each bound, we provide a characterization of the tight examples. The Petersen graph and $K_4$ play key roles in our results., Comment: Submitted to a journal

We describe a quantum algorithm for the Planted Noisy $k$XOR problem (also known as sparse Learning Parity with Noise) that achieves a nearly quartic ($4$th power) speedup over the best known classical algorithm while also only using logarithmically many qubits. Our work generalizes and simplifies prior work of Hastings, by building on his quantum algorithm for the Tensor Principal Component Analysis (PCA) problem. We achieve our quantum speedup using a general framework based on the Kikuchi Method (recovering the quartic speedup for Tensor PCA), and we anticipate it will yield similar speedups for further planted inference problems. These speedups rely on the fact that planted inference problems naturally instantiate the Guided Sparse Hamiltonian problem. Since the Planted Noisy $k$XOR problem has been used as a component of certain cryptographic constructions, our work suggests that some of these are susceptible to super-quadratic quantum attacks., Comment: 50 pages

Large Language Models(LLMs) have shown exceptional abilities, yet training these models can be quite challenging. There is a strong dependence on the quality of data and finding the best instruction tuning set. Further, the inherent limitations in training methods create substantial difficulties to train relatively smaller models with 7B and 13B parameters. In our research, we suggest an improved training method for these models by utilising knowledge from larger models, such as a mixture of experts (8x7B) architectures. The scale of these larger models allows them to capture a wide range of variations from data alone, making them effective teachers for smaller models. Moreover, we implement a novel post-training domain alignment phase that employs domain-specific expert models to boost domain-specific knowledge during training while preserving the model's ability to generalise. Fine-tuning Mistral 7B and 2x7B with our method surpasses the performance of state-of-the-art language models with more than 7B and 13B parameters: achieving up to $7.9$ in MT-Bench and $93.04\%$ on AlpacaEval., Comment: 7 pages, 4 figures

We prove that for every $D \in \N$, and large enough constant $d \in \N$, with high probability over the choice of $G \sim G(n,d/n)$, the \Erdos-\Renyi random graph distribution, the canonical degree $2D$ Sum-of-Squares relaxation fails to certify that the largest independent set in $G$ is of size $o(\frac{n}{\sqrt{d} D^4})$. In particular, degree $D$ sum-of-squares strengthening can reduce the integrality gap of the classical \Lovasz theta SDP relaxation by at most a $O(D^4)$ factor. This is the first lower bound for $>4$-degree Sum-of-Squares (SoS) relaxation for any problems on \emph{ultra sparse} random graphs (i.e. average degree of an absolute constant). Such ultra-sparse graphs were a known barrier for previous methods and explicitly identified as a major open direction (e.g.,~\cite{deshpande2019threshold, kothari2021stressfree}). Indeed, the only other example of an SoS lower bound on ultra-sparse random graphs was a degree-4 lower bound for Max-Cut. Our main technical result is a new method to obtain spectral norm estimates on graph matrices (a class of low-degree matrix-valued polynomials in $G(n,d/n)$) that are accurate to within an absolute constant factor. All prior works lose $\poly log n$ factors that trivialize any lower bound on $o(\log n)$-degree random graphs. We combine these new bounds with several upgrades on the machinery for analyzing lower-bound witnesses constructed by pseudo-calibration so that our analysis does not lose any $\omega(1)$-factors that would trivialize our results. In addition to other SoS lower bounds, we believe that our methods for establishing spectral norm estimates on graph matrices will be useful in the analyses of numerical algorithms on average-case inputs.

It is becoming cheaper to launch disinformation operations at scale using AI-generated content, in particular 'deepfake' technology. We have observed instances of deepfakes in political campaigns, where generated content is employed to both bolster the credibility of certain narratives (reinforcing outcomes) and manipulate public perception to the detriment of targeted candidates or causes (adversarial outcomes). We discuss the threats from deepfakes in politics, highlight model specifications underlying different types of deepfake generation methods, and contribute an accessible evaluation of the efficacy of existing detection methods. We provide this as a summary for lawmakers and civil society actors to understand how the technology may be applied in light of existing policies regulating its use. We highlight the limitations of existing detection mechanisms and discuss the areas where policies and regulations are required to address the challenges of deepfakes., Comment: Accepted at the AAAI 2024 conference, AI for Credible Elections Workshop-AI4CE 2024

We present an atmospheric retrieval analysis of the Y0 brown dwarf WISE J035934.06$-$540154.6 using the low-resolution 0.96--12 $\mu$m JWST spectrum presented in \citet{Beiler_2023}. We obtain volume number mixing ratios of the major gas-phase absorbers (H$_2$O, CH$_4$, CO, CO$_2$, PH$_3$, and H$_2$S) that are 3--5$\times$ more precise than previous work that used HST spectra. We also find an order-of-magnitude improvement in the precision of the retrieved thermal profile, a direct result of the broad wavelength coverage of the JWST data. We used the retrieved thermal profile and surface gravity to generate a grid of chemical forward models with varying metallicity, (C/O)$_\textrm{atm}$, and strengths of vertical mixing as encapsulated by the eddy diffusion coefficient $K_\textrm{zz}$. Comparison of the retrieved abundances with this grid of models suggests that the deep atmosphere of WISE 0359$-$54 shows signs of vigorous vertical mixing with $K_\textrm{zz}=10^9$ [cm$^{2}$ s$^{-1}$]. To test the sensitivity of these results to our 5-knot spline thermal profile model, we performed a second retrieval using the \citet{Madhusudhan_2009} thermal profile model. While the results of the two retrievals generally agree well, we do find differences between the retrieved values of mass and volume number mixing ratio of H$_2$S with fractional differences of the median values of $-$0.64 and $-$0.10, respectively. In addition, the 5-knot thermal profile is consistently warmer at pressure between 1 and 70 bar. Nevertheless, our results underscore the power that the broad-wavelength infrared spectra obtainable with the James Webb Space Telescope have to characterize the atmospheres of cool brown dwarfs.

For most problems pertaining to perfect matchings, one may restrict attention to matching covered graphs -- that is, connected nontrivial graphs with the property that each edge belongs to some perfect matching. There is extensive literature on these graphs that are also known as $1$-extendable graphs (since each edge extends to a perfect matching) including an ear decomposition theorem due to Lovasz and Plummer. A cycle $C$ of a graph $G$ is conformal if $G-V(C)$ has a perfect matching; such cycles play an important role in the study of perfect matchings, especially when investigating the Pfaffian orientation problem. A matching covered graph $G$ is cycle-extendable if -- for each even cycle $C$ -- the cycle $C$ is conformal, or equivalently, each perfect matching of $C$ extends to a perfect matching of $G$, or equivalently, $C$ is the symmetric difference of two perfect matchings of $G$, or equivalently, $C$ extends to an ear decomposition of $G$. In the literature, these are also known as cycle-nice or as $1$-cycle resonant graphs. Zhang, Wang, Yuan, Ng and Cheng [Discrete Mathematics, 345:7 (2022), 112876] provided a characterization of claw-free cycle-extendable graphs. Guo and Zhang [Discrete Mathematics, 275:1-3 (2004), 151-164] and independently Zhang and Li [Discrete Applied Mathematics, 160:13-14 (2012), 2069-2074], provided characterizations of bipartite planar cycle-extendable graphs. In this paper, we establish a characterization of all planar cycle-extendable graphs -- in terms of $K_2$ and four infinite families., Comment: Submitted to a journal

A set of high dimensional points $X=\{x_1, x_2,\ldots, x_n\} \subset R^d$ in isotropic position is said to be $\delta$-anti concentrated if for every direction $v$, the fraction of points in $X$ satisfying $|\langle x_i,v \rangle |\leq \delta$ is at most $O(\delta)$. Motivated by applications to list-decodable learning and clustering, recent works have considered the problem of constructing efficient certificates of anti-concentration in the average case, when the set of points $X$ corresponds to samples from a Gaussian distribution. Their certificates played a crucial role in several subsequent works in algorithmic robust statistics on list-decodable learning and settling the robust learnability of arbitrary Gaussian mixtures, yet remain limited to rotationally invariant distributions. This work presents a new (and arguably the most natural) formulation for anti-concentration. Using this formulation, we give quasi-polynomial time verifiable sum-of-squares certificates of anti-concentration that hold for a wide class of non-Gaussian distributions including anti-concentrated bounded product distributions and uniform distributions over $L_p$ balls (and their affine transformations). Consequently, our method upgrades and extends results in algorithmic robust statistics e.g., list-decodable learning and clustering, to such distributions. Our approach constructs a canonical integer program for anti-concentration and analysis a sum-of-squares relaxation of it, independent of the intended application. We rely on duality and analyze a pseudo-expectation on large subsets of the input points that take a small value in some direction. Our analysis uses the method of polynomial reweightings to reduce the problem to analyzing only analytically dense or sparse directions., Comment: updated exposition; added certifiable hypercontractivity of degree-two polynomials for any Poincar\'e distribution

We develop a new approach for approximating large independent sets when the input graph is a one-sided spectral expander - that is, the uniform random walk matrix of the graph has the second eigenvalue bounded away from 1. Consequently, we obtain a polynomial time algorithm to find linear-sized independent sets in one-sided expanders that are almost $3$-colorable or are promised to contain an independent set of size $(1/2-\epsilon)n$. Our second result above can be refined to require only a weaker vertex expansion property with an efficient certificate. Somewhat surprisingly, we observe that the analogous task of finding a linear-sized independent set in almost $4$-colorable one-sided expanders (even when the second eigenvalue is $o_n(1)$) is NP-hard, assuming the Unique Games Conjecture. All prior algorithms that beat the worst-case guarantees for this problem rely on bottom eigenspace enumeration techniques (following the classical spectral methods of Alon and Kahale) and require two-sided expansion, meaning a bounded number of negative eigenvalues of magnitude $\Omega(1)$. Such techniques naturally extend to almost $k$-colorable graphs for any constant $k$, in contrast to analogous guarantees on one-sided expanders, which are Unique Games-hard to achieve for $k \geq 4$. Our rounding builds on the method of simulating multiple samples from a pseudodistribution introduced by Barak et. al. for rounding Unique Games instances. The key to our analysis is a new clustering property of large independent sets in expanding graphs - every large independent set has a larger-than-expected intersection with some member of a small list - and its formalization in the low-degree sum-of-squares proof system., Comment: 57 pages, 3 figures

Given copies of a quantum state $\rho$, a shadow tomography protocol aims to learn all expectation values from a fixed set of observables, to within a given precision $\epsilon$. We say that a shadow tomography protocol is triply efficient if it is sample- and time-efficient, and only employs measurements that entangle a constant number of copies of $\rho$ at a time. The classical shadows protocol based on random single-copy measurements is triply efficient for the set of local Pauli observables. This and other protocols based on random single-copy Clifford measurements can be understood as arising from fractional colorings of a graph $G$ that encodes the commutation structure of the set of observables. Here we describe a framework for two-copy shadow tomography that uses an initial round of Bell measurements to reduce to a fractional coloring problem in an induced subgraph of $G$ with bounded clique number. This coloring problem can be addressed using techniques from graph theory known as chi-boundedness. Using this framework we give the first triply efficient shadow tomography scheme for the set of local fermionic observables, which arise in a broad class of interacting fermionic systems in physics and chemistry. We also give a triply efficient scheme for the set of all $n$-qubit Pauli observables. Our protocols for these tasks use two-copy measurements, which is necessary: sample-efficient schemes are provably impossible using only single-copy measurements. Finally, we give a shadow tomography protocol that compresses an $n$-qubit quantum state into a $\text{poly}(n)$-sized classical representation, from which one can extract the expected value of any of the $4^n$ Pauli observables in $\text{poly}(n)$ time, up to a small constant error.

In the rapidly advancing landscape of connected and automated vehicles (CAV), the integration of Vehicle-to-Everything (V2X) communication in traditional fusion systems presents a promising avenue for enhancing vehicle perception. Addressing current limitations with vehicle sensing, this paper proposes a novel Vehicle-to-Vehicle (V2V) enabled track management system that leverages the synergy between V2V signals and detections from radar and camera sensors. The core innovation lies in the creation of independent priority track lists, consisting of fused detections validated through V2V communication. This approach enables more flexible and resilient thresholds for track management, particularly in scenarios with numerous occlusions where the tracked objects move outside the field of view of the perception sensors. The proposed system considers the implications of falsification of V2X signals which is combated through an initial vehicle identification process using detection from perception sensors. Presented are the fusion algorithm, simulated environments, and validation mechanisms. Experimental results demonstrate the improved accuracy and robustness of the proposed system in common driving scenarios, highlighting its potential to advance the reliability and efficiency of autonomous vehicles., Comment: 6 pages, 5 figures

Clinical trial matching is the task of identifying trials for which patients may be potentially eligible. Typically, this task is labor-intensive and requires detailed verification of patient electronic health records (EHRs) against the stringent inclusion and exclusion criteria of clinical trials. This process is manual, time-intensive, and challenging to scale up, resulting in many patients missing out on potential therapeutic options. Recent advancements in Large Language Models (LLMs) have made automating patient-trial matching possible, as shown in multiple concurrent research studies. However, the current approaches are confined to constrained, often synthetic datasets that do not adequately mirror the complexities encountered in real-world medical data. In this study, we present the first, end-to-end large-scale empirical evaluation of clinical trial matching using real-world EHRs. Our study showcases the capability of LLMs to accurately match patients with appropriate clinical trials. We perform experiments with proprietary LLMs, including GPT-4 and GPT-3.5, as well as our custom fine-tuned model called OncoLLM and show that OncoLLM, despite its significantly smaller size, not only outperforms GPT-3.5 but also matches the performance of qualified medical doctors. All experiments were carried out on real-world EHRs that include clinical notes and available clinical trials from a single cancer center in the United States., Comment: 30 Pages, 8 Figures, Supplementary Work Attached

We give a simple, greedy $O(n^{\omega+0.5})=O(n^{2.872})$-time algorithm to list-decode planted cliques in a semirandom model introduced in [CSV17] (following [FK01]) that succeeds whenever the size of the planted clique is $k\geq O(\sqrt{n} \log^2 n)$. In the model, the edges touching the vertices in the planted $k$-clique are drawn independently with probability $p=1/2$ while the edges not touching the planted clique are chosen by an adversary in response to the random choices. Our result shows that the computational threshold in the semirandom setting is within a $O(\log^2 n)$ factor of the information-theoretic one [Ste17] thus resolving an open question of Steinhardt. This threshold also essentially matches the conjectured computational threshold for the well-studied special case of fully random planted clique. All previous algorithms [CSV17, MMT20, BKS23] in this model are based on rather sophisticated rounding algorithms for entropy-constrained semidefinite programming relaxations and their sum-of-squares strengthenings and the best known guarantee is a $n^{O(1/\epsilon)}$-time algorithm to list-decode planted cliques of size $k \geq \tilde{O}(n^{1/2+\epsilon})$. In particular, the guarantee trivializes to quasi-polynomial time if the planted clique is of size $O(\sqrt{n} \operatorname{polylog} n)$. Our algorithm achieves an almost optimal guarantee with a surprisingly simple greedy algorithm. The prior state-of-the-art algorithmic result above is based on a reduction to certifying bounds on the size of unbalanced bicliques in random graphs -- closely related to certifying the restricted isometry property (RIP) of certain random matrices and known to be hard in the low-degree polynomial model. Our key idea is a new approach that relies on the truth of -- but not efficient certificates for -- RIP of a new class of matrices built from the input graphs., Comment: 22 pages, to appear FOCS 2024

We give improved lower bounds for binary $3$-query locally correctable codes (3-LCCs) $C \colon \{0,1\}^k \rightarrow \{0,1\}^n$. Specifically, we prove: (1) If $C$ is a linear design 3-LCC, then $n \geq 2^{(1 - o(1))\sqrt{k} }$. A design 3-LCC has the additional property that the correcting sets for every codeword bit form a perfect matching and every pair of codeword bits is queried an equal number of times across all matchings. Our bound is tight up to a factor $\sqrt{8}$ in the exponent of $2$, as the best construction of binary $3$-LCCs (obtained by taking Reed-Muller codes on $\mathbb{F}_4$ and applying a natural projection map) is a design $3$-LCC with $n \leq 2^{\sqrt{8 k}}$. Up to a $\sqrt{8}$ factor, this resolves the Hamada conjecture on the maximum $\mathbb{F}_2$-codimension of a $4$-design. (2) If $C$ is a smooth, non-linear, adaptive $3$-LCC with perfect completeness, then, $n \geq 2^{\Omega(k^{1/5})}$. (3) If $C$ is a smooth, non-linear, adaptive $3$-LCC with completeness $1 - \varepsilon$, then $n \geq \tilde{\Omega}(k^{\frac{1}{2\varepsilon}})$. In particular, when $\varepsilon$ is a small constant, this implies a lower bound for general non-linear LCCs that beats the prior best $n \geq \tilde{\Omega}(k^3)$ lower bound of [AGKM23] by a polynomial factor. Our design LCC lower bound is obtained via a fine-grained analysis of the Kikuchi matrix method applied to a variant of the matrix used in [KM23]. Our lower bounds for non-linear codes are obtained by designing a from-scratch reduction from nonlinear $3$-LCCs to a system of "chain XOR equations": polynomial equations with similar structure to the long chain derivations that arise in the lower bounds for linear $3$-LCCs [KM23].

A connected graph, on four or more vertices, is matching covered if every edge is present in some perfect matching. An ear decomposition theorem (similar to the one for $2$-connected graphs) exists for bipartite matching covered graphs due to Hetyei. From the results and proofs of Lov\'asz and Plummer, that rely on Hetyei's theorem, one may deduce that any minimal bipartite matching covered graph has at least $2(m-n+2)$ vertices of degree two (where minimal means that deleting any edge results in a graph that is not matching covered); such a graph is said to be extremal if it attains the stated lower bound. In this paper, we provide a complete characterization of the class of extremal minimal bipartite matching covered graphs. In particular, we prove that every such graph $G$ is obtained from two copies of a tree devoid of degree two vertices, say $T$ and $T'$, by adding edges -- each of which joins a leaf of $T$ with the corresponding leaf of $T'$. Apart from the aforementioned bound, there are four other bounds that appear in, or may be deduced from, the work of Lov\'asz and Plummer. Each of these bounds leads to a notion of extremality. In this paper, we obtain a complete characterization of all of these extremal classes and also establish relationships between them. Two of our characterizations are in the same spirit as the one stated above. For the remaining two extremal classes, we reduce each of them to one of the already characterized extremal classes using standard matching theoretic operations., Comment: Submitted to Innovations in Graph Theory

Retrieving information from EHR systems is essential for answering specific questions about patient journeys and improving the delivery of clinical care. Despite this fact, most EHR systems still rely on keyword-based searches. With the advent of generative large language models (LLMs), retrieving information can lead to better search and summarization capabilities. Such retrievers can also feed Retrieval-augmented generation (RAG) pipelines to answer any query. However, the task of retrieving information from EHR real-world clinical data contained within EHR systems in order to solve several downstream use cases is challenging due to the difficulty in creating query-document support pairs. We provide a blueprint for creating such datasets in an affordable manner using large language models. Our method results in a retriever that is 30-50 F-1 points better than propriety counterparts such as Ada and Mistral for oncology data elements. We further compare our model, called Onco-Retriever, against fine-tuned PubMedBERT model as well. We conduct an extensive manual evaluation on real-world EHR data along with latency analysis of the different models and provide a path forward for healthcare organizations to build domain-specific retrievers., Comment: 18 pages

We use the kinematics of field OB stars to estimate the frequencies of runaway stars generated by the dynamical ejection scenario (DES), the binary supernova scenario (BSS), and the combined two-step mechanism. We update the proper motions for field OB and OBe stars in the Small Magellanic Cloud (SMC) using Gaia DR3. Our sample now contains 336 stars from the Runaways and Isolated O-Type Star Spectroscopic Survey of the SMC (RIOTS4), and we update our algorithm to calculate more accurate velocities compared to those obtained previously from DR2. We find a decrease in median velocity from 39 to 29 km/s, implying that the proper motions from our previous work were systematically overestimated. We present the velocity distribution for OBe stars and quantitatively compare it to those of non-compact binaries and high-mass X-ray binaries. We confirm that OBe stars appear to be dominated by the BSS and are likely post-SN binary systems, further supporting the mass-transfer model to explain the origin of their emission-line disks. In contrast, normal OB stars may show a bimodal velocity distribution, as may be expected from different processes that occur with dynamical ejections. The kinematics of fast-rotating OB stars are similar to those of normal OB stars rather than OBe stars, suggesting that the origin of their high v_r*sin(i) is different from that of OBe stars. We update our model parameters describing the kinematic origins of the SMC field population, still confirming that for runaway stars, the DES mechanism dominates, and two-step ejections seem comparable in frequency to pure BSS ejections., Comment: 12 pages, 7 figures (figures 5 and 7 contain 2 files each), and 4 tables

We demonstrate synthesis of BaZr(S,Se)3 chalcogenide perovskite alloys by selenization of BaZrS3 thin films. The anion-exchange process produces films with tunable composition and band gap without changing the orthorhombic perovskite crystal structure or the film microstructure. The direct band gap is tunable between 1.5 and 1.9 eV. The alloy films made in this way feature 100x stronger photoconductive response and a lower density of extended defects, compared to alloy films made by direct growth. The perovskite structure is stable in high-selenium-content thin films with and without epitaxy. The manufacturing-compatible process of selenization in H2Se gas may spur the development of chalcogenide perovskite solar cell technology.

Due to its optimal complexity, the multigrid (MG) method is one of the most popular approaches for solving large-scale linear systems arising from the discretization of partial differential equations. However, the parallel implementation of standard MG methods, which are inherently multiplicative, suffers from increasing communication complexity. In such cases, the additive variants of MG methods provide a good alternative due to their inherently parallel nature, although they exhibit slower convergence. This work combines the additive multigrid method with the multipreconditioned conjugate gradient (MPCG) method. In the proposed approach, the MPCG method employs the corrections from the different levels of the MG hierarchy as separate preconditioned search directions. In this approach, the MPCG method updates the current iterate by using the linear combination of the preconditioned search directions, where the optimal coefficients for the linear combination are computed by exploiting the energy norm minimization of the CG method. The idea behind our approach is to combine the $A$-conjugacy of the search directions of the MPCG method and the quasi $H_1$-orthogonality of the corrections from the MG hierarchy. In the numerical section, we study the performance of the proposed method compared to the standard additive and multiplicative MG methods used as preconditioners for the CG method.

Many online platforms predominantly rank items by predicted user engagement. We believe that there is much unrealized potential in including non-engagement signals, which can improve outcomes both for platforms and for society as a whole. Based on a daylong workshop with experts from industry and academia, we formulate a series of propositions and document each as best we can from public evidence, including quantitative results where possible. There is strong evidence that ranking by predicted engagement is effective in increasing user retention. However retention can be further increased by incorporating other signals, including item "quality" proxies and asking users what they want to see with "item-level" surveys. There is also evidence that "diverse engagement" is an effective quality signal. Ranking changes can alter the prevalence of self-reported experiences of various kinds (e.g. harassment) but seldom have large enough effects on attitude measures like user satisfaction, well-being, polarization etc. to be measured in typical experiments. User controls over ranking often have low usage rates, but when used they do correlate well with quality and item-level surveys. There was no strong evidence on the impact of transparency/explainability on retention. There is reason to believe that generative AI could be used to create better quality signals and enable new kinds of user controls.

We present LiRank, a large-scale ranking framework at LinkedIn that brings to production state-of-the-art modeling architectures and optimization methods. We unveil several modeling improvements, including Residual DCN, which adds attention and residual connections to the famous DCNv2 architecture. We share insights into combining and tuning SOTA architectures to create a unified model, including Dense Gating, Transformers and Residual DCN. We also propose novel techniques for calibration and describe how we productionalized deep learning based explore/exploit methods. To enable effective, production-grade serving of large ranking models, we detail how to train and compress models using quantization and vocabulary compression. We provide details about the deployment setup for large-scale use cases of Feed ranking, Jobs Recommendations, and Ads click-through rate (CTR) prediction. We summarize our learnings from various A/B tests by elucidating the most effective technical approaches. These ideas have contributed to relative metrics improvements across the board at LinkedIn: +0.5% member sessions in the Feed, +1.76% qualified job applications for Jobs search and recommendations, and +4.3% for Ads CTR. We hope this work can provide practical insights and solutions for practitioners interested in leveraging large-scale deep ranking systems.

Given a $k$-uniform hypergraph $H$ on $n$ vertices, an even cover in $H$ is a collection of hyperedges that touch each vertex an even number of times. Even covers are a generalization of cycles in graphs and are equivalent to linearly dependent subsets of a system of linear equations modulo $2$. As a result, they arise naturally in the context of well-studied questions in coding theory and refuting unsatisfiable $k$-SAT formulas. Analogous to the irregular Moore bound of Alon, Hoory, and Linial (2002), in 2008, Feige conjectured an extremal trade-off between the number of hyperedges and the length of the smallest even cover in a $k$-uniform hypergraph. This conjecture was recently settled up to a multiplicative logarithmic factor in the number of hyperedges (Guruswami, Kothari, and 1Manohar 2022 and Hsieh, Kothari, and Mohanty 2023). These works introduce the new technique that relates hypergraph even covers to cycles in the associated \emph{Kikuchi} graphs. Their analysis of these Kikuchi graphs, especially for odd $k$, is rather involved and relies on matrix concentration inequalities. In this work, we give a simple and purely combinatorial argument that recovers the best-known bound for Feige's conjecture for even $k$. We also introduce a novel variant of a Kikuchi graph which together with this argument improves the logarithmic factor in the best-known bounds for odd $k$. As an application of our ideas, we also give a purely combinatorial proof of the improved lower bounds (Alrabiah, Guruswami, Kothari and Manohar, 2023) on 3-query binary linear locally decodable codes., Comment: 19 pages