On the average-case complexity of MCSP and its variants

DOI10.4230/LIPICS.CCC.2017.7MaRDI QIDQ5111137zbMATH OpenFDO

Authors Shuichi Hirahara, Rahul Santhanam

Publication date 26 May 2020

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2017.7

zbMATH Keywords

average-case complexitycircuit lower boundshardnessminimum circuit size problemtime-bounded Kolmogorov complexity

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 7204388
• 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 (non) \(\mathsf{NP}\)-hardness of computing circuit complexity

Cited in

(32)

• On parameterized complexity of the multi-MCS problem
• Hardness of sparse sets and minimal circuit size problem
• On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \)
• Cryptographic hardness under projections for time-bounded Kolmogorov complexity
• MCS Extraction with Sublinear Oracle Queries
• On the complexity of MMSNP
• Minimum circuit size, graph isomorphism, and related problems
• Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
• On nonadaptive reductions to the set of random strings and its dense subsets
• Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
• Minimum circuit size, graph isomorphism, and related problems
• Circuit lower bounds for MCSP from local pseudorandom generators
• Randomness and intractability in Kolmogorov complexity
• Circuit lower bounds for MCSP from local pseudorandom generators
• \(\mathrm{AC}^0[p]\) lower bounds against MCSP via the coin problem
• Hardness magnification near state-of-the-art lower bounds
• scientific article; zbMATH DE number 7561748 (Why is no real title available?)
• scientific article; zbMATH DE number 7561750 (Why is no real title available?)
• Circuit lower bounds from NP-hardness of MCSP under turing reductions
• scientific article; zbMATH DE number 7204388 (Why is no real title available?)
• New insights on the (non-)hardness of circuit minimization and related problems
• scientific article; zbMATH DE number 7650382 (Why is no real title available?)
• The non-hardness of approximating circuit size
• scientific article; zbMATH DE number 7758317 (Why is no real title available?)
• Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
• Cryptographic hardness under projections for time-bounded Kolmogorov complexity
• Capturing one-way functions via NP-hardness of meta-complexity
• NP-hardness of approximating meta-complexity: a cryptographic approach
• One-tape Turing machine and branching program lower bounds for MCSP
• Impagliazzo's worlds through the Lens of conditional Kolmogorov complexity
• NP-hardness of approximating meta-complexity: a cryptographic approach
• One-tape Turing machine and branching program lower bounds for MCSP

This page was built for publication: On the average-case complexity of MCSP and its variants

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