Learning Complexity vs Communication Complexity

DOI10.1017/S0963548308009656zbMath1202.68314OpenAlexW1970169765MaRDI QIDQ3557511

Adi Shraibman, Nathan Linial

Publication date: 23 April 2010

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s0963548308009656

zbMATH Keywords

machine learning algorithmsmargin classifiersmargin complexityrigidity of margin complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05)

Related Items (20)

Grothendieck-Type Inequalities in Combinatorial Optimization ⋮ Approximate Degree in Classical and Quantum Computing ⋮ The landscape of communication complexity classes ⋮ Zero-information protocols and unambiguity in Arthur-Merlin communication ⋮ Around the log-rank conjecture ⋮ Unnamed Item ⋮ On the Power of Statistical Zero Knowledge ⋮ Sign rank versus Vapnik-Chervonenkis dimension ⋮ On a theorem of Razborov ⋮ Unbounded-Error Classical and Quantum Communication Complexity ⋮ Using elimination theory to construct rigid matrices ⋮ The hardest halfspace ⋮ The communication complexity of addition ⋮ Upper and Lower Bounds on the Power of Advice ⋮ Sign rank vs discrepancy ⋮ Lower bounds in communication complexity based on factorization norms ⋮ An Additive Combinatorics Approach Relating Rank to Communication Complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Upper bounds on communication in terms of approximate rank

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A remark on matrix rigidity
• Probabilistic communication complexity
• Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
• On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes
• Complexity measures of sign matrices
• Improved lower bounds on the rigidity of Hadamard matrices
• Some combinatorial-algebraic problems from complexity theory
• Extensions of Lipschitz mappings into a Hilbert space
• 10.1162/153244303321897681
• Embedding with a Lipschitz function
• Geometric discrepancy. An illustrated guide

This page was built for publication: Learning Complexity vs Communication Complexity