scientific article; zbMATH DE number 7204388

DOI10.4230/LIPICS.MFCS.2017.54zbMATH Open1441.68082MaRDI QIDQ5111269FDOQ5111269

Authors: Shuichi Hirahara, Eric Allender 

Publication date: 26 May 2020

Title of this publication is not available (Why is that?)

Recommendations

• New insights on the (non-)hardness of circuit minimization and related problems
• The non-hardness of approximating circuit size
• The non-hardness of approximating circuit size
• On the average-case complexity of MCSP and its variants
• On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity

zbMATH Keywords

computational complexityKolmogorov complexitycircuit size

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Networks and circuits as models of computation; circuit complexity (68Q06)

Cites Work

• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• On the Structure of Polynomial Time Reducibility
• On the Hardness of Graph Isomorphism
• An Unconditional Study of Computational Zero Knowledge
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Title not available (Why is that?)
• Title not available (Why is that?)
• Natural proofs
• Amplifying lower bounds by means of self-reducibility
• Circuit minimization problem
• Reductions in circuit complexity: An isomorphism theorem and a gap theorem
• The isomorphism conjecture for constant depth reductions
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• Power from Random Strings
• Title not available (Why is that?)
• Title not available (Why is that?)
• The minimum oracle circuit size problem
• Title not available (Why is that?)
• Minimum Circuit Size, Graph Isomorphism, and Related Problems
• Title not available (Why is that?)
• Discrete logarithm and minimum circuit size
• Zero Knowledge and Circuit Minimization
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (14)

• New Collapse Consequences of NP Having Small Circuits
• Minimum Circuit Size, Graph Isomorphism, and Related Problems
• Minimum Circuit Size, Graph Isomorphism, and Related Problems
• Hardness of sparse sets and minimal circuit size problem
• Circuit lower bounds from NP-hardness of MCSP under turing reductions
• Title not available (Why is that?)
• One-tape Turing machine and branching program lower bounds for MCSP
• Title not available (Why is that?)
• Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the NP-Completeness of the Minimum Circuit Size Problem.

This page was built for publication:

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