scientific article; zbMATH DE number 7561523
From MaRDI portal
Publication:5091179
DOI10.4230/LIPIcs.ICALP.2019.30zbMath1495.68081MaRDI QIDQ5091179
Mark Bun, Justin Thaler, Nikhil S. Mande
Publication date: 21 July 2022
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Cites Work
- Unnamed Item
- Unnamed Item
- Probabilistic communication complexity
- Learning intersections and thresholds of halfspaces
- On the hardness of learning intersections of two halfspaces
- The landscape of communication complexity classes
- A linear lower bound on the unbounded error probabilistic communication complexity.
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- PP is closed under intersection
- The unbounded-error communication complexity of symmetric functions
- Cryptographic hardness for learning intersections of halfspaces
- The Sign-Rank of AC$^0$
- Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
- Efficient noise-tolerant learning from statistical queries
- The Pattern Matrix Method
- Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
- Improved Bounds on the Sign-Rank of AC^0
- The Intersection of Two Halfspaces Has High Threshold Degree
- Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
- New degree bounds for polynomial threshold functions
This page was built for publication:
