Average Case Complete Problems

Cited In (only showing first 100 items - show all)

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

This page was built for publication: Average Case Complete Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3718151)