Prediction from partial information and hindsight, an alternative proof

DOI10.1016/J.IPL.2018.04.011zbMath1425.68130OpenAlexW2801462386WikidataQ129940261 ScholiaQ129940261MaRDI QIDQ1751431

Alexander V. Smal, Navid Talebanfard

Publication date: 25 May 2018

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2018.04.011

zbMATH Keywords

computational complexityinformation theorycircuit complexityquery complexitycertificate complexity

Mathematics Subject Classification ID

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) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (1)

Prediction from partial information and hindsight, with application to circuit lower bounds

Cites Work

• An improved exponential-time algorithm for k -SAT
• Unnamed Item

This page was built for publication: Prediction from partial information and hindsight, an alternative proof