scientific article; zbMATH DE number 7204258
From MaRDI portal
Publication:5111137
DOI10.4230/LIPIcs.CCC.2017.7zbMath1435.68089MaRDI QIDQ5111137
Shuichi Hirahara, Rahul Santhanam
Publication date: 26 May 2020
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
hardnessaverage-case complexitycircuit lower boundsminimum circuit size problemtime-bounded Kolmogorov complexity
Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Networks and circuits as models of computation; circuit complexity (68Q06)
Related Items (18)
Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ Cryptographic hardness under projections for time-bounded Kolmogorov complexity ⋮ Unnamed Item ⋮ Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity ⋮ On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets ⋮ Hardness of sparse sets and minimal circuit size problem ⋮ Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The non-hardness of approximating circuit size ⋮ Unnamed Item ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization ⋮ Randomness and Intractability in Kolmogorov Complexity ⋮ Hardness magnification near state-of-the-art lower bounds ⋮ Circuit lower bounds from NP-hardness of MCSP under turing reductions
This page was built for publication:
