Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture

DOI10.1145/2591796.2591856MaRDI QIDQ5259555zbMATH OpenOpenAlexFDO

Authors Dmitry Gavinsky, Or Meir, O. Weinstein, A. Wigderson

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

zbMATH Keywords

information complexityformula complexity

Mathematics Subject Classification ID

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)

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

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

(11)

• Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation
• scientific article; zbMATH DE number 7250155 (Why is no real title available?)
• Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
• Prediction from partial information and hindsight, with application to circuit lower bounds
• Circuit depth reductions
• Improved composition theorems for functions and relations
• Communication complexity towards lower bounds on circuit depth
• Toward better depth lower bounds: two results on the multiplexor relation
• Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
• Toward better depth lower bounds: a KRW-like theorem for strong composition
• Lifting Theorems for Equality

Describes a project that uses

Uses Software

• SuLQ

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)