Search

The last five years of research on distributed graph algorithms have seen huge leaps of progress, both regarding algorithmic improvements and impossibility results: new strong lower bounds have emerged for many central problems and exponential improvements over the state of the art have been achieved for the runtimes of many algorithms. Nevertheless, there are still large gaps between the best known upper and lower bounds for many important problems. The current lower bound techniques for deterministic algorithms are often tailored to obtaining a logarithmic bound and essentially cannot be used to prove lower bounds beyond $\Omega(\log n)$. In contrast, the best deterministic upper bounds are often polylogarithmic, raising the fundamental question of how to resolve the gap between logarithmic lower and polylogarithmic upper bounds and finally obtain tight bounds. We develop a novel algorithm design technique aimed at closing this gap. In essence, each node finds a carefully chosen local solution in $O(\log n)$ rounds and we guarantee that this solution is consistent with the other nodes' solutions without coordination. The local solutions are based on a distributed version of Hall's theorem that may be of independent interest and motivates the title of this work. We showcase our framework by improving on the state of the art for the following fundamental problems: edge coloring, bipartite saturating matchings and hypergraph sinkless orientation. In particular, we obtain an asymptotically optimal $O(\log n)$-round algorithm for $3\Delta/2$-edge coloring in bounded degree graphs. The previously best bound for the problem was $O(\log^4 n)$ rounds, obtained by plugging in the state-of-the-art maximal independent set algorithm from arXiv:2303.16043 into the $3\Delta/2$-edge coloring algorithm from arXiv:1711.05469 ., Comment: To appear at SODA'25

We continue to study the learning-theoretic foundations of generation by extending the results from Kleinberg and Mullainathan [2024] and Li et al. [2024] to account for noisy example streams. In the noiseless setting of Kleinberg and Mullainathan [2024] and Li et al. [2024], an adversary picks a hypothesis from a binary hypothesis class and provides a generator with a sequence of its positive examples. The goal of the generator is to eventually output new, unseen positive examples. In the noisy setting, an adversary still picks a hypothesis and a sequence of its positive examples. But, before presenting the stream to the generator, the adversary inserts a finite number of negative examples. Unaware of which examples are noisy, the goal of the generator is to still eventually output new, unseen positive examples. In this paper, we provide necessary and sufficient conditions for when a binary hypothesis class can be noisily generatable. We provide such conditions with respect to various constraints on the number of distinct examples that need to be seen before perfect generation of positive examples. Interestingly, for finite and countable classes we show that generatability is largely unaffected by the presence of a finite number of noisy examples., Comment: 19 pages. arXiv admin note: text overlap with arXiv:2410.13714

Language model alignment has become a critical step in training modern generative language models. The goal of alignment is to finetune a reference model such that the win rate of a sample from the aligned model over a sample from the reference model is high, subject to a KL divergence constraint. Today, we are increasingly using inference-time algorithms (e.g., Best-of-N, controlled decoding, tree search) to decode from language models rather than standard sampling. However, the alignment objective does not capture such inference-time decoding procedures. We show that the existing alignment framework is sub-optimal in view of such inference-time methods. We then modify the alignment objective and propose a framework for inference-aware alignment (IAPO). We prove that for any inference-time decoding algorithm, the optimal solution that optimizes the inference-time win rate of the aligned policy against the reference policy is the solution to the typical RLHF problem with a transformation of the reward. This motivates us to provide the KL-regularized calibrate-and-transform RL (CTRL) algorithm to solve this problem, which involves a reward calibration step and a KL-regularized reward maximization step with a transformation of the calibrated reward. We particularize our study to two important inference-time strategies: best-of-N sampling and best-of-N jailbreaking, where N responses are sampled from the model and the one with the highest or lowest reward is selected. We propose specific transformations for these strategies and demonstrate that our framework offers significant improvements over existing state-of-the-art methods for language model alignment. Empirically, we outperform baselines that are designed without taking inference-time decoding into consideration by 8-12% and 4-9% on inference-time win rates over the Anthropic helpfulness and harmlessness dialog benchmark datasets.

