scientific article; zbMATH DE number 7204388
From MaRDI portal
Publication:5111269
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)
Recommendations
Cites work
- 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?)
- 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
- 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 Hardness of Graph Isomorphism
- On the Structure of Polynomial Time Reducibility
- On the average-case complexity of MCSP and its variants
- 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
(22)- New Collapse Consequences of NP Having Small Circuits
- Hardness of sparse sets and minimal circuit size problem
- Circuit lower bounds from NP-hardness of MCSP under turing reductions
- scientific article; zbMATH DE number 7561748 (Why is no real title available?)
- scientific article; zbMATH DE number 7758317 (Why is no real title available?)
- One-tape Turing machine and branching program lower bounds for MCSP
- Hardness magnification near state-of-the-art lower bounds
- Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
- On the average-case complexity of MCSP and its variants
- New insights on the (non-)hardness of circuit minimization and related problems
- scientific article; zbMATH DE number 7561750 (Why is no real title available?)
- The non-hardness of approximating circuit size
- The non-hardness of approximating circuit size
- scientific article; zbMATH DE number 7561559 (Why is no real title available?)
- Hardness magnification near state-of-the-art lower bounds
- Cryptographic hardness under projections for time-bounded Kolmogorov complexity
- scientific article; zbMATH DE number 7204388 (Why is no real title available?)
- scientific article; zbMATH DE number 7250145 (Why is no real title available?)
- Cryptographic hardness under projections for time-bounded Kolmogorov complexity
- On the NP-Completeness of the Minimum Circuit Size Problem.
- Minimum circuit size, graph isomorphism, and related problems
- Minimum circuit size, graph isomorphism, and related problems
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)
