Advice Lower Bounds for the Dense Model Theorem
From MaRDI portal
Publication:2828224
DOI10.1145/2676659zbMath1347.68174OpenAlexW2017812341MaRDI QIDQ2828224
No author found.
Publication date: 24 October 2016
Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2013/3971/
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Pseudo-random numbers; Monte Carlo methods (11K45)
Related Items (1)
Cites Work
- Unnamed Item
- Complexity of hard-core set proofs
- Linear forms and higher-degree uniformity for functions on \(\mathbb F^n_p\)
- The primes contain arbitrarily long polynomial progressions
- One way functions and pseudorandom generators
- Hardness vs randomness
- Boosting and hard-core set construction
- The primes contain arbitrarily long arithmetic progressions
- LINEAR FORMS AND QUADRATIC UNIFORMITY FOR FUNCTIONS ON
- Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
- Query Complexity in Errorless Hardness Amplification
- On Yao’s XOR-Lemma
- The Complexity of Local List Decoding
- List decoding from erasures: bounds and code constructions
- Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification
- Decompositions, approximate structure, transference, and the Hahn-Banach theorem
- Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
- On the Complexity of Hardness Amplification
- A Lower Bound on List Size for List Decoding
- Hardness Amplification Proofs Require Majority
- An arithmetic transference proof of a relative Szemerédi theorem
- Separating succinct non-interactive arguments from all falsifiable assumptions
- How to Fake Auxiliary Input
- Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
This page was built for publication: Advice Lower Bounds for the Dense Model Theorem
