Relations between communication complexity, linear arrangements, and computational complexity

DOI10.1007/3-540-45294-X_15MaRDI QIDQ4474216zbMATH OpenFDO

Authors Jürgen Forster, Matthias Krause, Satyanarayana V. Lokam, Niels Schmitt, Hans Ulrich Simon, R. Mubarakzianow

Publication date 4 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2245/22450171.htm

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Geometric arguments yield better bounds for threshold circuits and distributed computing
• Communication complexity and parallel computing
• Lower bounds on threshold and related circuits via communication complexity
• Probabilistic communication complexity
• A linear lower bound on the unbounded error probabilistic communication complexity.

Cited in

(25)

• Geometric arguments yield better bounds for threshold circuits and distributed computing
• A linear lower bound on the unbounded error probabilistic communication complexity.
• Upper bounds on communication in terms of approximate rank
• Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
• The unbounded-error communication complexity of symmetric functions
• Threshold circuit lower bounds on cryptographic functions
• Polynomial threshold functions and Boolean threshold circuits
• Cryptographic hardness under projections for time-bounded Kolmogorov complexity
• Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
• Learning complexity vs communication complexity
• scientific article; zbMATH DE number 5651473 (Why is no real title available?)
• scientific article; zbMATH DE number 524134 (Why is no real title available?)
• Sign rank versus Vapnik-Chervonenkis dimension
• Using elimination theory to construct rigid matrices
• Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0
• The NOF multiparty communication complexity of composed functions
• A short list of equalities induces large sign-rank
• Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
• Unbounded-Error Classical and Quantum Communication Complexity
• The large-error approximate degree of \(\mathrm{AC}^0\)
• Size, Depth and Energy of Threshold Circuits Computing Parity Function.
• Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees
• Upper bounds on communication in terms of approximate rank
• On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes
• Complexity measures of sign matrices

This page was built for publication: Relations between communication complexity, linear arrangements, and computational complexity

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