More Like this

1. Deciding accuracy of differential privacy schemes

   https://doi.org/10.1145/3434289  

   Barthe, Gilles; Chadha, Rohit; Krogmeier, Paul; Sistla, A_Prasad; Viswanathan, Mahesh (January 2021, Proceedings of the ACM on Programming Languages)

   Differential privacy is a mathematical framework for developing statistical computations with provable guarantees of privacy and accuracy. In contrast to the privacy component of differential privacy, which has a clear mathematical and intuitive meaning, the accuracy component of differential privacy does not have a generally accepted definition; accuracy claims of differential privacy algorithms vary from algorithm to algorithm and are not instantiations of a general definition. We identify program discontinuity as a common theme in existingad hocdefinitions and introduce an alternative notion of accuracy parametrized by, what we call, — the of an inputxw.r.t.  a deterministic computationfand a distanced, is the minimal distanced(x,y) over allysuch thatf(y)≠f(x). We show that our notion of accuracy subsumes the definition used in theoretical computer science, and captures known accuracy claims for differential privacy algorithms. In fact, our general notion of accuracy helps us prove better claims in some cases. Next, we study the decidability of accuracy. We first show that accuracy is in general undecidable. Then, we define a non-trivial class of probabilistic computations for which accuracy is decidable (unconditionally, or assuming Schanuel’s conjecture). We implement our decision procedure and experimentally evaluate the effectiveness of our approach for generating proofs or counterexamples of accuracy for common algorithms from the literature. 

   more » « less
2. AND testing and robust judgement aggregation

   https://doi.org/10.1145/3357713.3384254  

   Filmus, Y; Lifshitz, N; Minzer, D; Mossel, E. (June 2020, STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing)

   A function f∶{0,1}n→ {0,1} is called an approximate AND-homomorphism if choosing x,y∈n uniformly at random, we have that f(x∧ y) = f(x)∧ f(y) with probability at least 1−ε, where x∧ y = (x1∧ y1,…,xn∧ yn). We prove that if f∶ {0,1}n → {0,1} is an approximate AND-homomorphism, then f is δ-close to either a constant function or an AND function, where δ(ε) → 0 as ε→ 0. This improves on a result of Nehama, who proved a similar statement in which δ depends on n. Our theorem implies a strong result on judgement aggregation in computational social choice. In the language of social choice, our result shows that if f is ε-close to satisfying judgement aggregation, then it is δ(ε)-close to an oligarchy (the name for the AND function in social choice theory). This improves on Nehama’s result, in which δ decays polynomially with n. Our result follows from a more general one, in which we characterize approximate solutions to the eigenvalue equation f = λ g, where is the downwards noise operator f(x) = y[f(x ∧ y)], f is [0,1]-valued, and g is {0,1}-valued. We identify all exact solutions to this equation, and show that any approximate solution in which f and λ g are close is close to an exact solution. 

   more » « less
3. Algorithmic Aspects of Immersibility and Embeddability

   https://doi.org/10.1093/imrn/rnae170  

   Manin, Fedor; Weinberger, Shmuel (August 2024, International Mathematics Research Notices)

   Abstract We analyze an algorithmic question about immersion theory: for which $$m$$, $$n$$, and $$CAT=\textbf{Diff}$$ or $$\textbf{PL}$$ is the question of whether an $$m$$-dimensional $CAT$-manifold is immersible in $$\mathbb{R}^{n}$$ decidable? We show that PL immersibility is decidable in all cases except for codimension 2, whereas smooth immersibility is decidable in all odd codimensions and undecidable in many even codimensions. As a corollary, we show that the smooth embeddability of an $$m$$-manifold with boundary in $$\mathbb{R}^{n}$$ is undecidable when $n-m$ is even and $$11m \geq 10n+1$$. 

   more » « less
4. Nonlinear dimension reduction via outer Bi-Lipschitz extensions

   https://doi.org/10.1145/3188745.3188828  

   Mahabadi, Sepideh; Makarychev, Konstantin; Makarychev, Yury; Razenshteyn, Ilya (June 2018, Nonlinear dimension reduction via outer Bi-Lipschitz extensions)

   We introduce and study the notion of *an outer bi-Lipschitz extension* of a map between Euclidean spaces. The notion is a natural analogue of the notion of *a Lipschitz extension* of a Lipschitz map. We show that for every map f there exists an outer bi-Lipschitz extension f′ whose distortion is greater than that of f by at most a constant factor. This result can be seen as a counterpart of the classic Kirszbraun theorem for outer bi-Lipschitz extensions. We also study outer bi-Lipschitz extensions of near-isometric maps and show upper and lower bounds for them. Then, we present applications of our results to prioritized and terminal dimension reduction problems, described next. We prove a *prioritized* variant of the Johnson–Lindenstrauss lemma: given a set of points X⊂ ℝd of size N and a permutation (”priority ranking”) of X, there exists an embedding f of X into ℝO(logN) with distortion O(loglogN) such that the point of rank j has only O(log3 + ε j) non-zero coordinates – more specifically, all but the first O(log3+ε j) coordinates are equal to 0; the distortion of f restricted to the first j points (according to the ranking) is at most O(loglogj). The result makes a progress towards answering an open question by Elkin, Filtser, and Neiman about prioritized dimension reductions. We prove that given a set X of N points in ℜd, there exists a *terminal* dimension reduction embedding of ℝd into ℝd′, where d′ = O(logN/ε4), which preserves distances ||x−y|| between points x∈ X and y ∈ ℝd, up to a multiplicative factor of 1 ± ε. This improves a recent result by Elkin, Filtser, and Neiman. The dimension reductions that we obtain are nonlinear, and this nonlinearity is necessary. 

   more » « less
5. Stability of Loday constructions

   https://doi.org/10.4310/HHA.2022.v24.n1.a13  

   Lindenstrauss, Ayelet; Richter, Birgit (January 2022, Homology homotopy and applications)

   Greenlees, John (Ed.)

   We study the question for which commutative ring spectra A the tensor of a simplicial set X with A, X ⊗ A, is a stable invariant in the sense that it depends only on the homotopy type of ΣX. We prove several structural properties about different notions of stability, corresponding to different levels of invariance required of X ⊗ A. We establish stability in important cases, such as complex and real periodic topological K-theory, KU and KO. 

   more » « less