scientific article; zbMATH DE number 2081103
From MaRDI portal
Publication:4474216
zbMath1052.68051MaRDI QIDQ4474216
R. Mubarakzjanov, Satyanarayana V. Lokam, Niels Schmitt, Jürgen Forster, Matthias Krause, Hans Ulrich Simon
Publication date: 4 August 2004
Full work available at URL: http://link.springer.de/link/service/series/0558/bibs/2245/22450171.htm
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (20)
A linear lower bound on the unbounded error probabilistic communication complexity. ⋮ A Short List of Equalities Induces Large Sign-Rank ⋮ Unnamed Item ⋮ The unbounded-error communication complexity of symmetric functions ⋮ Sign rank versus Vapnik-Chervonenkis dimension ⋮ Cryptographic hardness under projections for time-bounded Kolmogorov complexity ⋮ Unbounded-Error Classical and Quantum Communication Complexity ⋮ Using elimination theory to construct rigid matrices ⋮ New algorithms and lower bounds for circuits with linear threshold gates ⋮ The NOF multiparty communication complexity of composed functions ⋮ Complexity measures of sign matrices ⋮ Size, Depth and Energy of Threshold Circuits Computing Parity Function. ⋮ Threshold circuit lower bounds on cryptographic functions ⋮ Polynomial threshold functions and Boolean threshold circuits ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization ⋮ Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression ⋮ 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
This page was built for publication:
