scientific article; zbMATH DE number 5485440

zbMATH Open1232.68047MaRDI QIDQ3549600FDOQ3549600

Authors: Cynthia Dwork, Frank McSherry, Kunal Talwar 

Publication date: 5 January 2009

Title of this publication is not available (Why is that?)

zbMATH Keywords

error ratesprivacy protectionerror-correcting codesstatistical databasepolynomial-time decodable random linear codes

Mathematics Subject Classification ID

Linear programming (90C05) Database theory (68P15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Decoding (94B35) Error probability in coding theory (94B70)

Cited In (only showing first 100 items - show all)

• On the existence of extractable one-way functions
• Attacks on statistical databases: the highly noisy case
• Distributed approximation algorithms for weighted shortest paths
• Formulas vs. circuits for small distance connectivity
• Embedding and canonizing graphs of bounded genus in logspace
• The sample complexity of revenue maximization
• Smoothed analysis of tensor decompositions
• Differentially private nearest neighbor classification
• Privacy in implementation
• Query complexity of approximate nash equilibria
• Efficient density estimation via piecewise polynomial approximation
• Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture
• Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
• Hitting sets for multilinear read-once algebraic branching programs, in any order
• Polynomial bounds for the grid-minor theorem
• Approximate relational Hoare logic for continuous random samplings
• Confidentiality and differential privacy in the dissemination of frequency tables
• Fingerprinting codes and the price of approximate differential privacy
• Distribution-invariant differential privacy
• Approximate distance oracles with constant query time
• Formal verification of differential privacy for interactive systems (extended abstract)
• Breaking the quadratic barrier for 3-LCC's over the reals
• Communication lower bounds via critical block sensitivity
• Primal beats dual on online packing LPs in the random-order model
• The core of the participatory budgeting problem
• A survey on approximation mechanism design without money for facility games
• Efficient money burning in general domains
• Efficient deterministic approximate counting for low-degree polynomial threshold functions
• Lower bounds for depth 4 formulas computing iterated matrix multiplication
• Differentially private data release via statistical election to partition sequentially
• Processing text for privacy: an information flow perspective
• A characterization of strong approximation resistance
• Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions
• Entropy, optimization and counting
• A characterization of locally testable affine-invariant properties via decomposition theorems
• A super-polynomial lower bound for regular arithmetic formulas
• How to delegate computations
• Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas
• Economic efficiency requires interaction
• Comparative study of differentially private data synthesis methods
• Solving SDD linear systems in nearly \(m \log^{1/2} n\) time
• Privacy, patience, and protection
• Secure sampling with sublinear communication
• An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem
• Optimal error rates for interactive coding. I: Adaptivity and other settings
• A strongly polynomial algorithm for generalized flow maximization
• Analytical approach to parallel repetition
• Coin flipping of any constant bias implies one-way functions
• \(L_p\)-testing
• Satisfiability threshold for random regular NAE-SAT
• Distributed computability in Byzantine asynchronous systems
• Faster all-pairs shortest paths via circuit complexity
• Pufferfish
• How to use indistinguishability obfuscation
• Analyze Gauss: optimal bounds for privacy-preserving principal component analysis
• Concentrated differential privacy: simplifications, extensions, and lower bounds
• The asymptotic \(k\)-SAT threshold
• The complexity of differential privacy
• The cost of privacy: optimal rates of convergence for parameter estimation with differential privacy
• On the power of multiple anonymous messages: frequency estimation and selection in the shuffle model of differential privacy
• Constant factor approximation for balanced cut in the PIE model
• Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing
• Every list-decodable code for high noise has abundant near-optimal rate puncturings
• What can we learn privately?
• Secure random sampling in differential privacy
• Minimum bisection is fixed parameter tractable
• Pseudorandom generators with optimal seed length for non-Boolean poly-size circuits
• Bounds on the sample complexity for private learning and private data release
• Community detection thresholds and the weak Ramanujan property
• Optimal data-independent noise for differential privacy
• Preserving differential privacy in convolutional deep belief networks
• Linear time construction of compressed text indices in compact space
• Shortest paths on polyhedral surfaces and terrains
• The limits of depth reduction for arithmetic formulas
• An efficient parallel solver for SDD linear systems
• Approximation algorithms for bipartite matching with metric and geometric costs
• Circuits resilient to additive attacks with applications to secure computation
• Rounding sum-of-squares relaxations
• Computing with a full memory: catalytic space
• Non-malleable codes from additive combinatorics (extended abstract)
• Truthful mechanisms with implicit payment computation
• A quantum algorithm for computing the unit group of an arbitrary degree number field
• Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
• Multiway cut, pairwise realizable distributions, and descending thresholds
• Parallel algorithms for geometric graph problems
• Bandits with switching costs, \(T^{2/3}\) regret
• Optimal competitive auctions
• Discrimination- and privacy-aware patterns
• Black-box non-black-box zero knowledge
• Distributed Private Data Analysis: Simultaneously Solving How and What
• Probability comprehension of differential privacy for privacy protection algorithms: a new measure
• Sample complexity bounds on differentially private learning via communication complexity
• Sylvester-Gallai type theorems for approximate collinearity
• Title not available (Why is that?)
• Homological product codes
• Learning privately with labeled and unlabeled examples
• A differentially private hybrid approach to traffic monitoring
• Discrete optimization methods for group model selection in compressed sensing
• Simultaneous private learning of multiple concepts
• Gaussian differentially private robust mean estimation and inference

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3549600)