The Monotone Complexity of $k$-Clique on Random Graphs

DOI10.1137/110839059zbMath1304.68081OpenAlexW2159233562MaRDI QIDQ5419039

Benjamin Rossman

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

zbMATH Keywords

random graphscliqueaverage-case complexitymonotone circuitquasi-sunflowers

Mathematics Subject Classification ID

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 (12)

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

This page was built for publication: The Monotone Complexity of $k$-Clique on Random Graphs