Does Looking Inside a Circuit Help

DOI10.4230/LIPIcs.MFCS.2017.1zbMath1440.68079OpenAlexW2774527366MaRDI QIDQ5111215

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

Publication date: 26 May 2020

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

zbMATH Keywords

circuit complexitySATRice's theoremdecision-tree complexityblack-box hypothesissensitivity of Boolean functions

Mathematics Subject Classification ID

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

Related Items (2)

On some FPT problems without polynomial Turing compressions ⋮ Does Looking Inside a Circuit Help

Cites Work

• Unnamed Item
• Unnamed Item
• Lower bounds and the hardness of counting properties
• NP is as easy as detecting unique solutions
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• Hardness vs randomness
• A second step towards complexity-theoretic analogs of Rice's Theorem
• Which problems have strongly exponential complexity?
• Complexity measures and decision tree complexity: a survey.
• The minimum oracle circuit size problem
• On the complexity of circuit satisfiability
• Size of Sets with Small Sensitivity: A Generalization of Simon’s Lemma
• Constant Depth Reducibility
• CREW PRAM<scp>s</scp> and Decision Trees
• Looking for an Analogue of Rice's Theorem in Circuit Complexity Theory
• Does Looking Inside a Circuit Help
• On the (im)possibility of obfuscating programs

This page was built for publication: Does Looking Inside a Circuit Help