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

DOI10.1007/S00037-019-00177-4zbMATH Open1425.68128OpenAlexW2929835774MaRDI QIDQ2311545FDOQ2311545

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

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

zbMATH Keywords

sensitivityinformation theoryquery complexitycircuit complexitydecision tree complexitycertificate complexitycircuit complexity lower bounds

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 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)

Cites Work

• Title not available (Why is that?)
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Applications of matrix methods to the theory of lower bounds in computational complexity
• Constant depth circuits, Fourier transform, and learnability
• Parity, circuits, and the polynomial-time hierarchy
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits
• The average sensitivity of bounded-depth circuits
• Top-down lower bounds for depth-three circuits
• Rounds in Communication Complexity Revisited
• An information statistics approach to data stream and communication complexity
• Fractional Covers and Communication Complexity
• Randomness is linear in space
• A Parallel Repetition Theorem
• Title not available (Why is that?)
• Communication complexity
• Lower bounds on communication complexity
• On the distributional complexity of disjointness
• Title not available (Why is that?)
• Monotone circuits for matching require linear depth
• Super-logarithmic depth lower bounds via the direct sum in communication complexity
• Communication complexity towards lower bounds on circuit depth
• Interactive channel capacity
• Prediction from partial information and hindsight, an alternative proof
• Title not available (Why is that?)
• Monotone separation of logarithmic space from logarithmic depth
• 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
• Exponential separation of communication and external information
• Poly-logarithmic Frege depth lower bounds via an expander switching lemma
• Near-optimal small-depth lower bounds for small distance connectivity
• Title not available (Why is that?)

Cited In (4)

• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Algorithmic Learning Theory
• AC0 unpredictability
• Prediction from partial information and hindsight, an alternative proof

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)