Formula lower bounds via the quantum method

DOI10.1145/3055399.3055472MaRDI QIDQ4978064zbMATH OpenOpenAlexWikidataFDO

Authors Avishay Tal

Publication date 17 August 2017

Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3055399.3055472

zbMATH Keywords

average-case complexitybipartite formula complexityformula complexityformula lower boundsgraph complexityinner productsize amplification

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The quantum adversary method and classical formula size power bounds
• Quantum formulas: A lower bound and simulation
• Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of Boolean variables
• The quantum query complexity of read-many formulas
• Average-case lower bounds for formula size

Cited in

(19)

• Closed-form formula on quantum factorization effectiveness
• Quantum formulas: A lower bound and simulation
• The quantum query complexity of read-many formulas
• Dequantizing read-once quantum formulas
• Depth-independent lower bounds on the communication complexity of read-once Boolean formulas
• Quantified Derandomization: How to Find Water in the Ocean
• Approximate Degree in Classical and Quantum Computing
• Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
• Cubic Formula Size Lower Bounds Based on Compositions with Majority
• Circuit lower bounds for MCSP from local pseudorandom generators
• Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
• A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
• Algorithmic Polynomials
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• One-Way Communication Complexity and the Nečiporuk Lower Bound on Formula Size
• Quantum lower bounds by quantum arguments
• Lower bounds for QCDCL via formula gauge
• Range avoidance for low-depth circuits and connections to pseudorandomness
• Bounded simultaneous messages

This page was built for publication: Formula lower bounds via the quantum method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4978064)