{'fraction_non_alphanumeric': 0.02960039467192896, 'fraction_numerical': 0.008880118401578688, 'mean_word_length': 4.9298245614035086, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
PCPs and Instance Compression from a Cryptographic Lens

Modern cryptography fundamentally relies on the assumption that the adversary trying to break the scheme is computationally bounded. This assumption lets us construct cryptographic protocols and primitives that are known to be impossible otherwise. In this work we explore the eﬀect of bounding the adversary’s power in other information theoretic proof-systems and show how to use this assumption to bypass impossibility results. We ﬁrst consider the question of constructing succinct PCP s. These are PCP s whose length is polynomial only in the length of the original NP witness (in contrast to standard PCP s whose length is proportional to the non-deterministic veriﬁcation time). Unfortunately, succinct PCP s are known to be impossible to construct under standard complexity assumptions. Assuming the sub-exponential hardness of the learning with errors (LWE) problem, we construct succinct probabilistically checkable arguments or PCA s (Zimand 2001, Kalai and Raz 2009), which are PCP s in which soundness is guaranteed against eﬃciently generated false proofs. Our PCA construction is for every NP relation that can be veriﬁed by a small-depth circuit (e.g., SAT, clique, TSP, etc.) and in contrast to prior work is publicly veriﬁable and has constant query complexity. Curiously, we also show, as a proof-of-concept, that such publicly-veriﬁable PCA s can be used to derive hardness of approximation results. Second, we consider the notion of Instance Compression (Harnik and Naor, 2006). An instance compression scheme lets one compress, for example, a CNF formula ϕ on m variables and n (cid:29) m clauses to a new formula ϕ (cid:48) with only poly( m ) clauses, so that ϕ is satisﬁable if and only if ϕ (cid:48) is satisﬁable. Instance compression has been shown to be closely related to succinct PCP s and is similarly highly unlikely to exist. We introduce a computational analog of instance compression in which we require that if ϕ is unsatisﬁable then