Log-rank conjecture
id:
log-rank-conjecture-321-18605731
title:
Log-rank conjecture
text:
In theoretical computer science, the log-rank conjecture states that the deterministic communication complexity of a two-party Boolean function is polynomially related to the logarithm of the rank of its input matrix. Let D denote the deterministic communication complexity of a function, and let rank denote the rank of its input matrix M f . Since every protocol using up to c bits partitions M f into at most 2 c monochromatic rectangles, and each of these has rank at most 1, The log-rank conje
brand slug:
wiki
category slug:
encyclopedia
description:
Unsolved problem in theoretical computer science
original url:
https://en.wikipedia.org/wiki/Log-rank_conjecture
date created:
date modified:
2023-12-17T10:29:33Z
main entity:
{"identifier":"Q65051369","url":"https://www.wikidata.org/entity/Q65051369"}
image:
fields total:
13
integrity:
14