Does looking inside a circuit help?

DOI10.4230/LIPICS.MFCS.2017.1MaRDI QIDQ5111215zbMATH OpenOpenAlexFDO

Authors Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani

Publication date 26 May 2020

Full work available at URL https://doi.org/10.4230/LIPIcs.MFCS.2017.1

zbMATH Keywords

black-box hypothesiscircuit complexitydecision-tree complexityRice's theoremSATsensitivity of Boolean functions

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Computational aspects of satisfiability (68R07) Switching theory, applications of Boolean algebras to circuits and networks (94C11)

Recommendations

• Circuit minimization problem
• The circuit-input game, natural proofs, and testing circuits with data
• Some new consequences of the hypothesis that P has fixed polynomial-size circuits
• Almost-natural proofs
• On the complexity of circuit satisfiability

Cites work

• BPP has subexponential time simulations unless EXPTIME has publishable proofs
• A second step towards complexity-theoretic analogs of Rice's Theorem
• Complexity measures and decision tree complexity: a survey.
• Constant Depth Reducibility
• CREW PRAM<scp>s</scp> and Decision Trees
• Does looking inside a circuit help?
• Hardness vs randomness
• scientific article; zbMATH DE number 3829252 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• Looking for an Analogue of Rice's Theorem in Circuit Complexity Theory
• Lower bounds and the hardness of counting properties
• NP is as easy as detecting unique solutions
• On the (im)possibility of obfuscating programs
• On the complexity of circuit satisfiability
• Size of sets with small sensitivity: a generalization of Simon's lemma
• The minimum oracle circuit size problem
• Which problems have strongly exponential complexity?

Cited in

(3)

• On some FPT problems without polynomial Turing compressions
• Does looking inside a circuit help?
• A framework of quantum strong exponential-time hypotheses

This page was built for publication: Does looking inside a circuit help?

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