betaFeedback

WorksComputer Science

Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy kk-LIN\mathsf{LIN} Over Expanders

Abstract

We give a public key encryption scheme that is provably secure against poly-size adversaries, assuming nlog⁡αnn^{\log^αn} hardness of the standard planted clique conjecture, for any α∈(0,1)α\in (0,1), and a relatively mild hardness conjecture about noisy k\mbox{-}\mathsf{LIN} over expanders that is not known to imply public-key encryption on its own. Both of our conjectures correspond to natural average-case variants of NP-complete problems and have been studied for multiple decades, with unconditional lower bounds supporting them in a variety of restricted models of computation. Our encryption scheme answers an open question in a seminal work by Applebaum, Barak, and Wigderson [STOC'10].

Introduction

Public-key encryption (PKE) [32, 74] is a fundamental primitive enabling secure communication via open and untrusted channels. Despite the immense success of public-key cryptography as a field, and despite intense interest and effort over nearly five decades, we know of surprisingly few sources of hardness that can be nontrivially utilized in building PKE1.

Furthermore, almost all of these rely on structured hardness rooted in domains such as number theory, algebra, coding theory or lattices (see, for example [32, 74, 71, 16, 9]). This is in stark contrast with private-key encryption and one-way functions, where any hard-on-average problem satisfying very mild structural requirements suffices (e.g. planted clique problem, random constraint satisfaction problems, and sparse PCA).

The overarching goal of this research is to devise new ways of nontrivially leveraging other sources of hardness to enable public-key encryption (and beyond). One such untapped source of hardness is the domain of statistical inference and average-case complexity. For decades, these areas have excelled at identifying and studying natural average-case problems in domains such as graph theory, combinatorics and machine learning from both algorithmic and hardness perspectives. There are also systematic means to give evidence of hardness in restricted algorithmic models such as sum-of-squares [76, 66, 70, 62], statistical-query model [56], low-degree tests framework [BHK⁺19, Hop18] and many others. Unfortunately, despite an abundant supply of well-studied average-case problems, what we seem to lack are algorithmic reduction techniques that can nontrivially leverage these problems to create the kinds of “trapdoor” structures that are needed to create public-key encryption. Can we develop new techniques that would allow us to add to the short list of hardness conjectures that can be nontrivially used to build PKE?

In this work, we humbly add one more source of hardness to this list, namely nlog⁡αnn^{\log^{\alpha} n} hardness of the classic planted clique conjecture, for any α∈(0,1)\alpha\in(0,1). We do by developing a new quasi-polynomial-time sparsification technique, that can “simulate” a random sparse graph from the point of view of achieving a desired level of expansion. We now elaborate.

Can the planted clique conjecture help us build PKE? Let us examine the classic planted-clique conjecture which roughly states that no efficient algorithm can determine, with constant advantage, whether a random graph contains a planted clique of an appropriate size. This conjecture is the oldest [7, 52 Kuč95, 54] and arguably the most well-studied conjecture in average-case complexity. Moreover, its worst-case counterpart, the max clique problem, is a classic NP-complete problem. Despite decades of research on the planted clique conjecture [52 Kuč95, 35, 53, 5 ABI⁺23, MRS20, 45 AAK⁺07, 2, 21, 14, 13, 48], constructing a PKE nontrivially utilizing this conjecture has remained elusive.

A seminal work that kick-started the search of PKE from such average-case complexity problems was that of Applebaum, Barak and Wigderson [5] which showed several PKE schemes from various statistical inference problems. Of particular relevance to this work is a construction recipe that shows how to design a PKE from any local CSP and a variant planted graph conjecture that, roughly speaking, posits the hardness of finding a small subgraph planted in a random sparse kk-regular bipartite graph. Indeed, the work of [5] leaves finding a way to leverage the classic planted clique conjecture directly to build PKE as an open question.

We make significant progress towards this question. In particular, our main result builds a PKE scheme from two very well-studied [AKS98, Jer92, Kuč95, Kar76, ERSY22, JP00, ABW10, ABI⁺23, MRS20, [45, 1, 2, 21, 14, 13, 48, 37, 40, 34, 31, 17, 65, 61, 50, 10, 19, 73, 39, 12, 25, 58] average-case complexity problems, namely: nlog⁡αnn^{\log^\alpha n} hardness of the standard planted clique conjecture on graphs with nn vertices, for any constant α∈(0,1)\alpha\in(0,1), together with a mild conjecture on the hardness of the noisy kk-LIN problem2 over expanding graphs. Our kk-LIN conjecture when interpreted in the special case of equations over F2\mathbb{F}_2 also gives rise to one of the most studied hard distributions for MAX-kk-SAT (e.g. [44, 75, 38, 58]).

Indeed, neither of these well-studied conjectures (with parameters that we use) were previously known to imply PKE. To the best of our knowledge, ours is the first work that constructs a PKE making critical use of the standard planted clique conjecture3. At the heart of our work is a new algorithmic technique to leverage this conjecture to create “trapdoor-friendly” structures.

We now introduce our hardness conjectures, and go through a brief discussion of their history.

Conjecture 1: The Planted Clique Problem. Let G(n,12)\mathcal{G}(n,\frac{1}{2}) denote the standard Erdős–Rényi distribution4 over random graphs. Let G(n,12,nδ)\mathcal{G}(n,\frac{1}{2},n^\delta) denote the distribution that first samples a graph from G(n,12)\mathcal{G}(n,\frac{1}{2}) and then plants a clique on nδn^\delta randomly selected nodes.

Conjecture 1.1 (nlog⁡αnn^{\log^\alpha n} hardness5 of the Planted Clique Conjecture). There exist constants 0<α<10 < \alpha< 1 and δ∈(0,12)\delta\in(0,\frac{1}{2}) such that, for all nO(log⁡αn)n^{O(\log^\alpha n)}-size algorithms A\mathcal{A},

∣Pr⁡[A(G)=1∣G←$G(n,12)]−Pr⁡[A(G)=1∣G←$G(n,12,nδ)]∣≤13.\left| \Pr\left[\mathcal{A}(G)=1 \mid G \xleftarrow{\$} \mathcal{G}\left(n,\frac{1}{2}\right)\right] - \Pr\left[\mathcal{A}(G)=1 \mid G \xleftarrow{\$} \mathcal{G}\left(n,\frac{1}{2},n^\delta\right)\right] \right| \leq\frac{1}{3}.

Remark 1.2. For conciseness, we refer to the above conjecture simply as “the planted clique conjecture” in the body of this paper.

Note that we only require the existence of some constants; for example, α=10−3\alpha= 10^{-3} and δ=10−3\delta= 10^{-3} would suffice. Even stronger versions have been considered, for example the “strongish planted clique conjecture” of Manurangsi, Rubinstein, and Schramm [MRS20], which posits no(log⁡n)n^{o(\log n)} hardness for the same problem.

Planted clique has been rigorously studied in statistical inference and average-case complexity ever since its introduction [7, 52, 60, 54, 35, 53, 5, 3 MRS20, 45, 1, 2, 21, 14, 13, 48, 65, 61, 50]. Many different algorithms have been proposed (e.g. [7, 37, 40, 34, 31]), but none of the currently known algorithms succeed in determining, with constant advantage, whether there exists a planted clique of size smaller than o(n)o(\sqrt{n}) in polynomial time. Furthermore, the problem has been very well analyzed in restricted algorithmic models, and is subject to strong lower bounds in these models, including sum-of-squares [17] and other frameworks [52, 30, 72, 36, 37], providing rigorous evidence for hardness. The recent work of Hirahara and Shimizu also showed a search-to-decision reduction for planted clique [48], so our conjecture is equivalent to assuming only the hardness of the search version of the problem.

Noisy kk-LIN Problem over Expanders

We now describe the noisy kk-LIN problem over expander graphs. This is a particular well-studied instantiation of local CSPs over expander graphs where the predicate is just the linear function. As in standard planted CSPs over expander graphs, the problem is defined with respect to a graph represented by a collection of sets (S1,…,Sm)(S_1,\ldots,S_m). Here, nn is the number of variables and m=m(n)m=m(n) is the number of clauses (each clause being a sparse linear equation over a subset of the variables), and each set SiS_i is of size exactly k=k(n)k=k(n) and supported over {1,…,n}\{1,\ldots,n\}. The set system satisfies a property that is called (γ,k,t)(\gamma,k,t)-expansion, which requires that for any collection {Si}i∈I\{S_i\}_{i\in I} of size at most tt, the union of SiS_i has at least γ⋅k⋅∣I∣\gamma\cdot k\cdot|I| many distinct variables, where γ\gamma is a constant bigger than 12\frac{1}{2}. See Definition 3.1 for formal details.

In the context of the noisy kk-LIN problem, one is asked to distinguish between the joint distributions (A,b=As+e)(\mathbf{A},\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e}) and (A,b=r)(\mathbf{A},\mathbf{b}=\mathbf{r}), where A\mathbf{A} is a sparse matrix in Fpm×n\mathbb{F}_p^{m\times n} produced by taking an indicator matrix I∈{0,1}m×n\mathbf{I}\in\{0,1\}^{m\times n} representing the sets {S1,…,Sm}\{S_1,\ldots,S_m\} and replacing each nonzero entry in I\mathbf{I} with a random element of Fp\mathbb{F}_p. Specifically, for all ii, the ithi^{\mathrm{th}} row of A\mathbf{A} encodes the set SiS_i: we have that Ai,j≠0A_{i,j}\ne0 if j∈Sij\in S_i and 00 otherwise. The secret s∈Fpn\mathbf{s}\in\mathbb{F}_p^n and r∈Fpm\mathbf{r}\in\mathbb{F}_p^m are uniformly chosen random vectors of appropriate dimensions, and every entry of e\mathbf{e} is sampled independently from a Bernoulli distribution with probability η\eta. Backed by systematic lower bounds over many years [44, 38, 75, 19, 73, 39, 12, 25, 58], we formalize the following widely believed conjecture:

Conjecture 1.3 (Noisy kk-LIN Conjecture). There exists a constant γ∈(12,1)\gamma\in(\frac{1}{2},1) such that the following holds. Let α,ς\alpha,\varsigma be any constants with α∈(0,1)\alpha\in(0,1) and ς>0\varsigma>0. Then, for nn large enough, prime p=nΩ(1)p=n^{\Omega(1)}, k=Ω(log⁡(n))k=\Omega(\log(n)), we have the following: Let I∈{0,1}m×n\mathbf{I}\in\{0,1\}^{m\times n} correspond to any (γ,k,2(log⁡n)α)(\gamma,k,2^{(\log n)^\alpha})-expanding set system, and let A∈Fpm×n\mathbf{A}\in\mathbb{F}_p^{m\times n} be sampled by replacing each nonzero entry in I\mathbf{I} with a random element in Fp\mathbb{F}_p. It holds that

(A,b=As+e),(\mathbf{A},\mathbf{b}=\mathbf{A}\mathbf{s}+\mathbf{e}),

is computationally indistinguishable from

(A,b=r).(\mathbf{A},\mathbf{b}=\mathbf{r}).

We only require indistinguishability with respect to a small constant distinguishing advantage, specifically 116\frac{1}{16}. Above, s←Fpn\mathbf{s}\leftarrow\mathbb{F}_p^n and r←Fpm\mathbf{r}\leftarrow\mathbb{F}_p^m are uniformly randomly chosen and e∈Fpm\mathbf{e}\in\mathbb{F}_p^m sampled as:

ei={Random element of Fp, with probability η=(log⁡n)−ς,0, otherwise.e_i= \begin{cases} \text{Random element of }\mathbb{F}_p,\text{ with probability }\eta=(\log n)^{-\varsigma},\\ 0,\text{ otherwise.} \end{cases}

Remark 1.4. In fact, we can use the search version of the above conjecture, and the matrix A\mathbf{A} for our PKE scheme will satisfy additional desirable properties6. See § 4 for details.

Intuitively, the conjecture becomes more “secure” for larger values of kk, and if the expansion threshold tt and the error probability η\eta are large. In particular, it is desirable that tt is at least Ω(log⁡n)\Omega(\log n), and in our case, it is actually much larger, namely t=2log⁡αnt=2^{\log^\alpha n}. Keeping this value of tt in mind, we can mentally classify the problem in two regimes when it comes to using noisy kk-LIN for designing PKE, based on the noise probability η\eta.

References

  1. [1]Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, and Ning Xie. Testing k-wise and almost k-wise independence. In David S. Johnson and Uriel Feige, editors, 39th ACM STOC, pages 496–505. ACM Press, June 2007. 2, 3, 11DOI
  2. [2]Sanjeev Arora, Boaz Barak, Markus Brunnermeier, and Rong Ge. Computational complexity and information asymmetry in financial products. Communications of the ACM, 54(5):101–107, 2011. 2, 3, 11DOI
  3. [3]Damiano Abram, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, and Varun Narayanan. Cryptography from planted graphs: Security with logarithmic-size messages. In Guy N. Rothblum and Hoeteck Wee, editors, TCC 2023, Part I, volume 14369 of LNCS, pages 286–315. Springer, Cham, November / December 2023. 2, 3, 6, 11DOI
  4. [4]Benny Applebaum, Andrej Bogdanov, and Alon Rosen. A dichotomy for local small-bias generators. In Ronald Cramer, editor, TCC 2012, volume 7194 of LNCS, pages 600–617. Springer, Berlin, Heidelberg, March 2012. 6
  5. [5]Benny Applebaum, Boaz Barak, and Avi Wigderson. Public-key cryptography from different assumptions. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 171–180, 2010. 2, 3, 4, 5, 6, 7, 10, 11, 30DOI
  6. [6]Benny Applebaum and Eliran Kachlon. Sampling graphs without forbidden subgraphs and unbalanced expanders with negligible error. In David Zuckerman, editor, 60th FOCS, pages 171–179. IEEE Computer Society Press, November 2019. 6
  7. [7]Noga Alon, Michael Krivelevich, and Benny Sudakov. Finding a large hidden clique in a random graph. Random Structures & Algorithms, 13(3-4):457–466, 1998. 2, 3, 11
  8. [8]Benny Applebaum and Shachar Lovett. Algebraic attacks against random local functions and their countermeasures. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 1087–1100, 2016. 6, 12DOI
  9. [9]Michael Alekhnovich. More on average case vs approximation complexity. In 44th FOCS, pages 298–307. IEEE Computer Society Press, October 2003. 2, 3, 5
  10. [10]Sarah R Allen, Ryan O’Donnell, and David Witmer. How to refute a random csp. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 689–708. IEEE, 2015. 3, 4arxiv.org/abs/1505.04383
  11. [11]Benny Applebaum. Pseudorandom generators with long stretch and low locality from random local one-way functions. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 805–816, 2012. 6, 12DOI
  12. [12]Benny Applebaum. Cryptographic hardness of random local functions: Survey. Computational complexity, 25:667–722, 2016. 3, 4, 11, 12
  13. [13]Matthew Brennan and Guy Bresler. Reducibility and statistical-computational gaps from secret leakage. In Conference on Learning Theory, pages 648–847. PMLR, 2020. 2, 3, 11arxiv.org/abs/2005.08099
  14. [14]Matthew Brennan, Guy Bresler, and Wasim Huleihel. Reducibility and computational lower bounds for problems with planted sparse structure. In Conference On Learning Theory, pages 48–166. PMLR, 2018.arxiv.org/abs/1806.07508
  15. [15]Mihir Bellare. The goldreich-levin theorem. 1999.
  16. [16]Avrim Blum, Merrick L. Furst, Michael J. Kearns, and Richard J. Lipton. Cryptographic primitives based on hard learning problems. In Douglas R. Stinson, editor, CRYPTO’93, volume 773 of LNCS, pages 278–291. Springer, Berlin, Heidelberg, August 1994.DOI
  17. [17]Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh K Kothari, Ankur Moitra, and Aaron Potechin. A nearly tight sum-of-squares lower bound for the planted clique problem. SIAM Journal on Computing, 48(2):687–735, 2019.
  18. [18]Andrej Bogdanov, Pravesh K. Kothari, and Alon Rosen. Public-key encryption, local pseudorandom generators, and the low-degree method. In Guy N. Rothblum and Hoeteck Wee, editors, TCC 2023, Part I, volume 14369 of LNCS, pages 268–285. Springer, Cham, November / December 2023.DOI
  19. [19]Boaz Barak and Ankur Moitra. Noisy tensor completion via the sum-of-squares hierarchy. In Conference on Learning Theory, pages 417–445. PMLR, 2016.arxiv.org/abs/1501.06521
  20. [20]Andrej Bogdanov and Youming Qiao. On the security of goldreich’s one-way function. In Irit Dinur, Klaus Jansen, Joseph Naor, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings, volume 5687 of Lecture Notes in Computer Science, pages 392–405. Springer, 2009.
  21. [21]Quentin Berthet and Philippe Rigollet. Complexity theoretic lower bounds for sparse principal component detection. In Conference on learning theory, pages 1046–1066. PMLR, 2013.
  22. [22]Mark Braverman. Polylogarithmic independence fools ac 0 circuits. Journal of the ACM (JACM), 57(5):1–10, 2008.DOI
  23. [23]Boaz Barak and David Steurer. Higher-degree integrality gaps: from computational hardness to limitations of sum-of-squares. Sum-of-squares: proofs, beliefs, and algorithms.
  24. [24]Piotr Berman and Georg Schnitger. On the complexity of approximating the independent set problem. Information and Computation, 96(1):77–94, 1992.
  25. [25]Andrej Bogdanov, Manuel Sabin, and Prashant Nalini Vasudevan. Xor codes and sparse learning parity with noise. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 986–1004. SIAM, 2019.DOI
  26. [26]Geoffroy Couteau, Aurélien Dupin, Pierrick Méaux, Mélissa Rossi, and Yann Rotella. On the concrete security of Goldreich’s pseudorandom generator. In Thomas Peyrin and Steven Galbraith, editors, ASIACRYPT 2018, Part II, volume 11273 of LNCS, pages 96–124. Springer, Cham, December 2018.DOI
  27. [27]James Cook, Omid Etesami, Rachel Miller, and Luca Trevisan. Goldreich’s one-way function candidate and myopic backtracking algorithms. In Omer Reingold, editor, TCC 2009, volume 5444 of LNCS, pages 521–538. Springer, Berlin, Heidelberg, March 2009. ⁶DOI
  28. [28]Caicai Chen and Chris Jones. Key-recovery attack on a public-key encryption related to planted clique. Cryptology ePrint Archive, 2024. ⁶
  29. [30]Zongchen Chen, Elchanan Mossel, and Ilias Zadik. Almost-linear planted cliques elude the metropolis process. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4504–4539. SIAM, 2023. ³
  30. [31]Yael Dekel, Ori Gurel-Gurevich, and Yuval Peres. Finding hidden cliques in linear time with high probability. Combinatorics, Probability and Computing, 23(1):29–49, 2014. ³
  31. [32]Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644–654, 1976. ²
  32. [34]Yash Deshpande and Andrea Montanari. Finding hidden cliques of size n/e n/e in nearly linear time. Foundations of Computational Mathematics, 15:1069–1128, 2015. ³
  33. [35]Reyad Abed Elrazik, Robert Robere, Assaf Schuster, and Gal Yehuda. Pseudorandom self-reductions for NP-complete problems. In Mark Braverman, editor, ITCS 2022, volume 215, pages 65:1–65:12. LIPIcs, January / February 2022. ², ³, ¹¹DOI
  34. [36]Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S Vempala, and Ying Xiao. Statistical algorithms and a lower bound for detecting planted cliques. Journal of the ACM (JACM), 64(2):1–37, 2017. ³
  35. [37]Uriel Feige and Robert Krauthgamer. The probable value of the lovász–schrijver relaxations for maximum independent set. SIAM Journal on Computing, 32(2):345–370, 2003. ³DOI
  36. [38]Uriel Feige, Jeong Han Kim, and Eran Ofek. Witnesses for non-satisfiability of dense random 3CNF formulas. In 47th FOCS, pages 497–508. IEEE Computer Society Press, October 2006. ³, ⁴, ⁵, ¹¹
  37. [39]Vitaly Feldman, Will Perkins, and Santosh Vempala. On the complexity of random satisfiability problems with planted solutions. In Rocco A. Servedio and Ronitt Rubinfeld, editors, 47th ACM STOC, pages 77–86. ACM Press, June 2015. ³, ⁴, ¹¹
  38. [40]Uriel Feige and Dorit Ron. Finding hidden cliques in linear time. Discrete Mathematics & Theoretical Computer Science, (Proceedings), 2010. ³DOI
  39. [41]Oded Goldreich and Leonid A Levin. A hard-core predicate for all one-way functions. In Proceedings of the twenty-first annual ACM symposium on Theory of computing, pages 25–32, 1989.DOI
  40. [42]Oded Goldreich. Candidate one-way functions based on expander graphs. Electron. Colloquium Comput. Complex., TR00-090, 2000.
  41. [43]Oded Goldreich. Candidate one-way functions based on expander graphs. Studies in Complexity and Cryptography, pages 76–87, 2011.
  42. [44]Dima Grigoriev. Linear lower bound on degrees of positivstellensatz calculus proofs for the parity. Theoretical Computer Science, 259(1-2):613–622, 2001.DOI
  43. [45]Elad Hazan and Robert Krauthgamer. How hard is it to approximate the best nash equilibrium? SIAM Journal on Computing, 40(1):79–91, 2011.
  44. [47]Thomas Holenstein and Renato Renner. One-way secret-key agreement and applications to circuit polarization and immunization of public-key encryption. In Victor Shoup, editor, CRYPTO 2005, volume 3621 of LNCS, pages 478–493. Springer, Berlin, Heidelberg, August 2005.DOI
  45. [48]Shuichi Hirahara and Nobutaka Shimizu. Planted clique conjectures are equivalent. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, 56th ACM STOC, pages 358–366. ACM Press, June 2024.DOI
  46. [49]Péter Hudoba. Public key cryptography based on the clique and learning parity with noise problems for post-quantum cryptography. In Proceedings of the 11th Joint Conference on Mathematics and Computer Science, pages 102–112, 2016.
  47. [50]Bruce Hajek, Yihong Wu, and Jiaming Xu. Computational lower bounds for community detection on random graphs. In Conference on Learning Theory, pages 899–928. PMLR, 2015.arxiv.org/abs/1406.6625
  48. [51]Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. Cryptography with constant computational overhead. In Richard E. Ladner and Cynthia Dwork, editors, 40th ACM STOC, pages 433–442. ACM Press, May 2008.DOI
  49. [52]Mark Jerrum. Large cliques elude the metropolis process. Random Structures & Algorithms, 3(4):347–359, 1992.DOI
  50. [53]Ari Juels and Marcus Peinado. Hiding cliques for cryptographic security. Designs, Codes and Cryptography, 20(3):269–280, 2000.DOI
  51. [54]Richard Karp. Probabilistic analysis of some combinatorial search problems. Algorithms and Complexity: New Directions and Recent Results, 1976.
  52. [55]Gyula Katona. A theorem of finite sets. Classic Papers in Combinatorics, pages 381–401, 1987.
  53. [56]Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 45(6):983–1006, 1998.
  54. [57]Nicholas Kocurek and Peter Manohar. Strong refutation of semirandom k-lin over larger fields. 30
  55. [58]Pravesh K. Kothari, Ryuhei Mori, Ryan O’Donnell, and David Witmer. Sum of squares lower bounds for refuting any CSP. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, 49th ACM STOC, pages 132–145. ACM Press, June 2017. 3, 4, 6, 11arxiv.org/abs/1701.04521
  56. [59]Joseph B Kruskal. The number of simplices in a complex. Mathematical optimization techniques, 10:251–278, 1963. 20, 21DOI
  57. [60]Luděk Kučera. Expected complexity of graph partitioning problems. Discrete Applied Mathematics, 57(2-3):193–212, 1995. 2, 3, 11DOI
  58. [61]Pascal Koiran and Anastasios Zou zias. Hidden cliques and the certification of the restricted isometry property. IEEE transactions on information theory, 60(8):4999–5006, 2014. 3, 11arxiv.org/abs/1211.0665
  59. [62]Jean B Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on optimization, 11(3):796–817, 2001. 2DOI
  60. [64]Elchanan Mossel, Amir Shpilka, and Luca Trevisan. On e-biased generators in NC0. In 44th FOCS, pages 136–145. IEEE Computer Society Press, October 2003. 6
  61. [65]Zongming Ma and Yihong Wu. Computational barriers in minimax submatrix detection. 2015. 3, 11DOI
  62. [66]Yurii Nesterov. Squared Functional Systems and Optimization Problems, pages 405–440. Springer US, Boston, MA, 2000. 2
  63. [67]Noam Nisan. Pseudorandom bits for constant depth circuits. Combinatorica, 11:63–70, 1991. 5DOI
  64. [68]Igor C Oliveira, Rahul Santhanam, and Roei Tell. Expander-based cryptography meets natural proofs. 10th Innovations in Theoretical Computer Science, 2019. 5
  65. [69]Ryan O’Donnell and David Witmer. Goldreich’s PRG: evidence for near-optimal polynomial stretch. In IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11-13, 2014, pages 1–12. IEEE Computer Society, 2014. 6DOI
  66. [70]Pablo A Parrilo. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. California Institute of Technology, 2000. 2DOI
  67. [71]Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Harold N. Gabow and Ronald Fagin, editors, 37th ACM STOC, pages 84–93. ACM Press, May 2005. 2
  68. [72]Benjamin Rossman. On the constant-depth complexity of k-clique. In Richard E. Ladner and Cynthia Dwork, editors, 40th ACM STOC, pages 721–730. ACM Press, May 2008. 3DOI
  69. [73]Prasad Raghavendra, Satish Rao, and Tselil Schramm. Strongly refuting random CSPs below the spectral threshold. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, 49th ACM STOC, pages 121–131. ACM Press, June 2017. 3, 4, 11arxiv.org/abs/1605.00058
  70. [74]Ronald L. Rivest, Adi Shamir, and Leonard Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120–126, 1978. 2
  71. [75]Grant Schoenebeck. Linear level lasserre lower bounds for certain k-csps. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 593–602. IEEE, 2008. 3, 4, 11, 30
  72. [76]Naum Z. Shor. Minimization methods for non-differentiable functions and applications. Cybernetics, 13(1):94–96, 1985. 2DOI

Paper details

vlnc:W_e4wkvzfr
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents