zbMATH — the first resource for mathematics

On the complexity of random satisfiability problems with planted solutions. (English) Zbl 1396.68057

68Q25 Analysis of algorithms and problem complexity
05C65 Hypergraphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C80 Random graphs (graph-theoretic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Full Text: DOI
[1] E. Abbe, A. S. Bandeira, A. Bracher, and A. Singer, Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery, IEEE Trans. Network Sci. Eng., 1 (2014), pp. 10–22.
[2] E. Abbe and A. Montanari, Conditional random fields, planted constraint satisfaction, and entropy concentration, Theory Comput., 11 (2015), pp. 413–443. · Zbl 1351.68190
[3] D. Achlioptas and A. Coja-Oghlan, Algorithmic barriers from phase transitions, in Proceedings of the IEEE Symposium on Foundations of Computer Science, 2008, pp. 793–802.
[4] D. Achlioptas, H. Jia, and C. Moore, Hiding satisfying assignments: Two are better than one, J. Artificial Intelligence Res., 24 (2005), pp. 623–639. · Zbl 1080.68653
[5] M. Alekhnovich, More on average case vs approximation complexity, Comput. Complexity, 20 (2011), pp. 755–786. · Zbl 1242.68109
[6] S. R. Allen, R. O’Donnell, and D. Witmer, How to refute a random CSP, in Proceedings of the IEEE Symposium on Foundations of Computer Science, 2015, pp. 689–708, .
[7] N. Alon and J. H. Spencer, The Probabilistic Method, 3rd ed., John Wiley & Sons, New York, 2011. · Zbl 1333.05001
[8] B. Applebaum, Pseudorandom generators with long stretch and low locality from random local one-way functions, SIAM J. Comput., 42 (2013), pp. 2008–2037. · Zbl 1317.94081
[9] B. Applebaum, Cryptographic hardness of random local functions, Comput. Complexity, 25 (2016), pp. 667–722. · Zbl 1360.94293
[10] B. Applebaum, B. Barak, and A. Wigderson, Public-key cryptography from different assumptions, in Proceedings of the ACM Symposium on Theory of Computing, 2010, pp. 171–180. · Zbl 1293.94052
[11] B. Applebaum, A. Bogdanov, and A. Rosen, A dichotomy for local small-bias generators, in Theory of Cryptography, R. Cramer, ed., Springer, New York, 2012, pp. 600–617. · Zbl 1304.68041
[12] B. Applebaum and S. Lovett, Algebraic attacks against random local functions and their countermeasures, in Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, 2016, pp. 1087–1100. · Zbl 1377.94027
[13] P. Austrin and E. Mossel, Approximation resistant predicates from pairwise independence, Comput. Complexity, 18 (2009), pp. 249–271. · Zbl 1214.68172
[14] M. Balcan and V. Feldman, Statistical active learning algorithms for noise tolerance and differential privacy, Algorithmica, 72 (2015), pp. 282–315. · Zbl 1315.68202
[15] B. Barak, G. Kindler, and D. Steurer, On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction, in Proceedings of the ACM Conference on Innovations in Theoretical Computer Science, 2013, pp. 197–214. · Zbl 1361.68104
[16] W. Barthel, A. K. Hartmann, M. Leone, F. Ricci-Tersenghi, M. Weigt, and R. Zecchina, Hiding solutions in random satisfiability problems: A statistical mechanics approach, Phys. Rev. Lett., 88 (2002), 188701.
[17] W. Beckner, Inequalities in Fourier analysis, Ann. of Math., 102 (1975), pp. 159–182. · Zbl 0338.42017
[18] S. Ben-David and E. Dichterman, Learning with restricted focus of attention, J. Comput. System Sci., 56 (1998), pp. 277–298. · Zbl 0945.68531
[19] J. Blocki, M. Blum, A. Datta, and S. Vempala, Towards Human Computable Passwords, preprint, [cs.CR], 2014. · Zbl 1402.94073
[20] A. Blum, C. Dwork, F. McSherry, and K. Nissim, Practical privacy: The SuLQ framework, in Proceedings of the Symposium on Principles of Database Systems, 2005, pp. 128–138.
[21] A. Blum, A. Frieze, R. Kannan, and S. Vempala, A polynomial-time algorithm for learning noisy linear threshold functions, Algorithmica, 22 (1998), pp. 35–52. · Zbl 0910.68169
[22] A. Blum, M. Furst, J. Jackson, M. Kearns, Y. Mansour, and S. Rudich, Weakly learning DNF and characterizing statistical query learning using Fourier analysis, in Proceedings of the ACM Symposium on Theory of Computing, 1994, pp. 253–262. · Zbl 1345.68186
[23] A. Bogdanov and Y. Qiao, On the security of Goldreich’s one-way function, in Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, I. Dinur, K. Jansen, S. Naor, and J. Rolim, eds. Springer-Verlag, Berlin, 2009, pp. 392–405. · Zbl 1255.94053
[24] A. Bonami, Étude des coefficients de Fourier des fonctions de \(l_ p (g) \), Ann. Inst. Fourier (Grenoble), 20 (1970), pp. 335–402. · Zbl 0195.42501
[25] R. B. Boppana, Eigenvalues and graph bisection: An average-case analysis, in Proceedings of the IEEE Symposium on Foundations of Computer Science, 1987, pp. 280–285.
[26] M. Charikar and A. Wirth, Maximizing quadratic programs: Extending Grothendieck’s inequality, in Proceedings of the IEEE Symposium on Foundations of Computer Science, 2004, pp. 54–60.
[27] C.-T. Chu, S. K. Kim, Y.-A. Lin, Y. Yu, G. Bradski, A. Y. Ng, and K. Olukotun, Map-reduce for machine learning on multicore, in Proceedings of the Conference on Neural Information Processing Systems, 2006, pp. 281–288.
[28] A. Coja-Oghlan, A spectral heuristic for bisecting random graphs, Random Structures Algorithms, 29 (2006), pp. 351–398. · Zbl 1111.05088
[29] A. Coja-Oghlan, C. Cooper, and A. Frieze, An efficient sparse regularity concept, SIAM J. Discrete Math., 23 (2010), pp. 2000–2034. · Zbl 1207.05195
[30] A. Coja-Oghlan, A. Goerdt, and A. Lanka, Strong refutation heuristics for random k-SAT, in Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, K. Jansen, S. Khanna, J. D. P. Rolim, and D. Ron, eds., Springer-Verlag, Berlin, 2004, pp. 310–321. · Zbl 1105.68423
[31] A. Coja-Oghlan, A. Goerdt, A. Lanka, and F. Schädlich, Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2k-SAT, Theoret. Comput. Sci., 329 (2004), pp. 1–45. · Zbl 1086.68143
[32] J. Cook, O. Etesami, R. Miller, and L. Trevisan, Goldreich’s one-way function candidate and myopic backtracking algorithms, in Theory of Cryptography, Springer, New York, 2009, pp. 521–538. · Zbl 1213.94092
[33] A. Daniely, N. Linial, and S. Shalev-Shwartz, More data speeds up training time in learning halfspaces over sparse vectors, in Proceedings of the Conference on Neural Information Processing Systems, 2013, pp. 145–153.
[34] A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová, Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications, Phys. Rev., 84 (2011), 066106.
[35] A. Dempster, N. Laird, and D. Rubin, Maximum likelihood from incomplete data via the em algorithm, J. R. Stat. Soc. Ser. B. Stat. Mathodol., 39 (1977), pp. 1–38. · Zbl 0364.62022
[36] I. Dinur, E. Friedgut, G. Kindler, and R. O’Donnell, On the Fourier tails of bounded functions over the discrete cube, Israel J. Math., 160 (2007), pp. 389–412. · Zbl 1268.43003
[37] J. Dunagan and S. Vempala, A simple polynomial-time rescaling algorithm for solving linear programs, Math. Program., 114 (2008), pp. 101–114. · Zbl 1157.90007
[38] U. Feige, Relations between average case complexity and approximation complexity, in Proceedings of the ACM Symposium on Theory of Computing, 2002, pp. 534–543. · Zbl 1192.68358
[39] U. Feige and E. Ofek, Easily refutable subformulas of large random 3-CNF formulas, in Automata, Languages and Programming, G. Ausiello, M. Dezani-Ciancaglini, and S. Ronchi Della Rocca, eds., Springer-Verlag, Berlin, 2004, pp. 519–530. · Zbl 1099.68641
[40] V. Feldman, A complete characterization of statistical query learning with applications to evolvability, J. Comput. System Sci., 78 (2012), pp. 1444–1459. · Zbl 1244.68045
[41] V. Feldman, A General Characterization of the Statistical Query Complexity, preprint, [cs.LG], 2016.
[42] V. Feldman, Statistical query learning, in Encyclopedia of Algorithms, M.-Y. Kao, ed., Springer, New York, 2017, pp. 2090–2095.
[43] V. Feldman, E. Grigorescu, L. Reyzin, S. S. Vempala, and Y. Xiao, Statistical algorithms and a lower bound for detecting planted cliques, J. ACM, 64 (2017), pp. 8:1–8:37. · Zbl 1397.68085
[44] V. Feldman, C. Guzman, and S. Vempala, Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization, preprint, [cs.LG], 2015. · Zbl 1422.90031
[45] V. Feldman, W. Perkins, and S. Vempala, On the Complexity of Random Satisfiability Problems with Planted Solutions, preprint, [cs.CC], 2013. · Zbl 1321.68280
[46] V. Feldman, W. Perkins, and S. Vempala, Subsampled Power Iteration: A New Algorithm for Block Models and Planted CSP’s, preprint, [cs.DS], 2014.
[47] A. Flaxman, A spectral technique for random satisfiable 3cnf formulas, in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2003, pp. 357–363. · Zbl 1094.68574
[48] J. Friedman, A. Goerdt, and M. Krivelevich, Recognizing more unsatisfiable random k-SAT instances efficiently, SIAM J. Comput., 35 (2005), pp. 408–430. · Zbl 1090.05064
[49] D. Gamarnik and M. Sudan, Performance of the Survey Propagation-Guided Decimation Algorithm for the Random NAE-K-SAT Problem, preprint, [math.PR], 2014. · Zbl 1388.60037
[50] A. E. Gelfand and A. F. Smith, Sampling based approaches to calculating marginal densities, J. Amer. Statist. Assoc., 85 (1990), pp. 398–409. · Zbl 0702.62020
[51] M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42 (1995), pp. 1115–1145. · Zbl 0885.68088
[52] A. Goerdt and A. Lanka, Recognizing more random unsatisfiable 3-SAT instances efficiently, Electron. Notes Discrete Math., 16 (2003), pp. 21–46. · Zbl 1179.68143
[53] O. Goldreich, Candidate one-way functions based on expander graphs, preprint, ia.cr/2000/063,2000.
[54] H. Hàn, Y. Person, and M. Schacht, Note on strong refutation algorithms for random k-SAT formulas, Electron. Notes Discrete Math., 35 (2009), pp. 157–162. · Zbl 1268.68085
[55] L. P. Hansen, Large sample properties of generalized method of moments estimators, Econometrica, 50 (2012), pp. 1029–1054. · Zbl 0502.62098
[56] Y. Ishai, E. Kushilevitz, R. Ostrovsky, and A. Sahai, Cryptography with constant computational overhead, in Proceedings of the ACM Symposium on Theory of Computing, 2008, pp. 433–442. · Zbl 1231.94050
[57] S. Janson, Gaussian Hilbert Spaces, Cambridge University Press, Cambridge, 1997. · Zbl 0887.60009
[58] H. Jia, C. Moore, and D. Strain, Generating hard satisfiable formulas by hiding solutions deceptively, J. Artificial Intelligence Res., 28 (2007), pp. 107–118. · Zbl 1182.68249
[59] A. T. Kalai and S. Vempala, Simulated annealing for convex optimization, Oper. Res., 31 (2006), pp. 253–266. · Zbl 1278.90311
[60] M. Kearns, Efficient noise-tolerant learning from statistical queries, J. ACM, 45 (1998), pp. 983–1006. · Zbl 1065.68605
[61] S. Kirkpatrick, C. D. Gelatt, Jr., and M. P. Vecchi, Optimization by simulated annealing, Science, 220 (1983), pp. 671–680. · Zbl 1225.90162
[62] P. K. Kothari, R. Meka, and P. Raghavendra, Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPS, in Proceedings of the ACM Symposium on Theory of Computing, 2017, pp. 590–603. · Zbl 1370.68133
[63] M. Krivelevich and D. Vilenchik, Solving random satisfiable 3cnf formulas in expected polynomial time, in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2006, pp. 454–463. · Zbl 1192.68370
[64] F. Krzakala, M. Mézard, and L. Zdeborová, Reweighted belief propagation and quiet planting for random k-SAT, J. Satisf., Boolean Model. Comput., 8 (2014), pp. 149–171. · Zbl 1322.68182
[65] F. Krzakała, A. Montanari, F. Ricci-Tersenghi, G. Semerjian, and L. Zdeborová, Gibbs states and the set of solutions of random constraint satisfaction problems, Proc. Natl. Acad. Sci. USA, 104 (2007), pp. 10318–10323. · Zbl 1190.68031
[66] F. Krzakala and L. Zdeborová, Hiding quiet solutions in random constraint satisfaction problems, Phys. Rev. Lett., 102 (2009), 238701.
[67] A. Levin, On an algorithm for the minimization of convex functions, Dokl. Akad. Nauk, 6 (1965), pp. 268–290. · Zbl 0154.45001
[68] L. Lovász and S. Vempala, Fast algorithms for logconcave functions: Sampling, rounding, integration and optimization, in Proceedings of the IEEE Symposium on Foundations of Computer Science, 2006, pp. 57–68.
[69] R. Marino, G. Parisi, and F. Ricci-Tersenghi, The backtracking survey propagation algorithm for solving random k-SAT problems, Nature Communications, 7 (2016), 12996.
[70] L. Massoulié, Community detection thresholds and the weak Ramanujan property, in Proceedings of the ACM Symposium on Theory of Computing, 2014, pp. 1–10.
[71] F. McSherry, Spectral partitioning of random graphs, in Proceedings of the IEEE Symposium on Foundations of Computer Science, 2001, pp. 529–537.
[72] E. Mossel, J. Neeman, and A. Sly, A Proof of the Block Model Threshold Conjecture, preprint, , 2013. · Zbl 1424.05272
[73] E. Mossel, J. Neeman, and A. Sly, Reconstruction and estimation in the planted partition model, Probab. Theory Related Fields, 162 (2015), pp. 431–461. · Zbl 1320.05113
[74] E. Mossel, A. Shpilka, and L. Trevisan, On \(ε\)-biased generators in NC0, Random Structures Algorithms, 29 (2006), pp. 56–81. · Zbl 1102.68024
[75] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro, Robust stochastic approximation approach to stochastic programming, SIAM J. Optim., 19 (2009), pp. 1574–1609. · Zbl 1189.90109
[76] A. Nemirovsky and D. Yudin, Problem Complexity and Method Efficiency in Optimization, John Wiley and Sons, New York, 1983.
[77] R. O’Donnell, Constraint Satisfaction Problems, notes from lecture 13 of a course on linear and semidefinite programming, Carnegie Mellon University, 2011, .
[78] R. O’Donnell and D. Witmer, Goldreich’s PRG: Evidence for near-optimal polynomial stretch, in Proceedings of Conference on Computational Complexity, 2014.
[79] P. Raghavendra, Optimal algorithms and inapproximability results for every CSP?, in Proceedings of the ACM Symposium on Theory of Computing, 2008, pp. 245–254. · Zbl 1231.68142
[80] S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan, Stochastic convex optimization, in Proceedings of the Conference on Learning Theory, 2009.
[81] J. Steinhardt and J. C. Duchi, Minimax rates for memory-bounded sparse linear regression, in Proceedings of the Conference on Learning Theory, 2015, pp. 1564–1587 .
[82] J. Steinhardt, G. Valiant, and S. Wager, Memory, communication, and statistical queries, Technical Report TR15-126, , 2015.
[83] M. A. Tanner and W. H. Wong, The calculation of posterior distributions by data augmentation (with discussion), J. Amer. Statist. Assoc., 82 (1987), pp. 528–550. · Zbl 0619.62029
[84] L. Trevisan, Checking the Quasirandomness of Graphs and Hypergraphs, February 2008, .
[85] V. Černý, Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm, J. Optim. Theory Appl., 45 (1985), pp. 41–51. · Zbl 0534.90091
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.