Transformer-based large language models (LLMs) use the key-value (KV) cache to significantly accelerate inference by storing the key and value embeddings of past tokens. However, this cache consumes significant GPU memory. In this work, we introduce HashEvict, an algorithm that uses locality-sensitive hashing (LSH) to compress the KV cache. HashEvict quickly locates tokens in the cache that are cosine dissimilar to the current query token. This is achieved by computing the Hamming distance between binarized Gaussian projections of the current token query and cached token keys, with a projection length much smaller than the embedding dimension. We maintain a lightweight binary structure in GPU memory to facilitate these calculations. Unlike existing compression strategies that compute attention to determine token retention, HashEvict makes these decisions pre-attention, thereby reducing computational costs. Additionally, HashEvict is dynamic - at every decoding step, the key and value of the current token replace the embeddings of a token expected to produce the lowest attention score. We demonstrate that HashEvict can compress the KV cache by 30%-70% while maintaining high performance across reasoning, multiple-choice, long-context retrieval and summarization tasks., Comment: 10 pages, 6 figures, 2 tables

Continuum damage mechanics (CDM) is a popular framework for modelling crack propagation in solids. The CDM uses a damage parameter to quantitatively assess what one loosely calls `material degradation'. While this parameter is sometimes given a physical meaning, the mathematical equations for its evolution are generally not consistent with such physical interpretations. Curiously, degradation in the CDM may be viewed as a change of measures, wherein the damage variable appears as the Radon-Nikodym derivative. We adopt this point of view and use a probabilistic measure-valued description for the random microcracks underlying quasi-brittle damage. We show that the evolution of the underlying density may be described via killed diffusion as in the Feynman-Kac theory. Damage growth is then interpreted as the reduction in this measure over a region, which in turn quantifies the disruption of bonds through a loss of force-transmitting mechanisms between nearby material points. Remarkably, the evolution of damage admits an approximate closed-form solution. This brings forth substantive computational ease, facilitating fast yet accurate simulations of large dimensional problems. By selecting an appropriate killing rate, one accounts for the irreversibility of damage and thus eliminates the need for ad-hoc history-dependent routes typically employed, say, in phase field modelling of damage. Our proposal FeynKrack (a short form for Feynman-Kac crack propagator) is validated and demonstrated for its efficacy through several simulations on quasi-brittle damage. It also offers a promising stochastic route for future explorations of non-equilibrium thermodynamic aspects of damage.

In this paper, we consider nonparametric clustering of $M$ independent and identically distributed (i.i.d.) data streams generated from unknown distributions. The distributions of the $M$ data streams belong to $K$ underlying distribution clusters. Existing results on exponentially consistent nonparametric clustering algorithms, like single linkage-based (SLINK) clustering and $k$-medoids distribution clustering, assume that the maximum intra-cluster distance ($d_L$) is smaller than the minimum inter-cluster distance ($d_H$). First, in the fixed sample size (FSS) setting, we show that exponential consistency can be achieved for SLINK clustering under a less strict assumption, $d_I < d_H$, where $d_I$ is the maximum distance between any two sub-clusters of a cluster that partition the cluster. Note that $d_I < d_L$ in general. Our results show that SLINK is exponentially consistent for a larger class of problems than $k$-medoids distribution clustering. We also identify examples where $k$-medoids clustering is unable to find the true clusters, but SLINK is exponentially consistent. Then, we propose a sequential clustering algorithm, named SLINK-SEQ, based on SLINK and prove that it is also exponentially consistent. Simulation results show that the SLINK-SEQ algorithm requires fewer expected number of samples than the FSS SLINK algorithm for the same probability of error.

Path Integral Molecular Dynamics (PIMD) is a well established simulation technique to compute exact equilibrium properties for a quantum system using classical trajectories in an extended phase space. Standard PIMD simulations are numerically converged by systematically increasing the number of classical 'beads' or replicas used to represent each particle in the quantum system. Currently available scientific software for PIMD simulations leverage the massively parallel (with respect to number of beads) nature of the classical PIMD Hamiltonian. For particularly high-dimensional systems, contraction schemes designed to reduce the overall number of beads per particle required to achieve numerical convergence are also frequently employed. However, these implementations all rely on using the same number of beads to represent all atoms/particles, and become inefficient in systems with a large number of atoms where only a handful contribute significant quantum effects. Mixed time slicing (mixTS) offers an alternate path to efficient PIMD simulations by providing a framework where numerical convergence can be achieved with different numbers of beads for different types of atoms. Unfortunately, mixTS is not available in existing PIMD software. In this paper, we introduce MixPI for atomistic mixTS-PIMD simulations within the open-source software package CP2K. We demonstrate the use of MixPI in two different benchmark systems: we explore the use of mixTS in computing radial distributions functions for water, and in a more significant demonstration, for a solvated Co2+ ion represented as a classical Co3+ ion in water with an explicit, quantized 1024-bead electron localized on the metal ion.

The unique electronic properties of amorphous indium gallium zinc oxide (a-IGZO) thin films are closely associated with the complex charge dynamics of the materials. Conventional studies of charge transport in a-IGZO usually involve steady-state or transient measurements on field-effect transistors. Here, we employed microwave impedance microscopy to carry out position-dependent time-of-flight (TOF) experiments on a-IGZO devices, which offer spatial and temporal information of the underlying transport dynamics. The drift mobility calculated from the delay time between carrier injection and onset of TOF response is 2 - 3 cm2/Vs, consistent with the field-effect mobility from device measurements. The spatiotemporal conductivity data can be nicely fitted to a two-step function, corresponding to two coexisting mechanisms with a typical timescale of milliseconds. The competition between multiple-trap-and-release conduction through band-tail states and hopping conduction through deep trap states is evident from the fitting parameters. The underlying length scale and time scale of charge dynamics in a-IGZO are of fundamental importance for transparent and flexible nanoelectronics and optoelectronics, as well as emerging back-end-of-line applications., Comment: 15 pages, 5 figures

Pseudorandom codes are error-correcting codes with the property that no efficient adversary can distinguish encodings from uniformly random strings. They were recently introduced by Christ and Gunn [CRYPTO 2024] for the purpose of watermarking the outputs of randomized algorithms, such as generative AI models. Several constructions of pseudorandom codes have since been proposed, but none of them are robust to error channels that depend on previously seen codewords. This stronger kind of robustness is referred to as adaptive robustness, and it is important for meaningful applications to watermarking. In this work, we show the following. - Adaptive robustness: We show that the pseudorandom codes of Christ and Gunn are adaptively robust, resolving a conjecture posed by Cohen, Hoover, and Schoenbach [S&P 2025]. - Ideal security: We define an ideal pseudorandom code as one which is indistinguishable from the ideal functionality, capturing both the pseudorandomness and robustness properties in one simple definition. We show that any adaptively robust pseudorandom code for single-bit messages can be bootstrapped to build an ideal pseudorandom code with linear information rate, under no additional assumptions. - CCA security: In the setting where the encoding key is made public, we define a CCA-secure pseudorandom code in analogy with CCA-secure encryption. We show that any adaptively robust public-key pseudorandom code for single-bit messages can be used to build a CCA-secure pseudorandom code with linear information rate, in the random oracle model. These results immediately imply stronger robustness guarantees for generative AI watermarking schemes, such as the practical quality-preserving image watermarks of Gunn, Zhao, and Song (2024).

Owing to the ongoing COVID-19 pandemic and other recent global epidemics, epidemic simulation frameworks are gaining rapid significance. In this work, we present a workflow that will allow researchers to simulate the spread of an infectious disease under different intervention schemes. Our workflow is built using the Covasim simulator for COVID-19 alongside a network-based PREEMPT tool for vaccination. The Covasim simulator is a stochastic agent-based simulator with the capacity to test the efficacy of different intervention schemes. PREEMPT is a graph-theoretic approach that models epidemic intervention on a network using submodular optimization. By integrating the PREEMPT tool with the Covasim simulator, users will be able to test network diffusion based interventions for vaccination. The paper presents a description of this integrated workflow alongside preliminary results of our empirical evaluation for COVID-19.

We construct maximal supergravity in five-dimensions by 'oxidizing' the four-dimensional $\mathcal{N}=8$ theory. The relevant symmetries, the unitary symplectic group $USp(8)$ and the exceptional group $E_6$, are both presented in light-cone superspace and their connections with $SU(8)$ and $E_7$ highlighted. We explain a procedure to derive higher-point interaction vertices in both the 4- and 5-dimensional supergravity theories using exclusively the exceptional symmetries. Specific forms for the quartic and quintic interaction vertices in light-cone superspace are derived., Comment: 17 pages, 2 figures, minor edits, references added

We study the (in)feasibility of quantum pseudorandom notions in a quantum analog of the random oracle model, where all the parties, including the adversary, have oracle access to the same Haar random unitary. In this model, we show the following: - (Unbounded-query secure) pseudorandom unitaries (PRU) exist. Moreover, the PRU construction makes two calls to the Haar oracle. - We consider constructions of PRUs making a single call to the Haar oracle. In this setting, we show that unbounded-query security is impossible to achieve. We complement this result by showing that bounded-query secure PRUs do exist with a single query to the Haar oracle. - We show that multi-copy pseudorandom state generators and function-like state generators (with classical query access), making a single call to the Haar oracle, exist. Our results have two consequences: (a) when the Haar random unitary is instantiated suitably, our results present viable approaches for building quantum pseudorandom objects without relying upon one-way functions and, (b) for the first time, we show that the key length in pseudorandom unitaries can be generically shrunk (relative to the output length). Our results are also some of the first usecases of the new "path recording" formalism for Haar random unitaries, introduced in the recent breakthrough work of Ma and Huang., Comment: 51 pages; 4 figures

Generative models have shown impressive capabilities in synthesizing high-quality outputs across various domains. However, a persistent challenge is the occurrence of "hallucinations", where the model produces outputs that are plausible but invalid. While empirical strategies have been explored to mitigate this issue, a rigorous theoretical understanding remains elusive. In this paper, we develop a theoretical framework to analyze the learnability of non-hallucinating generative models from a learning-theoretic perspective. Our results reveal that non-hallucinating learning is statistically impossible when relying solely on the training dataset, even for a hypothesis class of size two and when the entire training set is truthful. To overcome these limitations, we show that incorporating inductive biases aligned with the actual facts into the learning process is essential. We provide a systematic approach to achieve this by restricting the facts set to a concept class of finite VC-dimension and demonstrate its effectiveness under various learning paradigms. Although our findings are primarily conceptual, they represent a first step towards a principled approach to addressing hallucinations in learning generative models.

Fundamental principles of quantum mechanics have inspired many new research directions, particularly in quantum cryptography. One such principle is quantum no-cloning which has led to the emerging field of revocable cryptography. Roughly speaking, in a revocable cryptographic primitive, a cryptographic object (such as a ciphertext or program) is represented as a quantum state in such a way that surrendering it effectively translates into losing the capability to use this cryptographic object. All of the revocable cryptographic systems studied so far have a major drawback: the recipient only receives one copy of the quantum state. Worse yet, the schemes become completely insecure if the recipient receives many identical copies of the same quantum state -- a property that is clearly much more desirable in practice. While multi-copy security has been extensively studied for a number of other quantum cryptographic primitives, it has so far received only little treatment in context of unclonable primitives. Our work, for the first time, shows the feasibility of revocable primitives, such as revocable encryption and revocable programs, which satisfy multi-copy security in oracle models. This suggest that the stronger notion of multi-copy security is within reach in unclonable cryptography more generally, and therefore could lead to a new research direction in the field., Comment: 42 pages

Urban air pollution hotspots pose significant health risks, yet their detection and analysis remain limited by the sparsity of public sensor networks. This paper addresses this challenge by combining predictive modeling and mechanistic approaches to comprehensively monitor pollution hotspots. We enhanced New Delhi's existing sensor network with 28 low-cost sensors, collecting PM2.5 data over 30 months from May 1, 2018, to Nov 1, 2020. Applying established definitions of hotspots to this data, we found the existence of additional 189 hidden hotspots apart from confirming 660 hotspots detected by the public network. Using predictive techniques like Space-Time Kriging, we identified hidden hotspots with 95% precision and 88% recall with 50% sensor failure rate, and with 98% precision and 95% recall with 50% missing sensors. The projected results of our predictive models were further compiled into policy recommendations for public authorities. Additionally, we developed a Gaussian Plume Dispersion Model to understand the mechanistic underpinnings of hotspot formation, incorporating an emissions inventory derived from local sources. Our mechanistic model is able to explain 65% of observed transient hotspots. Our findings underscore the importance of integrating data-driven predictive models with physics-based mechanistic models for scalable and robust air pollution management in resource-constrained settings.

A new discrete cohesive zone model (DCZM) is presented for modeling the interface behavior of adhesive-bonded thin laminates and sandwich panels. The proposed model treats the interface as a spring element and the adherent as a beam element. The use of the preceding assumptions facilitates the simplification of the computational framework reducing the problem from a 2D to 1D, thereby relaxing the requirements of maintaining the aspect ratio of elements in the finite element mesh. For thin laminates, the constitutive relation of the adhesive is represented by a bi-linear traction-separation law, whereas for sandwich panels, an exponential law is employed to model the adhesive behavior. In order to validate the proposed model for thin laminates, simulations of three established fracture tests: DCB, ENF, and MMB have been undertaken. Additionally, for the sandwich panel, two experiments documented in the literature have been simulated for assessing the efficacy of the modelling. One experiment has a mode-I interface failure and the other one a mode-II interface failure between the core and skin. It has been observed that the model is not sensitive to either the element size or the load step size. The results have been compared with reported (benchmark) numerical, analytical, and experimental findings. The proposed methodology for thin laminates offers a significant reduction in the computational effort (reduced number of unknown degrees of freedom compared to existing methods) with no compromise on the accuracy of the predictions. Specifically, it reduces the unknown degrees of freedom by more than 25\% compared to the corresponding mesh used in existing continuum cohesive zone model (CCZM) approaches. The Newton-Raphson solver can achieve quick convergence and no line search feature is required. The proposed algorithm is easy to implement on any computational platform.

We present a novel dataset aimed at advancing danger analysis and assessment by addressing the challenge of quantifying danger in video content and identifying how human-like a Large Language Model (LLM) evaluator is for the same. This is achieved by compiling a collection of 100 YouTube videos featuring various events. Each video is annotated by human participants who provided danger ratings on a scale from 0 (no danger to humans) to 10 (life-threatening), with precise timestamps indicating moments of heightened danger. Additionally, we leverage LLMs to independently assess the danger levels in these videos using video summaries. We introduce Mean Squared Error (MSE) scores for multimodal meta-evaluation of the alignment between human and LLM danger assessments. Our dataset not only contributes a new resource for danger assessment in video content but also demonstrates the potential of LLMs in achieving human-like evaluations., Comment: Preprint

Spectral Graph Convolutional Networks (GCNs) have gained popularity in graph machine learning applications due, in part, to their flexibility in specification of network propagation rules. These propagation rules are often constructed as polynomial filters whose coefficients are learned using label information during training. In contrast to learned polynomial filters, explicit filter functions are useful in capturing relationships between network topology and distribution of labels across the network. A number of algorithms incorporating either approach have been proposed; however the relationship between filter functions and polynomial approximations is not fully resolved. This is largely due to the ill-conditioned nature of the linear systems that must be solved to derive polynomial approximations of filter functions. To address this challenge, we propose a novel Arnoldi orthonormalization-based algorithm, along with a unifying approach, called G-Arnoldi-GCN that can efficiently and effectively approximate a given filter function with a polynomial. We evaluate G-Arnoldi-GCN in the context of multi-class node classification across ten datasets with diverse topological characteristics. Our experiments show that G-Arnoldi-GCN consistently outperforms state-of-the-art methods when suitable filter functions are employed. Overall, G-Arnoldi-GCN opens important new directions in graph machine learning by enabling the explicit design and application of diverse filter functions. Code link: https://github.com/mustafaCoskunAgu/GArnoldi-GCN

Influence maximization--the problem of identifying a subset of k influential seeds (vertices) in a network--is a classical problem in network science with numerous applications. The problem is NP-hard, but there exist efficient polynomial time approximations. However, scaling these algorithms still remain a daunting task due to the complexities associated with steps involving stochastic sampling and large-scale aggregations. In this paper, we present a new parallel distributed approximation algorithm for influence maximization with provable approximation guarantees. Our approach, which we call GreediRIS, leverages the RandGreedi framework--a state-of-the-art approach for distributed submodular optimization--for solving a step that computes a maximum k cover. GreediRIS combines distributed and streaming models of computations, along with pruning techniques, to effectively address the communication bottlenecks of the algorithm. Experimental results on up to 512 nodes (32K cores) of the NERSC Perlmutter supercomputer show that GreediRIS can achieve good strong scaling performance, preserve quality, and significantly outperform the other state-of-the-art distributed implementations. For instance, on 512 nodes, the most performant variant of GreediRIS achieves geometric mean speedups of 28.99x and 36.35x for two different diffusion models, over a state-of-the-art parallel implementation. We also present a communication-optimized version of GreediRIS that further improves the speedups by two orders of magnitude.

With the rapid advances in deep learning and smart manufacturing in Industry 4.0, there is an imperative for high-throughput, high-performance, and fully integrated visual inspection systems. Most anomaly detection approaches using defect detection datasets, such as MVTec AD, employ one-class models that require fitting separate models for each class. On the contrary, unified models eliminate the need for fitting separate models for each class and significantly reduce cost and memory requirements. Thus, in this work, we experiment with considering a unified multi-class setup. Our experimental study shows that multi-class models perform at par with one-class models for the standard MVTec AD dataset. Hence, this indicates that there may not be a need to learn separate object/class-wise models when the object classes are significantly different from each other, as is the case of the dataset considered. Furthermore, we have deployed three different unified lightweight architectures on the CPU and an edge device (NVIDIA Jetson Xavier NX). We analyze the quantized multi-class anomaly detection models in terms of latency and memory requirements for deployment on the edge device while comparing quantization-aware training (QAT) and post-training quantization (PTQ) for performance at different precision widths. In addition, we explored two different methods of calibration required in post-training scenarios and show that one of them performs notably better, highlighting its importance for unsupervised tasks. Due to quantization, the performance drop in PTQ is further compensated by QAT, which yields at par performance with the original 32-bit Floating point in two of the models considered., Comment: 20 pages

Common random string model is a popular model in classical cryptography. We study a quantum analogue of this model called the common Haar state (CHS) model. In this model, every party participating in the cryptographic system receives many copies of one or more i.i.d Haar random states. We study feasibility and limitations of cryptographic primitives in this model and its variants: - We present a construction of pseudorandom function-like states with security against computationally unbounded adversaries, as long as the adversaries only receive (a priori) bounded number of copies. By suitably instantiating the CHS model, we obtain a new approach to construct pseudorandom function-like states in the plain model. - We present separations between pseudorandom function-like states (with super-logarithmic length) and quantum cryptographic primitives, such as interactive key agreement and bit commitment, with classical communication. To show these separations, we prove new results on the indistinguishability of identical versus independent Haar states against LOCC (local operations, classical communication) adversaries.

Task-specific functional MRI (fMRI) images provide excellent modalities for studying the neuronal basis of cognitive processes. We use fMRI data to formulate and solve the problem of deconvolving task-specific aggregate neuronal networks into a set of basic building blocks called canonical networks, to use these networks for functional characterization, and to characterize the physiological basis of these responses by mapping them to regions of the brain. Our results show excellent task-specificity of canonical networks, i.e., the expression of a small number of canonical networks can be used to accurately predict tasks; generalizability across cohorts, i.e., canonical networks are conserved across diverse populations, studies, and acquisition protocols; and that canonical networks have strong anatomical and physiological basis. From a methods perspective, the problem of identifying these canonical networks poses challenges rooted in the high dimensionality, small sample size, acquisition variability, and noise. Our deconvolution technique is based on non-negative matrix factorization (NMF) that identifies canonical networks as factors of a suitably constructed matrix. We demonstrate that our method scales to large datasets, yields stable and accurate factors, and is robust to noise., Comment: 9 pages, 5 figures

Aligning large language models (LLMs) with human preferences is critical for their deployment. Recently, decoding-time alignment has emerged as an effective plug-and-play technique that requires no fine-tuning of model parameters. However, generating text that achieves both high reward and high likelihood remains a significant challenge. Existing methods often fail to generate high-reward text or incur substantial computational costs. In this paper, we propose Cascade Reward Sampling (CARDS) to address both issues, guaranteeing the generation of high-reward and high-likelihood text with significantly low costs. Based on our analysis of reward models (RMs) on incomplete text and our observation that high-reward prefixes induce high-reward complete text, we use rejection sampling to iteratively generate small semantic segments to form such prefixes. The segment length is dynamically determined by the predictive uncertainty of LLMs. This strategy guarantees desirable prefixes for subsequent generations and significantly reduces wasteful token re-generations and the number of reward model scoring. Our experiments demonstrate substantial gains in both generation efficiency and alignment ratings compared to the baselines, achieving five times faster text generation and 99\% win-ties in GPT-4/Claude-3 helpfulness evaluation.

Safety classifiers are critical in mitigating toxicity on online forums such as social media and in chatbots. Still, they continue to be vulnerable to emergent, and often innumerable, adversarial attacks. Traditional automated adversarial data generation methods, however, tend to produce attacks that are not diverse, but variations of previously observed harm types. We formalize the task of automated adversarial discovery for safety classifiers - to find new attacks along previously unseen harm dimensions that expose new weaknesses in the classifier. We measure progress on this task along two key axes (1) adversarial success: does the attack fool the classifier? and (2) dimensional diversity: does the attack represent a previously unseen harm type? Our evaluation of existing attack generation methods on the CivilComments toxicity task reveals their limitations: Word perturbation attacks fail to fool classifiers, while prompt-based LLM attacks have more adversarial success, but lack dimensional diversity. Even our best-performing prompt-based method finds new successful attacks on unseen harm dimensions of attacks only 5\% of the time. Automatically finding new harmful dimensions of attack is crucial and there is substantial headroom for future research on our new task., Comment: Published at Fourth Workshop on TrustworthyNLP (TrustNLP) at NAACL 2024

Classifiers are used throughout industry to enforce policies, ranging from the detection of toxic content to age-appropriate content filtering. While these classifiers serve important functions, it is also essential that they are built in ways that minimize unfair biases for users. One such fairness consideration is called group fairness, which desires that different sub-population of users receive equal treatment. This is a well-studied problem in the context of 'classical' classifiers. However, the emergence of prompt-based language model (LM) decision making has created new opportunities to solve text-based classification tasks, and the fairness properties of these new classifiers are not yet well understood. Further, the `remediation toolkit' is incomplete for LM-based decision makers and little is understood about how to improve decision maker group fairness while maintaining classifier performance. This work sets out to add more tools to that toolbox. We introduce adaptations of existing effective approaches from the classical classifier fairness to the prompt-based classifier space. We also devise simple methods that take advantage of the new structure of prompt-based decision makers and operate at the prompt level. We compare these approaches empirically on real data. Our results suggest that adaptations of approaches that are effective for classical classifiers remain effective in the LM-based classifier environment. However, there is room for further exploration of prompt-based remediation methods (and other remediation methods that take advantage of LM structure).

