Please use this identifier to cite or link to this item: https://doi.org/10.1109/CCC.2010.31
Title: The partition bound for classical communication complexity and query complexity
Authors: Jain, R. 
Klauck, H.
Keywords: Communication complexity
Linear programming
Lower bounds
Partition bound
Query complexity
Issue Date: 2010
Source: Jain, R., Klauck, H. (2010). The partition bound for classical communication complexity and query complexity. Proceedings of the Annual IEEE Conference on Computational Complexity : 247-258. ScholarBank@NUS Repository. https://doi.org/10.1109/CCC.2010.31
Abstract: We describe new lower bounds for randomized communication complexity and query complexity which we call the partition bounds. They are expressed as the optimum value of linear programs. For communication complexity we show that the partition bound is stronger than both the rectangle/corruption bound and the γ2/generalized discrepancy bounds. In the model of query complexity we show that the partition bound is stronger than the approximate polynomial degree and classical adversary bounds. We also exhibit an example where the partition bound is quadratically larger than the approximate polynomial degree and adversary bounds. © 2010 IEEE.
Source Title: Proceedings of the Annual IEEE Conference on Computational Complexity
URI: http://scholarbank.nus.edu.sg/handle/10635/40841
ISBN: 9780769540603
ISSN: 10930159
DOI: 10.1109/CCC.2010.31
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

41
checked on Dec 6, 2017

WEB OF SCIENCETM
Citations

17
checked on Nov 21, 2017

Page view(s)

42
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.