On derandomizing algorithms that err extremely rarely
From MaRDI portal
Recommendations
- Improved bounds for quantified derandomization of constant-depth circuits and polynomials
- Improved bounds for quantified derandomization of constant-depth circuits and polynomials
- Can every randomized algorithm be derandomized?
- Uniform derandomization from pathetic lower bounds
- Uniform Derandomization from Pathetic Lower Bounds
Cites work
- scientific article; zbMATH DE number 5485440 (Why is no real title available?)
- scientific article; zbMATH DE number 5485574 (Why is no real title available?)
- Advances in Cryptology – CRYPTO 2004
- Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
- Bounds on the sample complexity for private learning and private data release
- Characterizing the sample complexity of private learners
- Collusion-secure fingerprinting for digital data
- Differential privacy and the fat-shattering dimension of linear queries
- Efficient algorithms for privately releasing marginals via convex relaxations
- Faster algorithms for privately releasing marginals
- Faster private release of marginals on small databases
- Interactive privacy via the median mechanism
- Iterative Constructions and Private Data Release
- Lower bounds in differential privacy
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- On the complexity of differentially private data release, efficient algorithms and hardness results
- On the geometry of differential privacy
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
- Theory of Cryptography
Cited in
(22)- Satisfiability and derandomization for small polynomial threshold circuits
- Lower bounds on black-box reductions of hitting to density estimation
- On hitting-set generators for polynomials that vanish rarely
- Improved bounds for quantified derandomization of constant-depth circuits and polynomials
- Constructive separations and their consequences
- scientific article; zbMATH DE number 1962815 (Why is no real title available?)
- scientific article; zbMATH DE number 7561748 (Why is no real title available?)
- scientific article; zbMATH DE number 2019636 (Why is no real title available?)
- Uniform Derandomization from Pathetic Lower Bounds
- scientific article; zbMATH DE number 7528580 (Why is no real title available?)
- scientific article; zbMATH DE number 7650112 (Why is no real title available?)
- Quantified Derandomization: How to Find Water in the Ocean
- A new general derandomization method
- Quantified derandomization of linear threshold circuits
- scientific article; zbMATH DE number 2102761 (Why is no real title available?)
- When Arthur has neither random coins nor time to spare: superfast derandomization of proof systems
- Fine-grained derandomization: from problem-centric to resource-centric complexity
- Near-optimal pseudorandom generators for constant-depth read-once formulas
- Amplification and Derandomization without Slowdown
- Improved bounds for quantified derandomization of constant-depth circuits and polynomials
- Uniform derandomization from pathetic lower bounds
- Nearly optimal pseudorandomness from hardness
This page was built for publication: On derandomizing algorithms that err extremely rarely
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5259544)
