The following pages link to (Q3413362):
Displaying 36 items.
- A complete one-way function based on a finite rank free \(\mathbb{Z}\times\mathbb{Z}\)-module (Q376132) (← links)
- On an optimal randomized acceptor for graph nonisomorphism (Q413276) (← links)
- More on average case vs approximation complexity (Q430823) (← links)
- An algorithm to describe the solution set of any tropical linear system \(A \odot x = B \odot x\) (Q541953) (← links)
- Average-case intractability vs. worst-case intractability (Q598182) (← links)
- All natural NP-complete problems have average-case complete versions (Q626691) (← links)
- Structural complexity of AvgBPP (Q638488) (← links)
- Complete problems with L-samplable distributions (Q804284) (← links)
- Generic properties of a computational task predict human effort and performance (Q825138) (← links)
- Generalized juntas and NP-hard sets (Q837194) (← links)
- Generic complexity of Presburger arithmetic (Q848747) (← links)
- Query complexity in errorless hardness amplification (Q901934) (← links)
- Relations between average-case and worst-case complexity (Q927398) (← links)
- On the IO-complexity and approximation languages (Q1112018) (← links)
- On the theory of average case complexity (Q1190984) (← links)
- Complete distributional problems, hard languages, and resource-bounded measure (Q1575682) (← links)
- On the NP-isomorphism problem with respect to random instances (Q1892213) (← links)
- On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \) (Q2120065) (← links)
- A new algorithm design technique for hard problems (Q2173301) (← links)
- If NP languages are hard on the worst-case, then it is easy to find their hard instances (Q2475580) (← links)
- Average-case non-approximability of optimisation problems (Q2642911) (← links)
- On expected polynomial runtime in cryptography (Q2695649) (← links)
- Circuit Lower Bounds for Average-Case MA (Q3194723) (← links)
- An Infinitely-Often One-Way Function Based on an Average-Case Assumption (Q3511459) (← links)
- Average-Case Complexity (Q3522267) (← links)
- Instance complexity (Q4299297) (← links)
- (Q4336271) (← links)
- Average-case fine-grained hardness (Q4977996) (← links)
- Fine-grained derandomization: from problem-centric to resource-centric complexity (Q5002697) (← links)
- Average-Case Completeness in Tag Systems (Q5090467) (← links)
- (Q5092472) (← links)
- A remark on pseudo proof systems and hard instances of the satisfiability problem (Q5109236) (← links)
- The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs (Q5157395) (← links)
- First-Order Model-Checking in Random Graphs and Complex Networks (Q5874510) (← links)
- Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) (Q6140986) (← links)
- Beyond the worst case: semi-random complexity analysis of winner determination (Q6167260) (← links)
