Fractional covers and communication complexity
- 2 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 262-274
- https://doi.org/10.1109/sct.1992.215401
Abstract
It is possible to view communication complexity as the solution of an integer programming problem. The authors relax this integer programming problem to a linear programming problem, and try to deduce from it information regarding the original communication complexity question. This approach works well for nondeterministic communication complexity. In this case the authors get a special case of Lovasz's fractional cover measure and use it to completely characterize the amortized nondeterministic communication complexity. In the case of deterministic complexity the situation is more complicated. The authors discuss two attempts, and obtain some results using each of them.Keywords
This publication has 13 references indexed in Scilit:
- Short monotone formulae for the majority functionPublished by Elsevier ,2004
- Super-logarithmic depth lower bounds via direct sum in communication complexityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Amortized communication complexityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A simple lower bound for monotone clique using a communication gameInformation Processing Letters, 1992
- Applications of matrix methods to the theory of lower bounds in computational complexityCombinatorica, 1990
- Monotone circuits for connectivity require super-logarithmic depthPublished by Association for Computing Machinery (ACM) ,1988
- The power of randomness for communication complexityPublished by Association for Computing Machinery (ACM) ,1987
- Some complexity questions related to distributive computing(Preliminary Report)Published by Association for Computing Machinery (ACM) ,1979
- On the ratio of optimal integral and fractional coversDiscrete Mathematics, 1975
- Method of determining lower bounds for the complexity of P-schemesMathematical Notes, 1971