Does looking inside a circuit help?

DOI10.4230/LIPICS.MFCS.2017.1zbMATH Open1440.68079OpenAlexW2774527366MaRDI QIDQ5111215FDOQ5111215

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

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

zbMATH Keywords

SATcircuit complexityRice'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)

Cites Work

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

Cited In (2)

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

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)