The following pages link to Average Case Complete Problems (Q3718151):
Displaying 50 items.
- A complete one-way function based on a finite rank free \(\mathbb{Z}\times\mathbb{Z}\)-module (Q376132) (← links)
- An approach to estimating the average-case complexity of postoptimality analysis of discrete optimization problems (Q464980) (← links)
- The complexity of manipulative attacks in nearly single-peaked electorates (Q490458) (← links)
- Average-case intractability vs. worst-case intractability (Q598182) (← links)
- Structural complexity of AvgBPP (Q638488) (← links)
- A Random NP-complete problem for inversion of 2D cellular automata (Q672376) (← links)
- Average-case complexity and decision problems in group theory. (Q703812) (← links)
- On complete one-way functions (Q734307) (← links)
- Generic case completeness (Q736607) (← links)
- Complete problems with L-samplable distributions (Q804284) (← links)
- Guarantees for the success frequency of an algorithm for finding Dodgson-election winners (Q835761) (← links)
- Generalized juntas and NP-hard sets (Q837194) (← links)
- Query complexity in errorless hardness amplification (Q901934) (← links)
- Relations between average-case and worst-case complexity (Q927398) (← links)
- Frequency of correctness versus average polynomial time (Q989533) (← links)
- One way functions and pseudorandom generators (Q1100894) (← links)
- Average case completeness (Q1176231) (← links)
- On the theory of average case complexity (Q1190984) (← links)
- Average case complexity under the universal distribution equals worst- case complexity (Q1198047) (← links)
- The computational complexity of pattern formation (Q1279214) (← links)
- On the complexity of deadlock detection in families of planar nets (Q1285587) (← links)
- On average time hierarchies (Q1313704) (← links)
- Some properties of sets tractable under every polynomial-time computable distribution (Q1350351) (← links)
- An average complexity measure that yields tight hierarchies (Q1355380) (← links)
- No NP problems averaging over ranking of distributions are harder (Q1391309) (← links)
- Generic-case complexity, decision problems in group theory, and random walks. (Q1399190) (← links)
- Complete distributional problems, hard languages, and resource-bounded measure (Q1575682) (← links)
- Polynomial time samplable distributions (Q1578504) (← links)
- Complexity-theoretic models of phase transitions in search problems (Q1583531) (← links)
- From logic to tiling (Q1603696) (← links)
- Randomness vs time: Derandomization under a uniform assumption (Q1604214) (← links)
- Encoding invariance in average case complexity (Q1678756) (← links)
- Quantum one-way permutation over the finite field of two elements (Q1679363) (← links)
- Malign distributions for average case circuit complexity. (Q1854270) (← links)
- Complete on average Boolean satisfiability (Q1872642) (← links)
- Tilings: recursivity and regularity (Q1884987) (← links)
- The computational complexity of generating random fractals (Q1946896) (← links)
- Recovering nonuniform planted partitions via iterated projection (Q2002551) (← links)
- Asymptotic density and computability (Q2066410) (← links)
- On building fine-grained one-way functions from strong average-case hardness (Q2170063) (← links)
- Proof of the satisfiability conjecture for large \(k\) (Q2171413) (← links)
- A new algorithm design technique for hard problems (Q2173301) (← links)
- Control complexity in Bucklin and fallback voting: an experimental analysis (Q2256718) (← links)
- On expected probabilistic polynomial-time adversaries: a suggestion for restricted definitions and their benefits (Q2267359) (← links)
- Exact recovery in the hypergraph stochastic block model: a spectral algorithm (Q2310389) (← links)
- Parameterized clique on inhomogeneous random graphs (Q2341758) (← links)
- On the average-case complexity of parameterized clique (Q2344729) (← links)
- Small polyomino packing (Q2361496) (← links)
- Computational depth: Concept and applications (Q2368976) (← links)
- Secret sharing based on a hard-on-average problem (Q2369061) (← links)
