The Monotone Complexity of $k$-Clique on Random Graphs
From MaRDI portal
Publication:5419039
DOI10.1137/110839059zbMath1304.68081OpenAlexW2159233562MaRDI QIDQ5419039
Publication date: 4 June 2014
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/110839059
Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items
Tensor clustering with planted structures: statistical optimality and computational limits ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting) ⋮ Unnamed Item ⋮ Cliques enumeration and tree-like resolution proofs ⋮ Coding for Sunflowers ⋮ Beating treewidth for average-case subgraph isomorphism ⋮ Improved bounds for the sunflower lemma ⋮ Improved bounds for quantified derandomization of constant-depth circuits and polynomials ⋮ Unnamed Item ⋮ Monotone circuit lower bounds from robust sunflowers ⋮ On the average-case complexity of parameterized clique
