On rank vs. communication complexity
From MaRDI portal
Publication:1906852
DOI10.1007/BF01192527zbMath0845.68038OpenAlexW2175167577MaRDI QIDQ1906852
Publication date: 15 September 1996
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01192527
Combinatorics in computer science (68R05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)
Related Items
The corruption bound, log-rank, and communication complexity, Path embeddings in faulty 3-ary \(n\)-cubes, Algebraic techniques in communication complexity, Deterministic Communication vs. Partition Number, On public-coin zero-error randomized communication complexity, The augmentation property of binary matrices for the binary and Boolean rank, Ultrametric Algorithms and Automata, Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture, Around the log-rank conjecture, Bipartite perfect matching as a real polynomial, On bounds of \(A_\alpha\)-eigenvalue multiplicity and the rank of a complex unit gain graph, Approximate nonnegative rank is equivalent to the smooth rectangle bound, Linear algebraic methods in communication complexity, Panconnectivity and edge-pancyclicity of \(k\)-ary \(n\)-cubes with faulty elements, On order and rank of graphs, Extremal problems under dimension constraints., A counterexample to the Alon-Saks-Seymour conjecture and related problems, Unnamed Item, Some structural properties of low-rank matrices related to computational complexity, Edge-pancyclicity and path-embeddability of bijective connection graphs, Complexity measures of sign matrices, Communication complexity of some number theoretic functions, Multiparty Communication Complexity of Vector–Valued and Sum–Type Functions, Partition arguments in multiparty communication complexity, Traced communication complexity of cellular automata, Polynomial degree vs. quantum query complexity, Unnamed Item, On derandomized composition of Boolean functions, Superlinear Advantage for Exact Quantum Algorithms, On set intersection representations of graphs, Lower bounds in communication complexity based on factorization norms, An Additive Combinatorics Approach Relating Rank to Communication Complexity, Complexity measures and decision tree complexity: a survey., Communication complexity method for measuring nondeterminism in finite automata, Evaluation of exact quantum query complexities by semidefinite programming, A Composition Theorem for Randomized Query Complexity, Upper bounds on communication in terms of approximate rank
Uses Software
Cites Work
