Publication

Proofs, Circuits, and Communication

Mika Tapani Göös
2022
Reviews

Abstract

We survey lower-bound results in complexity theory that have been obtained via newfound interconnections between propositional proof complexity, boolean circuit complexity, and query/communication complexity. We advocate for the theory of total search problems (TFNP) as a unifying language for these connections and discuss how this perspective suggests a whole programme for further research.

Official source

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Proofs, Circuits, and Communication

Chat with Graph Search

Preliminary Sensitivity Analysis of Time-Dependent Code Outputs in Fuel Performance Models Using OFFBEAT for Future Calibration

Constructing multicomponent cluster expansions with machine-learning and chemical embedding

Quantifying the Unknown: Data-Driven Approaches and Applications in Energy Systems