# Studies in Complexity and Cryptography: Miscellanea on the Interplay between Randomness and Computation (Lecture Notes in Computer Science / Theoretical Computer Science and General Issues)

Language: English

Pages: 563

ISBN: 3642226698

Format: PDF / Kindle (mobi) / ePub

This book presents a collection of 36 pieces of scientific work in the areas of complexity theory and foundations of cryptography: 20 research contributions, 13 survey articles, and 3 programmatic and reflective viewpoint statements. These so far formally unpublished pieces were written by Oded Goldreich, some in collaboration with other scientists.

The articles included in this book essentially reflect the topical scope of the scientific career of Oded Goldreich now spanning three decades. In particular the topics dealt with include average-case complexity, complexity of approximation, derandomization, expander graphs, hashing functions, locally testable codes, machines that take advice, NP-completeness, one-way functions, probabilistically checkable proofs, proofs of knowledge, property testing, pseudorandomness, randomness extractors, sampling, trapdoor permutations, zero-knowledge, and non-iterative zero-knowledge.

All in all, this potpourri of studies in complexity and cryptography constitutes a most valuable contribution to the field of theoretical computer science centered around the personal achievements and views of one of its outstanding representatives.

The C Programming Language (2nd Edition)

A Bug Hunter's Diary: A Guided Tour Through the Wilds of Software Security

bound λ < 1, we consider the property, denoted Eλ , of having a normalized by d adjacency matrix with second eigenvalue at most O. Goldreich et al.: Studies in Complexity and Cryptography, LNCS 6650, pp. 68–75, 2011. c Springer-Verlag Berlin Heidelberg 2011 On Testing Expansion in Bounded-Degree Graphs 69 λ. Actually, we further relax the property testing formulation (as in [9]): Using an additional parameter λ ≥ λ, we only require that – the algorithm must accept (with probability at least

a collection such that Eq. (3) is big (i.e., bounded below by Ω(n)). Bad collections. Obviously, it is a bad idea to have Sj = {j + 1, ..., j + }, since in this case we have | ∪ij=1 Sj | − i ≤ − 1 for every i. It also follows that we cannot use ≤ 2, since in this case one can always ﬁnd an order π such that Eq. (3) is bounded above by − 1. Good collections. An obvious lower bound on Eq. (3) is obtained by the expansion property of the collection C = {Sj }, where the expansion of C is deﬁned as

7]), ζ0 , ..., ζn , such that ζi = ζi (ω) = |Σ|−(n−i) · ΔPn (ω1 · · · ωi ri+1 · · · rn ) ri+1 ,...,rn ∈Σ (3) On the Average-Case Complexity of Property Testing 135 where ω = ω1 · · · ωn . (Indeed, ζn (ω) = ΔPn (ω) and ζ0 = Eω [ζn ].) Note that actually ζi only depends on ω1 · · · ωi . Indeed, the martingale condition holds (i.e., for every ﬁxed ω1 · · · ωi , it holds that Eωi+1 [ζi+1 |ζi ] = ζi ) and |ζi+1 − ζi | ≤ 1 (because |ΔPn (x) − ΔPn (x )| ≤ Δ(x, x )). By the Martingale Tail

corresponding sub-matrix K satisﬁes ρ(L(K )) ≤ Proof: We combine the hypothesis that G is -far from BU(H) with the hypothesis that K is H-mappable, and denote the corresponding H-mapping by φ : R → def [h]. Extending this mapping to V (K ) = r∈R Vr (K ) such that φ(v) = φ(r) for every v ∈ Vr (K ), and using the hypothesis that |L(K )| < 2− N < N/2, we conclude that there are at least N 2 /2 vertex pairs that violate the edge relation of H (i.e., pairs (u, v) ∈ V (K )×V (K ) such that (u, v) ∈ E

that this extra property is easy to test. In fact, the negative example in [9, Prop. 5.4] can arise in our context. Speciﬁcally, consider the set of constraints generated by the constraint ((1, 2), φ) such that φ(S1 , S2 ) = 1 iﬀ both (1) |{i ∈ {1, 2} : Si = ∅}| = 1 and (2) |S1 | ∈ {0} ∪ {2i − 1 : i ∈ N}. (Indeed, condition (1) mandates that if the graph contains an isolated vertex then it contains no edges, whereas condition (2) mandates that all non-isolated vertices have odd degree.) The point