Paper Info
Title
Transparent (Holographic) Proofs
Abstract
Informally, a mathematical proof is transparent (or holographic) if it can be verified with large confidence by a small number of spotchecks. Recent work of a large group of researchers has shown that this seemingly paradoxical concept can be formalized and is feasible in a remarkably strong sense. This fact in turn has surprising implications toward the intractability of approximate solutions of a wide range of discrete optimization problems. Below we state some of the main results in the area, with pointers to the literature. David Johnson's excellent survey [Jo] of the same subject gives a different angle and greater detail, including many additional references.
Year
DOI
Venue
1993
10.1007/3-540-56503-5_52
STACS
Keywords
Field
DocType
discrete optimization
Small number,Pointer (computer programming),Discrete mathematics,Holography,Algebra,Computer science,Mathematical proof,Discrete optimization problem,Time complexity,Polynomial-time approximation scheme
Conference
ISBN
Citations 
PageRank 
3-540-56503-5
6
1.02
References 
Authors
12
1
Name
Order
Citations
PageRank
Laszlo Babai13537573.58