Triangle Detection Conjecture
Statement
Let be an input graph with vertices and edges. An algorithm runs in the word RAM model with word size bits. Triangle Detection Conjecture. There exists such that any algorithm to decide whether is triangle-free requires time in expectation. This is a standard fine-grained hardness assumption for triangle detection and is used as the foundation for complexity-theoretic lower bounds on subgraph counting in bounded-degeneracy graphs.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.