The Geometry of Differential Privacy: The Small Database and Approximate Cases
From MaRDI portal
Publication:2805515
DOI10.1137/130938943zbMath1339.68066arXiv1212.0297OpenAlexW2342483111WikidataQ115246987 ScholiaQ115246987MaRDI QIDQ2805515
L. Zhang, Kunal Talwar, Aleksandar Nikolov
Publication date: 12 May 2016
Published in: SIAM Journal on Computing, Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1212.0297
Database theory (68P15) Cryptography (94A60) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Authentication, digital signatures and secret sharing (94A62)
Related Items (only showing first 100 items - show all)
Differentially private range query on shortest paths ⋮ $(2+\varepsilon)$-Sat Is NP-hard ⋮ Privacy Aware Learning ⋮ 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 ⋮ Algorithmic Aspects of Combinatorial Discrepancy ⋮ Lower bounds on the error of query sets under the differentially-private matrix mechanism ⋮ An Improved Private Mechanism for Small Databases ⋮ 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 ⋮ Strong Hardness of Privacy from Weak Traitor Tracing ⋮ Fingerprinting Codes and the Price of Approximate Differential Privacy ⋮ Comment ⋮ Model averaging with privacy-preserving ⋮ Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design ⋮ Private Sampling: A Noiseless Approach for Generating Differentially Private Synthetic Data ⋮ TIGHTER BOUNDS FOR THE DISCREPANCY OF BOXES AND POLYTOPES ⋮ 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 ⋮ New algorithms and lower bounds for circuits with linear threshold gates ⋮ An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound ⋮ Deciding First-Order Properties of Nowhere Dense Graphs ⋮ The Matching Polytope has Exponential Extension Complexity ⋮ Economic efficiency requires interaction ⋮ On the power of multiple anonymous messages: frequency estimation and selection in the shuffle model of differential privacy ⋮ Bounded privacy-utility monotonicity indicating bounded tradeoff of differential privacy mechanisms ⋮ A simplified disproof of Beck’s three permutations conjecture and an application to root-mean-squared discrepancy ⋮ On a new method for controlling the entire spectrum in the problem of column subset selection ⋮ 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 ⋮ Analytical approach to parallel repetition ⋮ A characterization of strong approximation resistance ⋮ A strongly polynomial algorithm for generalized flow maximization ⋮ Approximate distance oracles with constant query time ⋮ Faster all-pairs shortest paths via circuit complexity ⋮ Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs ⋮ Zig-zag sort
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio
- Minimum-volume enclosing ellipsoids and core sets
- Discrepancy of set-systems and matrices
- Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
- The Brunn-Minkowski inequality in Gauss space
- Efficient algorithms for privately releasing marginals via convex relaxations
- On Khachiyan's algorithm for the computation of minimum-volume enclosing ellipsoids
- Nearly Optimal Private Convolution
- Privately Releasing Conjunctions and the Statistical Query Barrier
- On the geometry of differential privacy
- Interactive privacy via the median mechanism
- The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
- Lower Bounds in Differential Privacy
- Iterative Constructions and Private Data Release
- Private and Continual Release of Statistics
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- Approximation of the Sphere by Polytopes having Few Vertices
- Rounding of Polytopes in the Real Number Model of Computation
- The determinant bound for discrepancy is almost tight
- Universally utility-maximizing privacy mechanisms
- On the complexity of differentially private data release
- Impossibility of Differentially Private Universally Optimal Mechanisms
- Fingerprinting codes and the price of approximate differential privacy
- Minimax Rates of Estimation for High-Dimensional Linear Regression Over $\ell_q$-Balls
- Advances in Cryptology – CRYPTO 2004
- Approximating Hereditary Discrepancy via Small Width Ellipsoids
- $(2+\varepsilon)$-Sat Is NP-hard
- The complexity of satisfiability problems
- Unconditional differentially private mechanisms for linear queries
- Optimal private halfspace counting via discrepancy
- Answering n {2+o(1)} counting queries with differential privacy is hard
- The Power of Linear Reconstruction Attacks
- Theory of Cryptography
- Geometric discrepancy. An illustrated guide
- John's decompositions: Selecting a large part
This page was built for publication: The Geometry of Differential Privacy: The Small Database and Approximate Cases
