scientific article; zbMATH DE number 5081744
From MaRDI portal
Publication:3413362
Recommendations
- Average-Case Complexity
- scientific article; zbMATH DE number 1072538
- Average case complexity, revisited
- scientific article; zbMATH DE number 176768
- On the theory of average case complexity
- scientific article; zbMATH DE number 512870
- Structure in average case complexity
- Structural average case complexity
- scientific article; zbMATH DE number 1008511
- Average-case analysis of algorithms using Kolmogorov complexity
Cited in
(61)- On the IO-complexity and approximation languages
- On the theory of average case complexity
- On the NP-isomorphism problem with respect to random instances
- On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \)
- A new algorithm design technique for hard problems
- If NP languages are hard on the worst-case, then it is easy to find their hard instances
- Average-case non-approximability of optimisation problems
- On expected polynomial runtime in cryptography
- Average polynomial time is hard for exponential time under sn-reductions
- Average case complexity, revisited
- Circuit lower bounds for average-case MA
- An Infinitely-Often One-Way Function Based on an Average-Case Assumption
- Average-Case Complexity
- Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy
- Worst-Case to Average-Case Reductions Revisited
- A complete one-way function based on a finite rank free \(\mathbb{Z}\times\mathbb{Z}\)-module
- On an optimal randomized acceptor for graph nonisomorphism
- scientific article; zbMATH DE number 1222584 (Why is no real title available?)
- scientific article; zbMATH DE number 512799 (Why is no real title available?)
- Instance complexity
- More on average case vs approximation complexity
- Matrix Transformation Is Complete for the Average Case
- scientific article; zbMATH DE number 1008511 (Why is no real title available?)
- scientific article; zbMATH DE number 1008518 (Why is no real title available?)
- scientific article; zbMATH DE number 1072538 (Why is no real title available?)
- Complexity of distributions and average-case hardness
- scientific article; zbMATH DE number 2133317 (Why is no real title available?)
- Improving on Gutfreund, Shaltiel, and Ta-Shma's paper ``If NP languages are hard on the worst-case, then it is easy to find their hard instances
- Average-case fine-grained hardness
- Fine-grained derandomization: from problem-centric to resource-centric complexity
- Average-Case Completeness in Tag Systems
- scientific article; zbMATH DE number 7561750 (Why is no real title available?)
- Worst-Case to Average-Case Reductions for Subclasses of P
- A remark on pseudo proof systems and hard instances of the satisfiability problem
- The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
- Some Results on Average-Case Hardness Within the Polynomial Hierarchy
- An algorithm to describe the solution set of any tropical linear system A x = B x
- Fundamentals of Computation Theory
- Fundamentals of Computation Theory
- On Worst‐Case to Average‐Case Reductions for NP Problems
- First-Order Model-Checking in Random Graphs and Complex Networks
- Average-case intractability vs. worst-case intractability
- Rankable distributions do not provide harder instances than uniform distributions
- Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
- Beyond the worst case: semi-random complexity analysis of winner determination
- All natural NP-complete problems have average-case complete versions
- Structural complexity of AvgBPP
- Capturing one-way functions via NP-hardness of meta-complexity
- A duality between one-way functions and average-case symmetry of information
- On average-case hardness of higher-order model checking
- Matrix multiplication reductions
- The average-case complexity of counting cliques in Erdős-Rényi hypergraphs
- Applying the general theory of optimal algorithms in cryptography, steganography, and blockchain technology
- One-way functions and pKt complexity
- Average-case optimization analysis for distributed consensus algorithms on regular graphs
- Complete problems with L-samplable distributions
- Generic properties of a computational task predict human effort and performance
- Generalized juntas and NP-hard sets
- Generic complexity of Presburger arithmetic
- Query complexity in errorless hardness amplification
- Relations between average-case and worst-case complexity
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3413362)
