Towards Sharp Inapproximability For Any 2-CSP

By Per Austrin. 2007

972 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Numerical Analysis, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Numerical Analysis

In Algorithms & Complexity

Citations in the corpus

On Distributed Differential Privacy and Counting Distinct Elements (2020, background): “In central DP, the exponential mechanism of [35] yields an ε -DP algorithm for Selection when n = O ε (log D ).”
Marginal Release Under Local Differential Privacy (2017, positive): “To ensure DP, it uses the exponential mechanism [26] to sample a k -way marginal whose projection at a certain point in the true data is far from the corresponding value for the candidate.”
A Comprehensive Comparison of Multiparty Secure Additions with Differential Privacy (2015, background): “Differential privacy of released data is achieved by an exponential mechanism that samples existing records or items with an exponentially distributed probability [41].”
Algorithmic stability for adaptive data analysis (2015, methodology): “When considering arbitrary search queries over an arbitrary ﬁnite range, the optimal algorithm is the Exponential Mechanism [MT07].”
Differentially Private Empirical Risk Minimization (2009, positive): “In the notation of McSherry and Talwar (2007), the zmin = OPT , the base measure µ is uniform on [m], and St = {i : zi zmin + t}.”
A Statistical Framework for Differential Privacy (2008, positive): “Hence Q n has density A general data release mechanism is the exponential mechanism (McSherry and Talwar, 2007) which is deﬁned as follows.”
Universally utility-maximizing privacy mechanisms (2008, background): “The use of abstract “utility functions” in McSherry and Talwar [16] has a similar ﬂavor to our use of loss functions, though the motivations and goals of their work and ours are unrelated.”
Differentially private combinatorial optimization (2009, methodology): “• While the exponential mechanism of [25] is an easy way to obtain computationally inefficient private approximation algorithms for some problems, the approximation guarantees given by a direct application of this can be far from optimal (e.”
The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy (2012, background): “The exponential mechanism [MT07, BLR08] is a non-interactive privacy preserving mechanism, which is typically intractable.”
Private Convex Optimization for Empirical Risk Minimization with Applications to High-dimensional Regression (2012, methodology): “by McSherry and Talwar (2007). The second algorithm (Algorithm Samp-Agg ) is based on the Sample and Aggregate Framework by Nissim et al.”
Composable and versatile privacy via truncated CDP (2018, methodology): “The first algorithm for solving this problem is the exponential mechanism [18], defined by”
Mining Frequent Patterns with Differential Privacy (2013, methodology): “In literature, there are two well established techniques to achieve differential privacy: Laplace Mechanism [9] and Exponential Mechanism [18].”
Differentially Private Algorithms for Empirical Machine Learning (2014, neutral): “ Differentially private algorithms satisfy the following composition properties that allow us to design complex workﬂows by p iecing together differentially private algorithms. THEOREM 1 (COMPOSITION [20]). LetM1(·)and M2(·)be ǫ1- andǫ2-differentially private algorithms. Then, •Sequential Compositon”
Pufferfish Privacy Mechanisms for Correlated Data (2016, neutral): “There is a body of work on diﬀerentially private mechanisms [28, 27, 4, 3, 7] – see surveys [30, 9].”
Near-optimal Differentially Private Principal Components (2012, neutral): “There are several standard approaches for designing differentially-private data-mining algorithms, including input perturbation [2], output perturbation [9], the exponential mechanism [22], and objective perturbation [6].”
Privacy-Preserving Collaborative Deep Learning with Irregular Participants. (2018, background): “Thus, for the query whose outputs are not numeric, Mcsherry et al. [37] proposed Exponential mechanism that selects an output r from the output domain R .”
Study : Privacy Preserving Release of Spatio-temporal Density in Paris (2014, methodology): “Three principal techniques for achieving (probabilistic) DP are Laplace mechanism [10] (LPA), Gaussian mechanism [15] (GPA), and Exponential mechanism [22].”
Meritocratic Fairness for Cross-Population Selection (2017, methodology): “Speciﬁcally, we adopt variants of the “report noisy max” algorithm (Dwork & Roth, 2014), and Raskhodnikova and Smith’s “expo-nential mechanism for scores with varying sensitivities” (Raskhodnikova & Smith, 2016), which is itself a variant of the exponential mechanism (McSherry & Talwar, 2007).”
Differentially Private Online Learning (2011, neutral): “ly inefﬁcient updates (see [21] for a detailed discussion) . However, just for completeness, we note that by using techniques similar to our Private OCP framework and using exponential mechanism (see [30]), one can analyze this algorithm as well to guarantee differential privacy along with O˜( √ T) ”
Scalable privacy-preserving data sharing methodology for genome-wide association studies: an application to iDASH healthcare privacy protection challenge (2014, methodology): “One of the methods, due to [2], is called the Laplace mechanism (Definition 4), and the other method, due to [7], is called the exponential mechanism (Definition 5).”