Search

We study watermarking schemes for language models with provable guarantees. As we show, prior works offer no robustness guarantees against adaptive prompting: when a user queries a language model more than once, as even benign users do. And with just a single exception (Christ and Gunn, 2024), prior works are restricted to zero-bit watermarking: machine-generated text can be detected as such, but no additional information can be extracted from the watermark. Unfortunately, merely detecting AI-generated text may not prevent future abuses. We introduce multi-user watermarks, which allow tracing model-generated text to individual users or to groups of colluding users, even in the face of adaptive prompting. We construct multi-user watermarking schemes from undetectable, adaptively robust, zero-bit watermarking schemes (and prove that the undetectable zero-bit scheme of Christ, Gunn, and Zamir (2024) is adaptively robust). Importantly, our scheme provides both zero-bit and multi-user assurances at the same time. It detects shorter snippets just as well as the original scheme, and traces longer excerpts to individuals. The main technical component is a construction of message-embedding watermarks from zero-bit watermarks. Ours is the first generic reduction between watermarking schemes for language models. A challenge for such reductions is the lack of a unified abstraction for robustness -- that marked text is detectable even after edits. We introduce a new unifying abstraction called AEB-robustness. AEB-robustness provides that the watermark is detectable whenever the edited text "approximates enough blocks" of model-generated output., Comment: 39 pages

Current quantum computer designs will not scale. To scale beyond small prototypes, quantum architectures will likely adopt a modular approach with clusters of tightly connected quantum bits and sparser connections between clusters. We exploit this clustering and the statically-known control flow of quantum programs to create tractable partitioning heuristics which map quantum circuits to modular physical machines one time slice at a time. Specifically, we create optimized mappings for each time slice, accounting for the cost to move data from the previous time slice and using a tunable lookahead scheme to reduce the cost to move to future time slices. We compare our approach to a traditional statically-mapped, owner-computes model. Our results show strict improvement over the static mapping baseline. We reduce the non-local communication overhead by 89.8\% in the best case and by 60.9\% on average. Our techniques, unlike many exact solver methods, are computationally tractable., Comment: Appears in CF'20: ACM International Conference on Computing Frontiers

Mathematical models of SARS-CoV-2 spread are used for guiding the design of mitigation steps aimed at containing and decelerating the contagion, and at identifying impending breaches of health care system surge capacity. The challenges of having only lacunary information about daily new infections are compounded by the geographic heterogeneity of the population. To address this problem, we propose to account for the differences between rural and urban settings using network-based, distributed models where the spread of the pandemic is described in distinct local cohorts with nested SEIR models. The setting of the model parameters takes into account the fact that SARS-CoV-2 transmission occurs mostly via human-to-human contact, and that the frequency of contact among individuals differs between urban and rural areas, and may change over time. Moreover, the probability that the virus spreads into an uninfected community is associated with influx of individuals from other communities where the infection is present. To account for these important aspects, each node of the network is characterized by the frequency of contact between its members and by its level of connectivity with other nodes. Census and cell phone data can be used to set up the adjacency matrix of the network, which can, in turn, be modified to account for different levels of mitigation measures. In order to make the network SEIR model that we propose easy to customize, it is formulated in terms of easily interpretable parameters that can be estimated from available community level data. The models parameters are estimated with Bayesian techniques using COVID-19 data for the states of Ohio and Michigan. The network model also gives rise to a geographically distributed computational model that explains the geographic dynamics of the contagion, e.g., in larger cities surrounded by suburban and rural areas., Comment: 21 pages, 15 figures

In this article, we consider a dynamic epidemiology model for the spread of the COVID-19 infection. Starting from the classical SEIR model, the model is modified so as to better describe characteristic features of the underlying pathogen and its infectious modes. In line with the large number of secondary infections not related to contact with documented infectious individuals, the model includes a cohort of asymptomatic or oligosymptomatic infectious individuals, not accounted for in the data of new daily counts of infections. A Bayesian particle filtering algorithm is used to update dynamically the relevant cohort and simultaneously estimate the transmission rate as the new data on the number of new infections and disease related death become available. The underlying assumption of the model is that the infectivity rate is dynamically changing during the epidemics, either because of a mutation of the pathogen or in response to mitigation and containment measures. The sequential Bayesian framework naturally provides a quantification of the uncertainty in the estimate of the model parameters, including the reproduction number, and of the size of the different cohorts. Moreover, we introduce a dimensionless quantity, which is the equilibrium ratio between asymptomatic and symptomatic cohort sizes, and propose a simple formula to estimate the quantity. This ratio leads naturally to another dimensionless quantity that plays the role of the basic reproduction number $R_0$ of the model. When we apply the model and particle filter algorithm to COVID-19 infection data from several counties in Northeastern Ohio and Southeastern Michigan we found the proposed reproduction number $R_0$ to have a consistent dynamic behavior within both states, thus proving to be a reliable summary of the success of the mitigation measures., Comment: 21 pages, 8 figures

We present a general decomposition of the Generalized Toffoli, and for completeness, the multi-target gate using an arbitrary number of clean or dirty ancilla. While prior work has shown how to decompose the Generalized Toffoli using 0, 1, or $O(n)$ many clean ancilla and 0, 1, and $n-2$ dirty ancilla, we provide a generalized algorithm to bridge the gap, i.e. this work gives an algorithm to generate a decomposition for any number of clean or dirty ancilla. While it is hard to guarantee optimality, our decompositions guarantee a decrease in circuit depth as the number of ancilla increases., Comment: 10 pages, 5 figures

It is important to understand how the outcome of an election can be modified by an agent with control over the structure of the election. Electoral control has been studied for many election systems, but for all studied systems the winner problem is in P, and so control is in NP. There are election systems, such as Kemeny, that have many desirable properties, but whose winner problems are not in NP. Thus for such systems control is not in NP, and in fact we show that it is typically complete for $\Sigma_2^p$ (i.e., ${\rm NP}^{\rm NP}$, the second level of the polynomial hierarchy). This is a very high level of complexity. Approaches that perform quite well for solving NP problems do not necessarily work for $\Sigma_2^p$-complete problems. However, answer set programming is suited to express problems in $\Sigma_2^p$, and we present an encoding for Kemeny control., Comment: A version of this paper will appear in the Proceedings of AAAI-2019