Testing and reconstruction of Lipschitz functions with applications to data privacy

DOI10.1137/110840741MaRDI QIDQ2840991zbMATH OpenOpenAlexFDO

Authors Madhav Jha, Sofya Raskhodnikova

Publication date 24 July 2013

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/110840741

zbMATH Keywords

data privacyLipschitz constantproperty testingreconstruction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20) Approximation algorithms (68W25) Authentication, digital signatures and secret sharing (94A62)

Recommendations

• Testing Lipschitz functions on hypergrid domains
• Limitations of local filters of Lipschitz and monotone functions
• Limitations of local filters of Lipschitz and monotone functions
• Testing Lipschitz functions on hypergrid domains
• Testing the Lipschitz property over product distributions with applications to data privacy

Cited in

(22)

• Testing piecewise functions
• Bounded invariant verification for time-delayed nonlinear networked dynamical systems
• Can we locally compute sparse connected subgraphs?
• Local bounds for the optimal information ratio of secret sharing schemes
• Testing Lipschitz functions on hypergrid domains
• Testing Lipschitz functions on hypergrid domains
• Erasure-Resilient Property Testing
• Parameterized property testing of functions
• Testing the Lipschitz property over product distributions with applications to data privacy
• Testing local properties of arrays
• Optimal unateness testers for real-valued functions: adaptivity helps
• Local computation algorithms for graphs of non-constant degrees
• Limitations of local filters of Lipschitz and monotone functions
• Limitations of local filters of Lipschitz and monotone functions
• The power and limitations of uniform samples in testing properties of figures
• The complexity of verifying loop-free programs as differentially private
• The role of local algorithms in privacy (invited talk)
• Property testing with online adversaries
• Spanner approximations in practice
• Property testing with online adversaries
• Exact minimum weight spanners via column generation
• Locally computing edge orientations

This page was built for publication: Testing and reconstruction of Lipschitz functions with applications to data privacy

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