scientific article; zbMATH DE number 7650382
From MaRDI portal
Publication:5875732
Recommendations
- \(\mathrm{AC}^0[p]\) lower bounds against MCSP via the coin problem
- Circuit lower bounds from NP-hardness of MCSP under turing reductions
- On the average-case complexity of MCSP and its variants
- scientific article; zbMATH DE number 522838
- A satisfiability algorithm for \(\mathrm{AC}^0\)
- Conditional Hardness of Approximating Satisfiable Max 3CSP-q
- On parameterized complexity of the multi-MCS problem
- Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms.
Cited in
(16)- Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
- Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
- \(\mathrm{AC}^0[p]\) lower bounds against MCSP via the coin problem
- The non-hardness of approximating circuit size
- The power of natural properties as oracles
- NP-hardness of approximating meta-complexity: a cryptographic approach
- Constant depth formula and partial function versions of MCSP are hard
- Hardness along the boundary: towards one-way functions from the worst-case hardness of time-bounded Kolmogorov complexity
- Gap MCSP is not (Levin) NP-complete in obfustopia
- Consequences of randomized reductions from SAT to time-bounded Kolmogorov complexity
- NP-hardness of approximating meta-complexity: a cryptographic approach
- On one-way functions, the worst-case hardness of time-bounded Kolmogorov complexity, and computational depth
- Lower bounds for Levin-Kolmogorov complexity
- SAT reduces to the minimum circuit size problem with a random oracle
- Lower bounds on the overhead of indistinguishability obfuscation
- Kolmogorov complexity characterizes statistical zero knowledge
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 Q5875732)
