On black-box meta complexity and function inversion

DOI10.4230/LIPICS.APPROX/RANDOM.2024.66MaRDI QIDQ6920770zbMATH OpenFDO

Authors Noam Mazor, Rafael Pass

Publication date 6 October 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.APPROX/RANDOM.2024.66

zbMATH Keywords

function inversionKolmogorov complexitymeta complexity

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Cites work

• A formal theory of inductive inference. Part I
• A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
• Circuit minimization problem
• Cryptography from sublinear-time average-case hardness of time-bounded Kolmogorov complexity
• Hardness magnification for all sparse NP languages
• Hardness magnification for natural problems
• Hardness magnification near state-of-the-art lower bounds
• Hardness of KT characterizes parallel cryptography
• On one-way functions and Kolmogorov complexity
• On the notion of infinite pseudorandom sequences
• On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers
• Reviewing bounds on the circuit size of the hardest functions
• Rigorous Time/Space Trade-offs for Inverting Functions
• The non-uniform perebor conjecture for time-bounded Kolmogorov complexity is false
• Three approaches to the quantitative definition of information^*

This page was built for publication: On black-box meta complexity and function inversion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6920770)