PCPs and the hardness of generating synthetic data

DOI10.1007/S00145-020-09363-YMaRDI QIDQ2210447zbMATH OpenOpenAlexFDO

Authors Jonathan Ullman, Salil Vadhan

Publication date 6 November 2020

Published in Journal of Cryptology (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00145-020-09363-y

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Cryptography (94A60)

Recommendations

• Pcps and the hardness of generating private synthetic data
• On the complexity of differentially private data release, efficient algorithms and hardness results
• A learning theory approach to noninteractive database privacy
• Faster private release of marginals on small databases
• Hardness of non-interactive differential privacy from one-way functions

Cites work

• A dichotomy theorem for maximum generalized satisfiability problems.
• A theory of the learnable
• Advances in Cryptology – CRYPTO 2004
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• Asymptotically Efficient Lattice-Based Digital Signatures
• Computational limitations on learning from examples
• Computationally Sound Proofs
• Cryptographic limitations on learning Boolean formulae and finite automata
• Faster algorithms for privately releasing marginals
• Faster private release of marginals on small databases
• Foundations of Cryptography
• Hardness of approximate two-level logic minimization and PAC learning with membership queries
• scientific article; zbMATH DE number 1857639 (Why is no real title available?)
• scientific article; zbMATH DE number 5485574 (Why is no real title available?)
• Interactive privacy via the median mechanism
• Linear-time encodable and decodable error-correcting codes
• On the complexity of decoding Reed-Solomon codes (Corresp.)
• Optimization, approximation, and complexity classes
• Private data release via learning thresholds
• Releasing multiply-imputed synthetic data generated in two stages to protect confidentiality
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Some optimal inapproximability results
• The algorithmic foundations of differential privacy
• The approximability of constraint satisfaction problems
• The complexity of properly learning simple concept classes
• Theory of Cryptography
• Universal Arguments and their Applications
• Using convex relaxations for efficiently and privately releasing marginals (extended abstract)

Cited in

(2)

• Pcps and the hardness of generating private synthetic data
• One step to efficient synthetic data

Describes a project that uses

Uses Software

• SuLQ

This page was built for publication: PCPs and the hardness of generating synthetic data

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