Unclonable cryptography utilizes the principles of quantum mechanics to addresses cryptographic tasks that are impossible classically. We introduce a novel unclonable primitive in the context of secret sharing, called unclonable secret sharing (USS). In a USS scheme, there are $n$ shareholders, each holding a share of a classical secret represented as a quantum state. They can recover the secret once all parties (or at least $t$ parties) come together with their shares. Importantly, it should be infeasible to copy their own shares and send the copies to two non-communicating parties, enabling both of them to recover the secret. Our work initiates a formal investigation into the realm of unclonable secret sharing, shedding light on its implications, constructions, and inherent limitations. ** Connections: We explore the connections between USS and other quantum cryptographic primitives such as unclonable encryption and position verification, showing the difficulties to achieve USS in different scenarios. **Limited Entanglement: In the case where the adversarial shareholders do not share any entanglement or limited entanglement, we demonstrate information-theoretic constructions for USS. **Large Entanglement: If we allow the adversarial shareholders to have unbounded entanglement resources (and unbounded computation), we prove that unclonable secret sharing is impossible. On the other hand, in the quantum random oracle model where the adversary can only make a bounded polynomial number of queries, we show a construction secure even with unbounded entanglement. Furthermore, even when these adversaries possess only a polynomial amount of entanglement resources, we establish that any unclonable secret sharing scheme with a reconstruction function implementable using Cliffords and logarithmically many T-gates is also unattainable.

