Breaking the minsky-papert barrier for constant-depth circuits
DOI10.1145/2591796.2591871zbMATH Open1315.68159OpenAlexW2025510995MaRDI QIDQ5259556FDOQ5259556
Publication date: 26 June 2015
Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2591796.2591871
polynomial approximationcommunication complexitycomputational learning theorypolynomial threshold functionspolynomial representations of Boolean functions
Analysis of algorithms and problem complexity (68Q25) Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Theory of Cryptography
- The geometry of differential privacy: the small database and approximate cases
- 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
- Differential Privacy and the Fat-Shattering Dimension of Linear Queries
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- On the complexity of differentially private data release
- Collusion-secure fingerprinting for digital data
- Advances in Cryptology – CRYPTO 2004
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- Bounds on the Sample Complexity for Private Learning and Private Data Release
- Answering n {2+o(1)} counting queries with differential privacy is hard
- Characterizing the sample complexity of private learners
- Faster Algorithms for Privately Releasing Marginals
- Faster private release of marginals on small databases
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- Privately releasing conjunctions and the statistical query barrier
- Efficient algorithms for privately releasing marginals via convex relaxations
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (9)
- A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$
- Title not available (Why is that?)
- Dual polynomials for collision and element distinctness
- Title not available (Why is that?)
- Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
- The Power of Asymmetry in Constant-Depth Circuits
- On the Power of Statistical Zero Knowledge
- Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
- Parity, circuits, and the polynomial-time hierarchy
Uses Software
This page was built for publication: Breaking the minsky-papert barrier for constant-depth circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5259556)
