Please use this identifier to cite or link to this item:
|Title:||The partition bound for classical communication complexity and query complexity||Authors:||Jain, R.
|Issue Date:||2010||Citation:||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.
checked on May 17, 2019
WEB OF SCIENCETM
checked on May 8, 2019
checked on May 14, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.