This paper compares two actuator line methodologies for modelling wind turbines employing high-order h/p solvers and large-eddy simulations. The methods combine the accuracy of high-order solvers (in this work the maximum order is 6) with the computational efficiency of actuator lines to capture the aerodynamic effects of wind turbine blades. Comparisons with experiments validate the actuator line methodologies. We explore the effects of the polynomial order and the smoothing parameter associated with the Gaussian regularization function, and use them to blend the actuator line forcing in the high-order computational mesh, to show that both parameters influence the distribution of forces along the blades and the turbine wake. The greatest impact is obtained when the polynomial order is increased, allowing one to better capture the physics without requiring new meshes. When comparing the actuator line methodologies, we show the advantages of performing weighted sums, over element averages, to compute the blade velocities and forces in high-order solvers. For low-order simulations (low polynomial orders), both methods provide similar results, but as the polynomial order is increased, the weighted sum method shows smoother thrust/torque distributions and better wake resolution. Furthermore, cell averaging introduces nonphysical oscillations when increasing the polynomial order beyond 3 (4th order accuracy).

Predicting the spatiotemporal variation in streamflow along with uncertainty quantification enables decision-making for sustainable management of scarce water resources. Process-based hydrological models (aka physics-based models) are based on physical laws, but using simplifying assumptions which can lead to poor accuracy. Data-driven approaches offer a powerful alternative, but they require large amount of training data and tend to produce predictions that are inconsistent with physical laws. This paper studies a constrained reasoning and learning (CRL) approach where physical laws represented as logical constraints are integrated as a layer in the deep neural network. To address small data setting, we develop a theoretically-grounded training approach to improve the generalization accuracy of deep models. For uncertainty quantification, we combine the synergistic strengths of Gaussian processes (GPs) and deep temporal models (i.e., deep models for time-series forecasting) by passing the learned latent representation as input to a standard distance-based kernel. Experiments on multiple real-world datasets demonstrate the effectiveness of both CRL and GP with deep kernel approaches over strong baseline methods.

