Hiding cliques for cryptographic security
From MaRDI portal
Publication:1581792
DOI10.1023/A:1008374125234zbMath0965.94015OpenAlexW3139080059MaRDI QIDQ1581792
Publication date: 5 August 2001
Published in: Designs, Codes and Cryptography (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1023/a:1008374125234
combinatorial optimizationrandom graphscliquesone-way functioncryptographic primitivegraph-based cryptosystems
Random graphs (graph-theoretic aspects) (05C80) Cryptography (94A60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Optimal detection of sparse principal components in high dimension, The Ehrenfeucht-Fraïssé Method and the Planted Clique Conjecture, Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation, Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers, A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem, The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs, Finding Hidden Cliques in Linear Time with High Probability, On the hardness of designing public signals, Perfect Structure on the Edge of Chaos, Finding a planted clique by adaptive probing, Convex optimization for the densest subgraph and densest submatrix problems, The Complexity of Public-Key Cryptography, Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning, Computational barriers in minimax submatrix detection