A duality between one-way functions and average-case symmetry of information
From MaRDI portal
Publication:6499281
DOI10.1145/3564246.3585138MaRDI QIDQ6499281FDOQ6499281
Authors: Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor C. Oliveira 
Publication date: 8 May 2024
Cites Work
- Probabilistic encryption
- A Pseudorandom Generator from any One-way Function
- THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
- Bit commitment using pseudorandomness
- Foundations of Cryptography
- Kolmogorov Complexity and Algorithmic Randomness
- Pseudorandomness and average-case complexity via uniform reductions
- Title not available (Why is that?)
- Symmetry of information and one-way functions
- Resource bounded symmetry of information revisited
- Resource-bounded Kolmogorov complexity revisited
- On the Complexity of Learning Minimum Time-Bounded Turing Machines
- Power from Random Strings
- Pseudodeterministic algorithms and the structure of probabilistic time
- Language compression and pseudorandom generators
- A note on computational indistinguishability
- Extracting all the randomness and reducing the error in Trevisan's extractors
- Title not available (Why is that?)
- Randomness and intractability in Kolmogorov complexity
- An introduction to Kolmogorov complexity and its applications
- On symmetry of information and polynomial time invertibility
- Hardness magnification near state-of-the-art lower bounds
- On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \)
- Hardness of KT characterizes parallel cryptography
- Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
- Title not available (Why is that?)
- Average-case hardness of NP from exponential worst-case hardness assumptions
This page was built for publication: A duality between one-way functions and average-case symmetry of information
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499281)
