The following pages link to Average Case Complete Problems (Q3718151):
Displaying 47 items.
- Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity (Q2373445) (← links)
- Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey (Q2436695) (← links)
- Public-key cryptography and invariant theory (Q2577586) (← links)
- On the typical case complexity of graph optimization (Q2581548) (← links)
- On expected polynomial runtime in cryptography (Q2695649) (← links)
- On the Hardness of Learning with Rounding over Small Modulus (Q2796126) (← links)
- Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem (Q2968165) (← links)
- Asymptotic Density and the Theory of Computability: A Partial Survey (Q2970976) (← links)
- Query Complexity in Errorless Hardness Amplification (Q3088136) (← links)
- Notes on Levin’s Theory of Average-Case Complexity (Q3088187) (← links)
- On Yao’s XOR-Lemma (Q3088189) (← links)
- Average Case Complexity, Revisited (Q3088195) (← links)
- Asymptotic density, immunity and randomness (Q3195648) (← links)
- Hybrid Elections Broaden Complexity-Theoretic Resistance to Control (Q3392307) (← links)
- Structural Complexity of AvgBPP (Q3392950) (← links)
- Complex tilings (Q3503757) (← links)
- An Infinitely-Often One-Way Function Based on an Average-Case Assumption (Q3511459) (← links)
- An infinitely-often one-way function based on an average-case assumption (Q3586759) (← links)
- Generation of solved instances of Multiconstraint Knapsack problem and its applications to Private Key Cipher (Q4718638) (← links)
- An Average Case NP-complete Graph Colouring Problem (Q4962593) (← links)
- Average-case polynomial-time computability of hamiltonian dynamics (Q5005130) (← links)
- The Complexity of Public-Key Cryptography (Q5021130) (← links)
- The complexity of generating test instances (Q5048939) (← links)
- Recent results in hardness of approximation (Q5054764) (← links)
- Complete problems with L-samplable distributions (Q5056117) (← links)
- Generic complexity of the membership problem for semigroups of integer matrices (Q5071228) (← links)
- From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial) (Q5090451) (← links)
- Average-Case Completeness in Tag Systems (Q5090467) (← links)
- (Q5092470) (← links)
- Secure commitment against a powerful adversary (Q5096801) (← links)
- (Q5140842) (← links)
- (Q5150520) (← links)
- ON GENERIC NP-COMPLETENESS OF THE BOOLEAN SATISFIABILITY PROBLEM (Q5151063) (← links)
- ON GENERIC NP-COMPLETENESS OF THE PROBLEM OF BOOLEAN CIRCUITS SATISFIABILITY (Q5151438) (← links)
- Nonexistence of minimal pairs for generic computability (Q5300075) (← links)
- ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS (Q5401598) (← links)
- First-Order Model-Checking in Random Graphs and Complex Networks (Q5874510) (← links)
- (Q6054746) (← links)
- (Q6084358) (← links)
- Sets computable in polynomial time on average (Q6085734) (← links)
- Rankable distributions do not provide harder instances than uniform distributions (Q6085735) (← links)
- (Nondeterministic) hardness vs. non-malleability (Q6097260) (← links)
- Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) (Q6140986) (← links)
- Structure in average case complexity (Q6487946) (← links)
- A hard problem that is almost always easy (Q6487965) (← links)
- Theoretical computer science: computational complexity (Q6602263) (← links)
- On building fine-grained one-way functions from strong average-case hardness (Q6665547) (← links)
