scientific article
From MaRDI portal
Publication:3413362
zbMath1147.68025MaRDI QIDQ3413362
Luca Trevisan, Andrej Bogdanov
Publication date: 4 January 2007
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (21)
On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \) ⋮ Generic properties of a computational task predict human effort and performance ⋮ Generalized juntas and NP-hard sets ⋮ Generic complexity of Presburger arithmetic ⋮ Circuit Lower Bounds for Average-Case MA ⋮ 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 ⋮ On an optimal randomized acceptor for graph nonisomorphism ⋮ A remark on pseudo proof systems and hard instances of the satisfiability problem ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ An Infinitely-Often One-Way Function Based on an Average-Case Assumption ⋮ Unnamed Item ⋮ Beyond the worst case: semi-random complexity analysis of winner determination ⋮ Query complexity in errorless hardness amplification ⋮ On expected polynomial runtime in cryptography ⋮ Structural complexity of AvgBPP ⋮ First-Order Model-Checking in Random Graphs and Complex Networks ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ An algorithm to describe the solution set of any tropical linear system \(A \odot x = B \odot x\) ⋮ Unnamed Item ⋮ Average-Case Completeness in Tag Systems
This page was built for publication:
