Abstract. We consider the problem of estimating the average of a huge set of values. That is, given oracle access to an arbitrary function f: {0, 1} n P −n → [0, 1], we wish to estimate 2 x∈{0,1} n f(x) upto an additive error of ǫ. We are allowed to employ a randomized algorithm that may err with probability at most δ. We survey known algorithms for this problem and focus on the ideas underlying their construction. In particular, we present an algorithm that makes O(ǫ −2 · log(1/δ)) queries and uses n + O(log(1/ǫ)) + O(log(1/δ)) coin tosses, both complexities being very close to the corresponding lower bounds.
Abstract. We consider the problem of estimating the average of a huge set of values. That is, given oracle access to an arbitrary function f: {0, 1} n P −n → [0, 1], we wish to estimate 2 x∈{0,1} n f(x) upto an additive error of ǫ. We are allowed to employ a randomized algorithm that may err with probability at most δ. We survey known algorithms for this problem and focus on the ideas underlying their construction. In particular, we present an algorithm that makes O(ǫ −2 · log(1/δ)) queries and uses n + O(log(1/ǫ)) + O(log(1/δ)) coin tosses, both complexities being very close to the corresponding lower bounds.
Integral equations with Lipschitz kernels and right-hand sides are intractable for deterministic methods, the complexity increases exponentially in the dimension d . This is true even if we only want to compute a single function value of the solution. For this latter problem we study coin tossing algorithms (or restricted Monte Carlo methods), where only random bits are allowed. We construct a restricted Monte Carlo method with error ε that uses roughly ε −2 function values and only d log 2 ε random bits. The number of arithmetic operations is of the order ε −2 + d log 2 ε. Hence, the cost of our algorithm increases only mildly with the dimension d , we obtain the upper bound C · (ε −2 + d log 2 ε) for the complexity. In particular, the problem is tractable for coin tossing algorithms.
The computational equivalence between approximate counting and sampling is well established for polynomial-time algorithms. The most efficient general reduction from counting to sampling is based on simulated annealing. In this approach, the counting problem is formulated as estimating the ratio Q = Z(βmax)/Z(βmin) between partition functions Z(β) = Σx∈Ω exp(βH(x)) of Gibbs distributions μβ over Ω with Hamiltonian H, given access to a sampling oracle for μβ at any β ∈ [βmin, βmax]. The sample complexity (measured by the number of oracle calls) is typically expressed in terms of q and h, which respectively bound ln Q and H. The best upper bound achieved by known annealing algorithms with relative error ε is O(qε−2 log h). However, all known algorithms attaining this near-optimal complexity are inherently sequential, or adaptive: the queried parameters β depend on previous samples.
Given two distributions P and Q over a high-dimensional domain {0,1}n, and a parameter ε, the goal of distance estimation is to determine the statistical distance between P and Q, up to an additive tolerance ±ε. Since exponential lower bounds (in n) are known for the problem in the standard sampling model, research has focused on richer query models where one can draw conditional samples. This paper presents the first polynomial query distance estimator in the conditional sampling model (COND). We base our algorithm on the relatively weaker \textit{subcube conditional} sampling (SUBCOND) oracle, which draws samples from the distribution conditioned on some of the dimensions. SUBCOND is a promising model for widespread practical use because it captures the natural behavior of discrete samplers. Our algorithm makes O~(n3/ε5) queries to SUBCOND.
The noise sensitivity of a Boolean function f: {0,1}^n - > {0,1} is one of its fundamental properties. For noise parameter delta, the noise sensitivity is denoted as NS_{delta}[f]. This quantity is defined as follows: First, pick x = (x_1,...,x_n) uniformly at random from {0,1}^n, then pick z by flipping each x_i independently with probability delta. NS_{delta}[f] is defined to equal Pr [f(x) != f(z)]. Much of the existing literature on noise sensitivity explores the following two directions: (1) Showing that functions with low noise-sensitivity are structured in certain ways. (2) Mathematically showing that certain classes of functions have low noise sensitivity. Combined, these two research directions show that certain classes of functions have low noise sensitivity and therefore have useful structure. The fundamental importance of noise sensitivity, together with this wealth of structural results, motivates the algorithmic question of approximating NS_{delta}[f] given an oracle access to the function f. We show that the standard sampling approach is essentially optimal for general Boolean functions. Therefore, we focus on estimating the noise sensitivity of monotone functions, which form an important subclass of Boolean functions, since many functions of interest are either monotone or can be simply transformed into a monotone function (for example the class of unate functions consists of all the functions that can be made monotone by reorienting some of their coordinates [O'Donnell, 2014]). Specifically, we study the algorithmic problem of approximating NS_{delta}[f] for monotone f, given the promise that NS_{delta}[f] >= 1/n^{C} for constant C, and for delta in the range 1/n <= delta <= 1/2. For such f and delta, we give a randomized algorithm performing O((min(1,sqrt{n} delta log^{1.5} n))/(NS_{delta}[f]) poly (1/epsilon)) queries and approximating NS_{delta}[f] to within a multiplicative factor of (1 +/- epsilon). Given the same constraints on f and delta, we also prove a lower bound of Omega((min(1,sqrt{n} delta))/(NS_{delta}[f] * n^{xi})) on the query complexity of any algorithm that approximates NS_{delta}[f] to within any constant factor, where xi can be any positive constant. Thus, our algorithm’s query complexity is close to optimal in terms of its dependence on n. We introduce a novel descending-ascending view of noise sensitivity, and use it as a central tool for the analysis of our algorithm. To prove lower bounds on query complexity, we develop a technique that reduces computational questions about query complexity to combinatorial questions about the existence of "thin" functions with certain properties. The existence of such "thin" functions is proved using the probabilistic method. These techniques also yield new lower bounds on the query complexity of approximating other fundamental properties of Boolean functions: the total influence and the bias.
This thesis presents a theoretical analysis of round complexity in cryptographic sampling protocols. We study the following problem: how can n participants agree on a random sample from the distribution D without anybody knowing any secret information hidden in the chosen sample? How many rounds of interactions are needed in any such protocol? Which assumptions are required? These questions are particularly interesting in the context of multiparty computation (MPC) due to the extensive reliance (often unavoidable) on trusted setups such as common reference strings (CRSs). These are samples from known distributions made public before the beginning of the protocol. Security proofs often require CRSs to hide trapdoors. However, if these trapdoors get leaked, security is often fatally compromised. Since trusted setups are inherently single points of failure, it is desirable to generate CRSs in a distributed fashion using MPC protocols: as long as at least one of the participants remains honest, any trapdoor hidden in the CRS is guaranteed to remain secret. Previous research (Garg et al. TCC ’14) had shown that, in the setting of semi-honest security with dishonest majority, any functionality can be implemented in two rounds. In this thesis, we show that, using strong primitives such as indistinguishability obfuscation (iO), it is possible to build one-round sampling protocols. We call these constructions distributed samplers. We show that these protocols can be used to securely generate large amounts of correlated randomness with sublinear communication in a single round. We study different ways to upgrade our semi-honest construction to active security. First, we try to circumvent Cleve’s impossibility (STOC ’86) by allowing the adversary limited influence on the output of the protocol: we consider the functionality F_D^{Active} that proposes a polynomial number of different outputs to the adversary, letting it choose its favourite one (F_D^{Active} can still be used to generate CRSs). We show how to implement F_D^{Active} in one round by relying on a programmable random oracle. In subsequent work, we show that random oracles are necessary: any actively secure distributed samplers implementing F_D^{Active} needs to rely on a CRS that is non-reusable, as large as a sample from D and structured (unless D is an obliviously samplable distribution). This suggests that, without random oracles, simulation-based, actively secure distributed samplers provide no advantage over trusted dealers. We get around this impossibility by proposing new game-based definitions for actively secure distributed samplers. Hardness-preserving distributed samplers allow the removal of CRSs from MPC protocols preserving at the same time the hardness of search problems. Indistinguishability-preserving distributed samplers, on the other hand, substitute the trusted setup while preserving the functionality, however, the protocol needs to satisfy particular conditions. We show how to build distributed samplers with the defined properties by relying on extremely lossy functions, the subexponential security of iO and other primitives. Next, in the context of active security with dishonest majority, we study the feasibility of protocols producing unbiased samples with guaranteed output: to circumvent Cleve's impossibility, we assume the existence of an auxiliary functionality that, upon invocation, publishes a random , short k-bit string. We first study the question when D is the uniform distribution over {0, 1}^m where m>k. This problem is called coin tossing extension (CTE) (Bellare et al. PODC '96). We show the existence of O(1)-round CTE constructions producing an arbitrarily large quantity of unbiased randomness based on various assumptions (OWFs, DDH, QR and DCR, class groups). Our most important result is an LWE-based, one-round, UC-secure, n-party CTE protocol withstanding adaptive corruption. The protocol can be viewed as an explainable randomness extractor. By relying on distributed samplers and the auxiliary functionality, we build one-round unbiased sampling protocols for any distribution. Finally, we present a lower bound for statistically secure CTE with black-box simulation: an R-round protocol can generate at most k+R·O(log λ) bits of randomness.
Given a convex function f:Rd→R, the problem of sampling from a distribution ∝e−f(x) is called log-concave sampling. This task has wide applications in machine learning, physics, statistics, etc. In this work, we develop quantum algorithms for sampling log-concave distributions and for estimating their normalizing constants ∫Rde−f(x)dx. First, we use underdamped Langevin diffusion to develop quantum algorithms that match the query complexity (in terms of the condition number κ and dimension d) of analogous classical algorithms that use gradient (first-order) queries, even though the quantum algorithms use only evaluation (zeroth-order) queries. For estimating normalizing constants, these algorithms also achieve quadratic speedup in the multiplicative error ε. Second, we develop quantum Metropolis-adjusted Langevin algorithms with query complexity O(κ1/2d) and O(κ1/2d3/2/ε) for log-concave sampling and normalizing constant estimation, respectively, achieving polynomial speedups in κ,d,ε over the best known classical algorithms by exploiting quantum analogs of the Monte Carlo method and quantum walks. We also prove a 1/ε1−o(1) quantum lower bound for estimating normalizing constants, implying near-optimality of our quantum algorithms in ε.