Computational complexity: a conceptual perspective

By Oded Goldreich. SIGA, 2008

600 citations recorded by the source corpus.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/d0d01ec3c0051fa408ea1da9605ecb4ed53c634d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

The efficient certification of knottedness and Thurston norm (2016, methodology): “′|| 1 ≤ 2400t||φ˜|| 1; this will be provided by Addendum 11.5; (6) a triangulation T ′′ of a 3-manifold M′′, obtained from T ′ by attaching a 3-ball, triangulated as a cone, to each component of ∂M′; (7) a 1-cocycle φ′′ on M′′ that extends φ′ and satisﬁes ||φ′′|| 1 ≤ (1+1600t)||φ′|| 1; (8) the certi”
Nature-Inspired Optimization Algorithms: Challenges and Open Problems (2020, background): “For a moderate or large n , this problem becomes an NP-hard problem [Cook(1983), Arara and Barak(2009), Goldreich(2008)].”
Witness encryption and its applications (2013, background): “For example, consider the NP-complete 3-Exact Cover problem (Propo-sition 2.25, [14]), where an instance is deﬁned by a set of subsets T 1 , . . . , T (cid:2) of [ n ] such that each T i = 3, and the problem is to ﬁnd an exact cover T i 1 , . . . , T i t such that each universe [ n ] is contained…”
Learning Sparse Causal Models is not NP-hard (2013, background): “See (Garey and Johnson, 1979) for a standard introduction to the subject, and e.g. (Goldreich, 2008) for a more modern approach.”
Adiabatic Quantum Computing (2016, methodology): “The proof of this “amplification lemma” [see, e.g., (Goldreich, 2008; Marriott and Watrous, 2005; Nagaj et al., 2009)] is interesting since it invokes the Chernoff bound, a widely used tool.”
Adversarial Examples from Cryptographic Pseudo-Random Generators (2018, background): “from D1(ω). Let us ﬁx some constant c > 1 and denote Dn 0 = unif({0,1}n c) and Dn 1(N) the distribution of the ﬁrst nc bits of s◦ GN(s) where sis a uniformly random element of {0,1}n. Theorem 3.1 ([1, 4, 3]). Assuming that for inﬁnitely many N the computational statistical distance of {(Dn 0,D1n(”
A polynomial upper bound on Reidemeister moves (2013, background): “y that a polynomial time algorithm could be ruled out, even conditional upon the hypothesis that P 6= NP, because it is widely conjectured that problems in NP ∩ co-NP are not NP-complete (see p.95 of [10]). We also have a result for split links. Theorem 1.2. Let D be a diagram of a split link with c”