Breaking the Minsky-Papert barrier for constant-depth circuits
DOI10.1145/2591796.2591871zbMATH Open1315.68159OpenAlexW2025510995MaRDI QIDQ5259556FDOQ5259556
Authors: Alexander A. Sherstov 
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
Recommendations
- Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
- The power of asymmetry in constant-depth circuits
- New degree bounds for polynomial threshold functions
- New degree bounds for polynomial threshold functions
- Near-optimal lower bounds on the threshold degree and sign-rank of \(\mathrm{AC}^0\)
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
- 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, efficient algorithms and hardness results
- Title not available (Why is that?)
- Collusion-secure fingerprinting for digital data
- Advances in Cryptology – CRYPTO 2004
- Title not available (Why is that?)
- 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
- Efficient algorithms for privately releasing marginals via convex relaxations
Cited In (9)
- Approximate degree and the complexity of depth three circuits
- On the power of statistical zero knowledge
- The power of asymmetry in constant-depth circuits
- A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
- The large-error approximate degree of \(\mathrm{AC}^0\)
- Hardness amplification and the approximate degree of constant-depth circuits
- Dual polynomials for collision and element distinctness
- Breaking the Minsky--Papert Barrier for 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)
