View source for Exact k-Clique Hypothesis

== Target Problem == 

[[Exact $k$-Clique]]

== Description == 

The Exact $k$-Clique problem on $n$ node graphs with edge weights in $\{-n^{100k},\ldots,n^{100k}\}$ requires (randomized) $n^{k-o(1)}$ time.

== Implies the following Hypothesis == 

[[Orthogonal Vectors Hypothesis (OVH)|OVH]]

== Implied by the following Hypothesis == 



== Computation Model == 

Word-Ram on $\log(n)$ bit words

== Proven? == 

No

== Year == 



== References/Citation == 

http://people.csail.mit.edu/virgi/eccentri.pdf Hypothesis 8