Sign-rank can increase under intersection

DOI10.4230/LIPICS.ICALP.2019.30MaRDI QIDQ5091179zbMATH OpenFDO

Authors Mark Bun, Nikhil S. Mande, Justin Thaler

Publication date 21 July 2022

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2019.30

zbMATH Keywords

communication complexitydimension complexitylearning theorysign rank

Mathematics Subject Classification ID

Communication complexity, information complexity (68Q11) Computational learning theory (68Q32)

Recommendations

• Sign-rank can increase under intersection
• The Sign-Rank of AC^0
• A short list of equalities induces large sign-rank
• Improved bounds on the sign-rank of \(\mathrm{AC}^0\)
• Communication complexity under product and nonproduct distributions

Cites work

• A linear lower bound on the unbounded error probabilistic communication complexity.
• Any AND-OR formula of size \(N\) can be evaluated in time \(N^{1/2+o(1)}\) on a quantum computer
• Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
• Cryptographic hardness for learning intersections of halfspaces
• Efficient noise-tolerant learning from statistical queries
• scientific article; zbMATH DE number 46318 (Why is no real title available?)
• Improved bounds on the sign-rank of \(\mathrm{AC}^0\)
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• Learning intersections and thresholds of halfspaces
• New degree bounds for polynomial threshold functions
• On the hardness of learning intersections of two halfspaces
• PP is closed under intersection
• Probabilistic communication complexity
• Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
• The intersection of two halfspaces has high threshold degree
• The landscape of communication complexity classes
• The pattern matrix method
• The Sign-Rank of AC^0
• The unbounded-error communication complexity of symmetric functions

Cited in

(1)

• Sign-rank can increase under intersection

This page was built for publication: Sign-rank can increase under intersection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091179)