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

DOI10.1007/S00037-019-00177-4MaRDI QIDQ2311545zbMATH OpenOpenAlexFDO

Authors Or Meir, A. Wigderson

Publication date 10 July 2019

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-019-00177-4

zbMATH Keywords

certificate complexitycircuit complexitycircuit complexity lower boundsdecision tree complexityinformation theoryquery complexitysensitivity

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• Prediction from partial information and hindsight, an alternative proof
• AC0 unpredictability
• Top-down lower bounds for depth-three circuits
• An average-case depth hierarchy theorem for Boolean circuits
• Entropy of contact circuits and lower bounds on their complexity

Cites work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• A Parallel Repetition Theorem
• An information statistics approach to data stream and communication complexity
• Applications of matrix methods to the theory of lower bounds in computational complexity
• Communication complexity
• Communication complexity towards lower bounds on circuit depth
• Constant depth circuits, Fourier transform, and learnability
• Exponential separation of communication and external information
• Fractional Covers and Communication Complexity
• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• scientific article; zbMATH DE number 176870 (Why is no real title available?)
• scientific article; zbMATH DE number 176875 (Why is no real title available?)
• scientific article; zbMATH DE number 524117 (Why is no real title available?)
• scientific article; zbMATH DE number 1452705 (Why is no real title available?)
• Interactive channel capacity
• Lower bounds on communication complexity
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Monotone circuits for matching require linear depth
• Monotone separation of logarithmic space from logarithmic depth
• Near-optimal small-depth lower bounds for small distance connectivity
• On the distributional complexity of disjointness
• Parity, circuits, and the polynomial-time hierarchy
• Poly-logarithmic Frege depth lower bounds via an expander switching lemma
• Prediction from partial information and hindsight, an alternative proof
• Randomness is linear in space
• Rounds in Communication Complexity Revisited
• Super-logarithmic depth lower bounds via the direct sum in communication complexity
• The average sensitivity of bounded-depth circuits
• Top-down lower bounds for depth-three circuits
• Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture
• Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity

Cited in

(5)

• Prediction from partial information and hindsight, an alternative proof
• AC0 unpredictability
• Algorithmic Learning Theory
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Comparing computational entropies below majority (or: when is the dense model theorem false?)

This page was built for publication: Prediction from partial information and hindsight, with application to circuit lower bounds

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