Classical lower bounds from quantum upper bounds

Ben-David, S; Bouland, A; Garg, A; Kothari, R

Ben-David, S (reprint author), Univ Waterloo, Waterloo, ON, Canada.

2018 IEEE 59TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2018; (): 339

Abstract

We prove lower bounds on complexity measures, such as the approximate degree of a Boolean function and the approximate rank of a Boolean matrix, using......

Full Text Link


Links

期刊讨论 | 中国SCI论文 | 期刊主页 | 投稿经验 | 杂志官网 | 投稿链接 | 作者需知 | PMC链接 | Pubmed全文检索