Towards proving strong direct product theorems
From MaRDI portal
Publication:1889851
DOI10.1007/s00037-003-0175-xzbMath1084.68542OpenAlexW3157388067MaRDI QIDQ1889851
Publication date: 13 December 2004
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-003-0175-x
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Interactive Information Complexity ⋮ Interactive Information Complexity ⋮ A direct product theorem for two-party bounded-round public-coin communication complexity ⋮ A discrepancy lower bound for information complexity ⋮ A strong direct product theorem for quantum query complexity ⋮ Derandomized parallel repetition theorems for free games ⋮ Query-to-Communication Lifting for BPP ⋮ Improved direct product theorems for randomized query complexity ⋮ Unnamed Item ⋮ Simulation theorems via pseudo-random properties ⋮ New Strong Direct Product Results in Communication Complexity ⋮ Rectangles Are Nonnegative Juntas ⋮ Upper and Lower Bounds on the Power of Advice ⋮ The Communication Complexity of Set Intersection and Multiple Equality Testing ⋮ Query-to-Communication Lifting Using Low-Discrepancy Gadgets ⋮ Unnamed Item
