Learning complexity vs communication complexity
From MaRDI portal
Recommendations
Cites work
- 10.1162/153244303321897681
- A remark on matrix rigidity
- An introduction to support vector machines and other kernel-based learning methods.
- Complexity measures of sign matrices
- Embedding with a Lipschitz function
- Extensions of Lipschitz mappings into a Hilbert space
- Geometric discrepancy. An illustrated guide
- scientific article; zbMATH DE number 3944534 (Why is no real title available?)
- scientific article; zbMATH DE number 4032351 (Why is no real title available?)
- scientific article; zbMATH DE number 1528185 (Why is no real title available?)
- scientific article; zbMATH DE number 1391397 (Why is no real title available?)
- Improved lower bounds on the rigidity of Hadamard matrices
- On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes
- Probabilistic communication complexity
- Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
- Some combinatorial-algebraic problems from complexity theory
Cited in
(31)- The landscape of communication complexity classes
- A linear lower bound on the unbounded error probabilistic communication complexity.
- The hardest halfspace
- Upper bounds on communication in terms of approximate rank
- Towards a deeper geometric, analytic and algorithmic understanding of margins
- Upper and lower bounds on the power of advice
- Grothendieck-type inequalities in combinatorial optimization
- Distribution-dependent sample complexity of large margin learning
- Zero-information protocols and unambiguity in Arthur-Merlin communication
- On a theorem of Razborov
- Sign rank versus Vapnik-Chervonenkis dimension
- Computing and Combinatorics
- Using elimination theory to construct rigid matrices
- Approximate Degree in Classical and Quantum Computing
- Sign rank vs discrepancy
- On the power of statistical zero knowledge
- The large-error approximate degree of \(\mathrm{AC}^0\)
- The communication complexity of addition
- Unbounded-Error Classical and Quantum Communication Complexity
- An additive combinatorics approach relating rank to communication complexity
- A little advice can be very helpful
- The large-error approximate degree of \(\mathrm{AC}^0\)
- Lower bounds in communication complexity based on factorization norms
- Around the log-rank conjecture
- A Borsuk-Ulam lower bound for sign-rank and its applications
- Upper bounds on communication in terms of approximate rank
- A hierarchy of constant communication complexity
- Factorization norms and an inverse theorem for MaxCut
- Communication complexity and discrepancy of halfplanes
- Distributional PAC-learning from Nisan's natural proofs
- Matrix discrepancy and the log-rank conjecture
This page was built for publication: Learning complexity vs communication complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3557511)
