Computational Complexity – Oded Goldreich (1)

Figure 7.2: Proofs of hardness amplification: Organization. 7.2.1.1. From Worst-Case Hardness to Mild Average-Case Hardness The transformation of worst-case hardness into average-case hardness (even in a mild sense) is indeed remarkable. Note that worst-case hardness may be due to a relatively small number of instances, whereas even mild forms of average-case hardness refer to a very large number of possible instances.11 In other words, we should transform hard- ness that may occur on a negligible fraction of the instances into hardness that occurs on a noticeable fraction of the instances.

Intuitively, we should “spread” the hardness of few instances (of the original problem) over all (or most) instances (of the trans- formed problem). The counter-positive view is that computing the value of typical in- stances of the transformed problem should enable solving the original problem on every instance. The aforementioned transformation is based on the self-correction paradigm, to be reviewed first. The paradigm refers to functions g that can be evaluated at any desired point by using the value of g at a few random points, where each of these points is uniformly distributed in the function’s domain (but indeed the points are not independently distributed).

The key observation is that if g(x) can be reconstructed based on the value of g at t such random points, then such a reconstruction can tolerate a 1/3t fraction of errors (regarding the values of g). Thus, if we can correctly obtain the value of g on all but at most a 1/3t fraction of its domain, then we can probabilistically recover the correct value of g at any point with very high probability.

It follows that if no probabilistic polynomial-time algorithm can correctly compute g in the worst-case sense, then every probabilistic polynomial-time algorithm must fail to correctly compute g on more than a 1/3t fraction of its domain. The archetypical example of a self-correctable function is any m-variate polynomial of individual degree d over a finite field F such that |F| > dm + 1. The value of such a polynomial at any desired point x can be recovered based on the values of dm + 1 points (other than x) that reside on a random line that passes through x.

Complexity Theory is a central field of the theoretical foundations of computer science. It is concerned with the general study of the intrinsic complexity of computational tasks; that is, it addresses the question of what can be achieved within limited time (and/or with other limited natural computational resources). This book offers a conceptual perspective on Complexity Theory. It is intended to serve as an introduction for advanced undergraduate and graduate students, either as a textbook or for self-study.

The book will also be useful to experts, since it provides expositions of the various sub-areas of Complexity Theory such as hardness amplification, pseudoran- domness, and probabilistic proof systems. In each case, the author starts by posing the intuitive questions that are addressed by the sub-area and then discusses the choices made in the actual formulation of these questions, the approaches that lead to the answers, and the ideas that are embedded in these answers.

Oded Goldreich is a Professor of Computer Science at the Weizmann Institute of Science and an Incumbent of the Meyer W. Weisgal Professorial Chair. He is an editor for the SIAM Journal on Computing, the Journal of Cryptology, and Computational Complex- ity and previously authored the books Modern Cryptography, Probabilistic Proofs and Pseudorandomness, and the two-volume work Foundations of Cryptography.

Computational Complexity A Conceptual Perspective Oded Goldreich Weizmann Institute of Science CAMBRIDGE UNIVERSITY PRESS Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo Cambridge University Press The Edinburgh Building, Cambridge CB2 8RU, UK First published in print format ISBN-13 978-0-521-88473-0 ISBN-13 978-0-511-39882-7 © Oded Goldreich 2008 2008 Information on this title: www.cambridge.org/9780521884730 This publication is in copyright.

Subject to statutory exception and to the provision of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. Cambridge University Press has no responsibility for the persistence or accuracy of urls for external or third-party internet websites referred to in this publication, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate.

This is a short excerpt from the opening of “” by Unknown, quoted for review and introduction purposes. All rights belong to the copyright holders.

Book Information

• Unique ID: 8208b380d8137475
• File Extension: .pdf
• File Size: 4,370,214 bytes (4.168 MB)
• Title: –
• Author: Unknown
• ISBN: 9780521884730, 9780511398827
• Pages: 633
• Language: English (en)

Reading & Word Statistics

• Estimated Reading Time: 1688.7 minutes
• Total Words: 337,741
• Total Characters: 2,003,763
• Average Words per Page: 533.56
• Average Characters per Page: 3165.5

Most Frequent Words

proof (1178), complexity (1115), problem (1112), input (979), problems (971), every (904), theorem (862), set (810), see (810), time (808), algorithm (780), case (777), note (772), probability (750), function (730), thus (712), one (675), exercise (675), polynomial (652), definition (631), two (610), using (573), holds (569), length (551), random (548), machine (544), given (521), polynomial-time (506), reduction (502), exists (480), indeed (478), space (475), section (469), graph (469), number (465), log (464), search (452), functions (441), consider (441), first (426), class (420), computational (415), computation (408), following (408), poly (404), corresponding (397), natural (396), decision (381), also (375), probabilistic (375), fact (373), circuits (365), prove (361), circuit (360), oracle (359), pseudorandom (354), let (351), value (350), size (349), rather (344), specifically (343), algorithms (341), theory (335), proofs (334), verifier (328), follows (326), systems (322), constant (322), model (320), between (319), defined (310), used (308), foregoing (302), system (301), general (300), output (299), def (299), use (294), notion (288), error (288), whether (288), construction (287), sequence (287), boolean (283), generators (283), say (274), possible (263), instances (262), randomness (261), resp (258), pcp (254), randomized (247), efficient (246), uniform (243), recall (240), furthermore (235), whereas (234), least (233), vertices (233), generator (232).

PDF Download