Average Case Complete Problems
From MaRDI portal
Publication:3718151
DOI10.1137/0215020zbMath0589.68032OpenAlexW2100008268WikidataQ56018602 ScholiaQ56018602MaRDI QIDQ3718151
Publication date: 1986
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0215020
Related Items (97)
Complete on average Boolean satisfiability ⋮ Small polyomino packing ⋮ Computational depth: Concept and applications ⋮ Secret sharing based on a hard-on-average problem ⋮ Tilings: recursivity and regularity ⋮ Guarantees for the success frequency of an algorithm for finding Dodgson-election winners ⋮ The complexity of generating test instances ⋮ Generalized juntas and NP-hard sets ⋮ Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity ⋮ Recent results in hardness of approximation ⋮ Nonexistence of minimal pairs for generic computability ⋮ Some properties of sets tractable under every polynomial-time computable distribution ⋮ One way functions and pseudorandom generators ⋮ An average complexity measure that yields tight hierarchies ⋮ Generic complexity of the membership problem for semigroups of integer matrices ⋮ Asymptotic density, immunity and randomness ⋮ On building fine-grained one-way functions from strong average-case hardness ⋮ Average-case intractability vs. worst-case intractability ⋮ Proof of the satisfiability conjecture for large \(k\) ⋮ A new algorithm design technique for hard problems ⋮ A complete one-way function based on a finite rank free \(\mathbb{Z}\times\mathbb{Z}\)-module ⋮ Encoding invariance in average case complexity ⋮ Quantum one-way permutation over the finite field of two elements ⋮ Secure commitment against a powerful adversary ⋮ No NP problems averaging over ranking of distributions are harder ⋮ Sets computable in polynomial time on average ⋮ Rankable distributions do not provide harder instances than uniform distributions ⋮ Complex tilings ⋮ (Nondeterministic) hardness vs. non-malleability ⋮ Average circuit depth and average communication complexity ⋮ Generic-case complexity, decision problems in group theory, and random walks. ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ Coloring k-colorable graphs in constant expected parallel time ⋮ An Infinitely-Often One-Way Function Based on an Average-Case Assumption ⋮ Query complexity in errorless hardness amplification ⋮ Near-optimal dominating sets in dense random graphs in polynomial expected time ⋮ Reductions and convergence rates of average time ⋮ The computational complexity of generating random fractals ⋮ Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem ⋮ On expected polynomial runtime in cryptography ⋮ Asymptotic Density and the Theory of Computability: A Partial Survey ⋮ Structural complexity of AvgBPP ⋮ Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An approach to estimating the average-case complexity of postoptimality analysis of discrete optimization problems ⋮ Relations between average-case and worst-case complexity ⋮ Average case completeness ⋮ First-Order Model-Checking in Random Graphs and Complex Networks ⋮ The complexity of manipulative attacks in nearly single-peaked electorates ⋮ Average-case polynomial-time computability of hamiltonian dynamics ⋮ ON GENERIC NP-COMPLETENESS OF THE BOOLEAN SATISFIABILITY PROBLEM ⋮ A Random NP-complete problem for inversion of 2D cellular automata ⋮ ON GENERIC NP-COMPLETENESS OF THE PROBLEM OF BOOLEAN CIRCUITS SATISFIABILITY ⋮ ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS ⋮ On the theory of average case complexity ⋮ Average case complexity under the universal distribution equals worst- case complexity ⋮ Recovering nonuniform planted partitions via iterated projection ⋮ Control complexity in Bucklin and fallback voting: an experimental analysis ⋮ Average-case complexity and decision problems in group theory. ⋮ Complete problems with L-samplable distributions ⋮ An infinitely-often one-way function based on an average-case assumption ⋮ On expected probabilistic polynomial-time adversaries: a suggestion for restricted definitions and their benefits ⋮ Frequency of correctness versus average polynomial time ⋮ Unnamed Item ⋮ On the Hardness of Learning with Rounding over Small Modulus ⋮ On complete one-way functions ⋮ Generic case completeness ⋮ An Average Case NP-complete Graph Colouring Problem ⋮ Query Complexity in Errorless Hardness Amplification ⋮ Notes on Levin’s Theory of Average-Case Complexity ⋮ On Yao’s XOR-Lemma ⋮ Average Case Complexity, Revisited ⋮ Hybrid Elections Broaden Complexity-Theoretic Resistance to Control ⋮ Generation of solved instances of Multiconstraint Knapsack problem and its applications to Private Key Cipher ⋮ Structural Complexity of AvgBPP ⋮ Exact recovery in the hypergraph stochastic block model: a spectral algorithm ⋮ Average-Case Completeness in Tag Systems ⋮ From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial) ⋮ Asymptotic density and computability ⋮ The computational complexity of pattern formation ⋮ On the complexity of deadlock detection in families of planar nets ⋮ Unnamed Item ⋮ Complete distributional problems, hard languages, and resource-bounded measure ⋮ Polynomial time samplable distributions ⋮ Unnamed Item ⋮ Complexity-theoretic models of phase transitions in search problems ⋮ Public-key cryptography and invariant theory ⋮ Parameterized clique on inhomogeneous random graphs ⋮ Malign distributions for average case circuit complexity. ⋮ On the typical case complexity of graph optimization ⋮ On the average-case complexity of parameterized clique ⋮ On average time hierarchies ⋮ Complete problems with L-samplable distributions ⋮ The Complexity of Public-Key Cryptography ⋮ From logic to tiling ⋮ Randomness vs time: Derandomization under a uniform assumption
This page was built for publication: Average Case Complete Problems
