scientific article; zbMATH DE number 7561748
From MaRDI portal
Publication:5092470
DOI10.4230/LIPIcs.CCC.2020.20MaRDI QIDQ5092470
Publication date: 21 July 2022
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items (3)
Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ Cryptographic hardness under projections for time-bounded Kolmogorov complexity ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Turing machines that take advice
- NP is as easy as detecting unique solutions
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Pseudorandom generators for space-bounded computation
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Hardness vs randomness
- Decoding of Reed Solomon codes beyond the error-correction bound
- Boosting and hard-core set construction
- The complexity of constructing pseudorandom generators from hard functions
- Some results on derandomization
- On lower bounds for read-\(k\)-times branching programs
- Pseudorandomness and average-case complexity via uniform reductions
- Pseudorandomness
- A Sample of Samplers: A Computational Perspective on Sampling
- Random-Self-Reducibility of Complete Sets
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Circuit minimization problem
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- On the Complexity of Learning Minimum Time-Bounded Turing Machines
- Amplifying lower bounds by means of self-reducibility
- Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
- Average Case Complete Problems
- Randomness conservation inequalities; information and independence in mathematical theories
- The complexity of promise problems with applications to public-key cryptography
- A Pseudorandom Generator from any One-way Function
- A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
- Hardness magnification near state-of-the-art lower bounds
- Unexpected hardness results for Kolmogorov complexity under uniform reductions
- 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 derandomizing algorithms that err extremely rarely
- On the NP-Completeness of the Minimum Circuit Size Problem.
- Learning algorithms from natural proofs
- Some Results on Average-Case Hardness Within the Polynomial Hierarchy
- Hardness Amplification Proofs Require Majority
- Using Nondeterminism to Amplify Hardness
- Power from Random Strings
- On Worst‐Case to Average‐Case Reductions for NP Problems
- An Unconditional Study of Computational Zero Knowledge
- Locally Decodable Codes
- Natural proofs
- Extracting all the randomness and reducing the error in Trevisan's extractors
- Pseudorandom generators without the XOR lemma
This page was built for publication:
