Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition

DOI10.1145/2746539.2746630zbMath1321.68305arXiv1505.06362OpenAlexW3105296533MaRDI QIDQ2941514

Prahladh Harsha, Irit Dinur, Guy Kindler

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1505.06362

zbMATH Keywords

compositionsliding scale conjecturePCPsdecodable PCPs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

Subquadratic SNARGs in the random oracle model ⋮ A toolbox for barriers on interactive oracle proofs ⋮ ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming

This page was built for publication: Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition