A method for the catalytic, enantioselective, intermolecular, 1,2-sulfenoamination of alkenes is described. Functionalization is achieved through the intermediacy of an enantioenriched, ...configurationally stable thiiranium ion generated by Lewis base activation of a readily available sulfur electrophile. A diverse set of anilines and benzylamines react with different styrenes to afford products in good yield and stereoselectivity. Downstream manipulation of the products is facilitated by deprotonation of the amines to enable carbon–sulfur bond cleavage.
Misapplication of statistical data analysis is a common cause of spurious discoveries in scientific research. Existing approaches to ensuring the validity of inferences drawn from data assume a fixed ...procedure to be performed, selected before the data are examined. In common practice, however, data analysis is an intrinsically adaptive process, with new analyses generated on the basis of data exploration, as well as the results of previous analyses on the same data. We demonstrate a new approach for addressing the challenges of adaptivity based on insights from privacy-preserving data analysis. As an application, we show how to safely reuse a holdout data set many times to validate the results of adaptively chosen analyses.
We study the power of interactivity in local differential privacy. First, we focus on the difference between fully interactive and sequentially interactive protocols. Sequentially interactive ...protocols may query users adaptively in sequence, but they cannot return to previously queried users. The vast majority of existing lower bounds for local differential privacy apply only to sequentially interactive protocols, and before this paper it was not known whether fully interactive protocols were more powerful. We resolve this question. First, we classify locally private protocols by their compositionality, the multiplicative factor by which the sum of a protocol's single-round privacy parameters exceeds its overall privacy guarantee. We then show how to efficiently transform any fully interactive compositional protocol into an equivalent sequentially interactive protocol with a blowup in sample complexity linear in this compositionality. Next, we show that our reduction is tight by exhibiting a family of problems such that any sequentially interactive protocol requires this blowup in sample complexity over a fully interactive compositional protocol. We then turn our attention to hypothesis testing problems. We show that for a large class of compound hypothesis testing problems - which include all simple hypothesis testing problems as a special case - a simple noninteractive test is optimal among the class of all (possibly fully interactive) tests.
Motivated by tensions between data privacy for individual citizens and societal priorities such as counterterrorism and the containment of infectious disease, we introduce a computational model that ...distinguishes between parties for whom privacy is explicitly protected, and those for whom it is not (the targeted subpopulation). The goal is the development of algorithms that can effectively identify and take action upon members of the targeted subpopulation in a way that minimally compromises the privacy of the protected, while simultaneously limiting the expense of distinguishing members of the two groups via costly mechanisms such as surveillance, background checks, or medical testing. Within this framework, we provide provably privacy-preserving algorithms for targeted search in social networks. These algorithms are natural variants of common graph search methods, and ensure privacy for the protected by the careful injection of noise in the prioritization of potential targets. We validate the utility of our algorithms with extensive computational experiments on two large-scale social network datasets.
How to Use Heuristics for Differential Privacy Neel, Seth V.; Roth, Aaron L.; Wu, Zhiwei Steven
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS),
2019-Nov.
Conference Proceeding
We develop theory for using heuristics to solve computationally hard problems in differential privacy. Heuristic approaches have enjoyed tremendous success in machine learning, for which performance ...can be empirically evaluated. However, privacy guarantees cannot be evaluated empirically, and must be proven --- without making heuristic assumptions. We show that learning problems over broad classes of functions --- those that have polynomially sized universal identification sets --- can be solved privately and efficiently, assuming the existence of a non-private oracle for solving the same problem. Our first algorithm yields a privacy guarantee that is contingent on the correctness of the oracle. We then give a reduction which applies to a class of heuristics which we call certifiable, which allows us to convert oracle-dependent privacy guarantees to worst-case privacy guarantee that hold even when the heuristic standing in for the oracle might fail in adversarial ways. Finally, we consider classes of functions for which both they and their dual classes have small universal identification sets. This includes most classes of simple boolean functions studied in the PAC learning literature, including conjunctions, disjunctions, parities, and discrete halfspaces. We show that there is an efficient algorithm for privately constructing synthetic data for any such class, given a non-private learning oracle. This in particular gives the first oracle-efficient algorithm for privately generating synthetic data for contingency tables. The most intriguing question left open by our work is whether or not every problem that can be solved differentially privately can be privately solved with an oracle-efficient algorithm. While we do not resolve this, we give a barrier result that suggests that any generic oracle-efficient reduction must fall outside of a natural class of algorithms (which includes the algorithms given in this paper).
Selling privacy at auction Ghosh, Arpita; Roth, Aaron
Games and economic behavior,
05/2015, Letnik:
91
Journal Article
Recenzirano
Odprti dostop
We study markets for private data using differential privacy. We consider a setting in which a data analyst wishes to buy information from a population from which he can estimate some statistic. The ...analyst wishes to obtain an accurate estimate cheaply, while the owners of the private data experience some cost for their loss of privacy. Agents are rational and we wish to design truthful mechanisms.
We show that such problems can naturally be viewed and solved as variants of multi-unit procurement auctions. We derive auctions for two natural settings:1.The analyst has a fixed accuracy goal and wishes to minimize his payments.2.The analyst has a budget and wishes to maximize his accuracy. In both results, we treat each agent's cost for privacy as insensitive information. We then show that no individually rational mechanism can compensate individuals for the privacy loss incurred due to their reported valuations for privacy.
PDF
