Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
From MaRDI portal
Publication:3380367
DOI10.53733/148OpenAlexW3199012062MaRDI QIDQ3380367
Publication date: 28 September 2021
Published in: New Zealand Journal of Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.53733/148
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
- The new complexity landscape around circuit minimization
- On the notion of infinite pseudorandom sequences
- Hardness of sparse sets and minimal circuit size problem
- Zero knowledge and circuit minimization
- The minimum oracle circuit size problem
- The tale of one-way functions
- The Complexity of Complexity
- Algorithmic Randomness and Complexity
- Minimum Circuit Size, Graph Isomorphism, and Related Problems
- Circuit minimization problem
- On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets
- Amplifying lower bounds by means of self-reducibility
- Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
- Randomness conservation inequalities; information and independence in mathematical theories
- Computational limitations on learning from examples
- The minimum consistent DFA problem cannot be approximated within any polynomial
- Complexity of automaton identification from given data
- Circuit Lower Bounds for MCSP from Local Pseudorandom Generators
- Randomness and Intractability in Kolmogorov Complexity
- Hardness magnification near state-of-the-art lower bounds
- Relations and equivalences between circuit lower bounds and karp-lipton theorems
- Circuit lower bounds from NP-hardness of MCSP under turing reductions
- Unexpected hardness results for Kolmogorov complexity under uniform reductions
- Sharp threshold results for computational complexity
- New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems
- Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
- On the NP-Completeness of the Minimum Circuit Size Problem.
- Learning algorithms from natural proofs
- Power from Random Strings
- Natural proofs
- An introduction to Kolmogorov complexity and its applications
- The non-hardness of approximating circuit size
- Hardness of KT characterizes parallel cryptography
This page was built for publication: Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