We present an approximate semiclassical (SC) framework for mixed quantized dynamics in Wigner phase space in a two-part series. In the first article, we introduced the Adiabatic Hybrid Wigner Dynamics (AHWD) method that allows for a few important `system' degrees of freedom to be quantized using high-level Double Herman-Kluk SC theory while describing the rest (the `bath') using classical-limit Linearized SC theory. In this second article, we extend our hybrid Wigner dynamics to nonadiabatic processes. The resulting Nonadiabatic Hybrid Wigner Dynamics (NHWD) has two variants that differ in the choice of degrees of freedom to be quantized. Specifically, we introduce NHWD(E) where only the electronic state variables are quantized and the NHWD(V) where both electronic state variables and a handful of strongly coupled nuclear modes are quantized. We show that while NHWD(E) proves accurate for a wide range of scattering models and spin-boson models, systems where a few nuclear modes are strongly coupled to electronic states require NHWD(V) to accurately capture the long-time dynamics. Taken together, we show that AHWD and NHWD represent a new framework for SC simulations of high-dimensional systems with significant quantum effects.

The Wigner phase space formulation of quantum mechanics is a complete framework for quantum dynamic calculations that elegantly highlights connections with classical dynamics. In this series of two articles, building upon previous efforts, we derive the full hierarchy of approximate semiclassical (SC) dynamic methods for adiabatic and non-adiabatic problems in Wigner phase space. In paper I, focusing on adiabatic single surface processes, we derive the well-known Double Herman-Kluk (DHK) approximation for real-time correlation functions in Wigner phase space, and connect it to the Linearized SC (LSC) approximation through a stationary phase approximation. We exploit this relationship to introduce a new hybrid SC method, termed Adiabatic Hybrid Wigner Dynamics (AHWD) that allows for a few important `system' degrees of freedom (dofs) to be treated at the DHK level, while treating the rest of the dofs (the `bath') at the LSC level. AHWD is shown to accurately capture quantum interference effects in models of coupled oscillators, and the decoherence of vibrational probability density of a model I$_2$ Morse oscillator coupled to an Ohmic thermal bath. We show that AHWD significantly mitigates the sign-problem and employs a reduced dimensional prefactor bringing calculations of complex system-bath problems within the reach of SC methods. Paper II focuses on extending this hybrid SC dynamics to nonadiabatic processes.

We present a hybrid Path Integral Monte Carlo (hPIMC) algorithm to calculate real-time quantum thermal correlation functions and demonstrate its application to open quantum systems. The hPIMC algorithm leverages the successes of classical PIMC as a computational tool for high-dimensional system studies by exactly simulating dissipation using the Feynman-Vernon influence functional on a classical computer. We achieve a quantum speed-up over the classical algorithm by computing short-time matrix elements of the quantum propagator on a quantum computer. We show that the component of imaginary-time evolution can be performed accurately using the recently developed Probabilistic Imaginary-Time Evolution (PITE) algorithm, and we introduce a novel low-depth circuit for approximate real-time evolution under the kinetic energy operator using a Discrete Variable Representation (DVR). We test the accuracy of the approximation by computing the position-position thermal correlation function of a proton transfer reaction.