scientific article; zbMATH DE number 7204388
From MaRDI portal
Publication:5111269
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
Cites work
- Amplifying lower bounds by means of self-reducibility
- An Unconditional Study of Computational Zero Knowledge
- Circuit minimization problem
- Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness
- Discrete logarithm and minimum circuit size
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- scientific article; zbMATH DE number 6351503 (Why is no real title available?)
- scientific article; zbMATH DE number 1161568 (Why is no real title available?)
- scientific article; zbMATH DE number 1559537 (Why is no real title available?)
- scientific article; zbMATH DE number 7204388 (Why is no real title available?)
- Limits of minimum circuit size problem as oracle
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Minimum circuit size, graph isomorphism, and related problems
- Natural proofs
- On the (non) NP-hardness of computing circuit complexity
- On the average-case complexity of MCSP and its variants
- On the Hardness of Graph Isomorphism
- On the Structure of Polynomial Time Reducibility
- Power from Random Strings
- Reductions in circuit complexity: An isomorphism theorem and a gap theorem
- The isomorphism conjecture for constant depth reductions
- The minimum oracle circuit size problem
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
- Zero knowledge and circuit minimization
Cited in
(23)- Hardness of sparse sets and minimal circuit size problem
- Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
- Cryptographic hardness under projections for time-bounded Kolmogorov complexity
- Minimum circuit size, graph isomorphism, and related problems
- New Collapse Consequences of NP Having Small Circuits
- Minimum circuit size, graph isomorphism, and related problems
- Hardness magnification near state-of-the-art lower bounds
- \(\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
- On the average-case complexity of MCSP and its variants
- scientific article; zbMATH DE number 7204388 (Why is no real title available?)
- scientific article; zbMATH DE number 7250145 (Why is no real title available?)
- New insights on the (non-)hardness of circuit minimization and related problems
- On the NP-Completeness of the Minimum Circuit Size Problem.
- The non-hardness of approximating circuit size
- The non-hardness of approximating circuit size
- scientific article; zbMATH DE number 7758317 (Why is no real title available?)
- Cryptographic hardness under projections for time-bounded Kolmogorov complexity
- One-tape Turing machine and branching program lower bounds for MCSP
- One-tape Turing machine and branching program lower bounds for MCSP
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)
