Computational Complexity, volume 28, issue 1, pages 113-144

Query-to-Communication Lifting for PNP

Mika Göös 1
, 
Pritish Kamath 2
, 
Toniann Pitassi 3
, 
Thomas Watson 4
1
 
Institute for Advanced study, Princeton, USA | 
2
 
3
 
4
 
Publication type: Journal Article
Publication date: 2018-11-30
scimago Q2
SJR: 0.453
CiteScore: 1.5
Impact factor: 0.7
ISSN: 10163328, 14208954
General Mathematics
Computational Mathematics
Computational Theory and Mathematics
Theoretical Computer Science
Abstract
We prove that the PNP-type query complexity (alternatively, decision list width) of any Boolean function f is quadratically related to the PNP-type communication complexity of a lifted version of f. As an application, we show that a certain “product” lower bound method of Impagliazzo and Williams (CCC 2010) fails to capture PNP communication complexity up to polynomial factors, which answers a question of Papakonstantinou, Scheder, and Song (CCC 2014).
Found 
Found 0
By date By citations

Top-30

Journals

1
2
ACM Transactions on Computation Theory
ACM Transactions on Computation Theory, 2, 28.57%
SIAM Journal on Computing
SIAM Journal on Computing, 2, 28.57%
Computational Complexity
Computational Complexity, 1, 14.29%
1
2

Publishers

1
2
Association for Computing Machinery (ACM)
Association for Computing Machinery (ACM), 2, 28.57%
Society for Industrial and Applied Mathematics (SIAM)
Society for Industrial and Applied Mathematics (SIAM), 2, 28.57%
Springer Nature
Springer Nature, 1, 14.29%
Institute of Electrical and Electronics Engineers (IEEE)
Institute of Electrical and Electronics Engineers (IEEE), 1, 14.29%
1
2
  • We do not take into account publications without a DOI.
  • Statistics recalculated only for publications connected to researchers, organizations and labs registered on the platform.
  • Statistics recalculated weekly.

Are you a researcher?

Create a profile to get free access to personal recommendations for colleagues and new articles.
Share
Cite this
GOST | RIS | BibTex | MLA
Found error?