On the geometry of differential privacy
From MaRDI portal
Publication:2875197
DOI10.1145/1806689.1806786zbMath1293.68098arXiv0907.3754OpenAlexW2141902405MaRDI QIDQ2875197
Publication date: 13 August 2014
Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0907.3754
Related Items (only showing first 100 items - show all)
PAC privacy: automatic privacy measurement and control of data processing ⋮ The right complexity measure in locally private estimation: it is not the Fisher information ⋮ Canonical noise distributions and private hypothesis tests ⋮ Differentially private range query on shortest paths ⋮ Privacy Aware Learning ⋮ Every list-decodable code for high noise has abundant near-optimal rate puncturings ⋮ Non-malleable codes from additive combinatorics ⋮ Breaking the quadratic barrier for 3-LCC's over the reals ⋮ Optimal error rates for interactive coding I ⋮ The asymptotic k-SAT threshold ⋮ Satisfiability threshold for random regular NAE-SAT ⋮ Efficient deterministic approximate counting for low-degree polynomial threshold functions ⋮ Communication lower bounds via critical block sensitivity ⋮ Computing with a full memory ⋮ Hitting sets for multilinear read-once algebraic branching programs, in any order ⋮ Lower bounds on the error of query sets under the differentially-private matrix mechanism ⋮ Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region ⋮ Communication is Bounded by Root of Rank ⋮ Are Lock-Free Concurrent Algorithms Practically Wait-Free? ⋮ Robust Protocols for Securely Expanding Randomness and Distributing Keys Using Untrusted Quantum Devices ⋮ The Power of Localization for Efficiently Learning Linear Separators with Noise ⋮ Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds ⋮ Fingerprinting Codes and the Price of Approximate Differential Privacy ⋮ Unnamed Item ⋮ Differentially private response mechanisms on categorical data ⋮ Rejoinder ⋮ Comment ⋮ Comment ⋮ Model averaging with privacy-preserving ⋮ Extreme points of the local differential privacy polytope ⋮ A lower bound on the release of differentially private integer partitions ⋮ Private Sampling: A Noiseless Approach for Generating Differentially Private Synthetic Data ⋮ Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes ⋮ An Almost-Optimally Fair Three-Party Coin-Flipping Protocol ⋮ Optimal CUR Matrix Decompositions ⋮ EXPONENTIAL IMPROVEMENT IN PRECISION FOR SIMULATING SPARSE HAMILTONIANS ⋮ The average sensitivity of an intersection of half spaces ⋮ Comparative study of differentially private data synthesis methods ⋮ Differential Privacy on Finite Computers ⋮ New algorithms and lower bounds for circuits with linear threshold gates ⋮ Deciding First-Order Properties of Nowhere Dense Graphs ⋮ The Matching Polytope has Exponential Extension Complexity ⋮ New collaborative filtering algorithms based on SVD++ and differential privacy ⋮ Economic efficiency requires interaction ⋮ The Geometry of Differential Privacy: The Small Database and Approximate Cases ⋮ Structure and Sensitivity in Differential Privacy: Comparing K-Norm Mechanisms ⋮ Fingerprinting codes and the price of approximate differential privacy ⋮ Analyze gauss ⋮ Private matchings and allocations ⋮ Rounding sum-of-squares relaxations ⋮ Constant factor approximation for balanced cut in the PIE model ⋮ Entropy, optimization and counting ⋮ Polynomial bounds for the grid-minor theorem ⋮ An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem ⋮ Cops, robbers, and threatening skeletons ⋮ Pseudorandom generators with optimal seed length for non-boolean poly-size circuits ⋮ On derandomizing algorithms that err extremely rarely ⋮ Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas ⋮ Lower bounds for depth 4 formulas computing iterated matrix multiplication ⋮ The limits of depth reduction for arithmetic formulas ⋮ A super-polynomial lower bound for regular arithmetic formulas ⋮ A characterization of locally testable affine-invariant properties via decomposition theorems ⋮ L p -testing ⋮ Turnstile streaming algorithms might as well be linear sketches ⋮ Linear time construction of compressed text indices in compact space ⋮ Formulas vs. circuits for small distance connectivity ⋮ Toward better formula lower bounds ⋮ Breaking the minsky-papert barrier for constant-depth circuits ⋮ The sample complexity of revenue maximization ⋮ Optimal competitive auctions ⋮ Homological product codes ⋮ A quantum algorithm for computing the unit group of an arbitrary degree number field ⋮ Primal beats dual on online packing LPs in the random-order model ⋮ Competitive algorithms from competitive equilibria ⋮ Minimum bisection is fixed parameter tractable ⋮ An efficient parallel solver for SDD linear systems ⋮ Solving SDD linear systems in nearly m log 1/2 n time ⋮ From hierarchical partitions to hierarchical covers ⋮ Shortest paths on polyhedral surfaces and terrains ⋮ Embedding and canonizing graphs of bounded genus in logspace ⋮ Testing surface area with arbitrary accuracy ⋮ Coin flipping of any constant bias implies one-way functions ⋮ Infinite randomness expansion with a constant number of devices ⋮ From average case complexity to improper learning complexity ⋮ Bandits with switching costs ⋮ Online local learning via semidefinite programming ⋮ How to use indistinguishability obfuscation ⋮ How to delegate computations ⋮ Circuits resilient to additive attacks with applications to secure computation ⋮ On the existence of extractable one-way functions ⋮ Black-box non-black-box zero knowledge ⋮ Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions ⋮ Query complexity of approximate nash equilibria ⋮ Constant rank bimatrix games are PPAD-hard ⋮ Approximation algorithms for bipartite matching with metric and geometric costs ⋮ Distributed approximation algorithms for weighted shortest paths ⋮ Parallel algorithms for geometric graph problems ⋮ Fourier PCA and robust tensor decomposition ⋮ Smoothed analysis of tensor decompositions ⋮ Efficient density estimation via piecewise polynomial approximation
This page was built for publication: On the geometry of differential privacy
