scientific article; zbMATH DE number 7758312
From MaRDI portal
Publication:6084353
DOI10.4230/lipics.approx/random.2020.10MaRDI QIDQ6084353
Publication date: 31 October 2023
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
- Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Boosting and hard-core set construction
- Pseudorandomness and average-case complexity via uniform reductions
- If NP languages are hard on the worst-case, then it is easy to find their hard instances
- On basing one-way functions on NP-hardness
- On Yao’s XOR-Lemma
- Random-Self-Reducibility of Complete Sets
- The Complexity of Local List Decoding
- Limitations of Hardness vs. Randomness under Uniform Reductions
- Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy
- Worst-Case to Average-Case Reductions Revisited
- On the Complexity of Hardness Amplification
- On the Composition of Zero-Knowledge Proof Systems
- Parity helps to compute majority
- A fixed-depth size-hierarchy theorem for AC 0 [⊕ via the coin problem]
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Hardness Amplification Proofs Require Majority
- On Worst‐Case to Average‐Case Reductions for NP Problems
- Theory of Cryptography
- Pseudorandom generators without the XOR lemma
This page was built for publication:
