The query complexity of witness finding

DOI10.1007/s00224-016-9708-yzbMath1379.68170OpenAlexW2523399274MaRDI QIDQ2411034

Akinori Kawachi, Osamu Watanabe, Benjamin Rossman

Publication date: 20 October 2017

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: http://t2r2.star.titech.ac.jp/cgi-bin/publicationinfo.cgi?q_publication_content_number=CTT100759220

zbMATH Keywords

query complexitysearch-to-decision reductionwitness finding problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cites Work

• Unnamed Item
• Is Valiant-Vazirani's isolation probability improvable?
• NP is as easy as detecting unique solutions
• Threshold functions
• On the theory of average case complexity
• Shadows and intersections in vector spaces

This page was built for publication: The query complexity of witness finding