wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

hyperclique_hypothesis (354B)

      1 # Hyperclique hypothesis
      2 
      3 Defined in [bringmann2022unbalanced]
      4 
      5 For any k >= 3, detecting a k-[hyperclique] in a (k-1)-[uniform_hypergraph] cannot be done in O(n^{k-1})
      6 
      7 - implies in particular [triangle_detection_conjecture]: you cannot detect triangles in O(n^2) in graphs
      8 
      9 Up: [hypergraph]
     10 
     11 Aliases: hyperclique conjecture
     12 
     13 See also: [clique_problem]