Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture
DOI10.1145/2591796.2591856zbMATH Open1315.68138OpenAlexW2057918151MaRDI QIDQ5259555FDOQ5259555
A. Wigderson, Dmitry Gavinsky, O. Weinstein, Or Meir
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.2591856
Recommendations
- Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation
- Improved composition theorems for functions and relations
- Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
- Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
- Communication complexity towards lower bounds on circuit depth
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)
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
- 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
- Privately releasing conjunctions and the statistical query barrier
- Efficient algorithms for privately releasing marginals via convex relaxations
Cited In (7)
- Title not available (Why is that?)
- Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation
- Title not available (Why is that?)
- Prediction from partial information and hindsight, with application to circuit lower bounds
- Communication complexity towards lower bounds on circuit depth
- Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
- Lifting Theorems for Equality
Uses Software
This page was built for publication: Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5259555)
