A Simple Algorithm for Hamiltonicity

Original · EN

We develop a new algebraic technique that solves the following problem: Given a black box that contains an arithmetic circuit f over a field of characteristic 2 of degree d. Decide whether f, expressed as an equivalent multivariate polynomial, contains a multilinear monomial of degree d. This problem was solved by Williams W and Björklund et. al. BHKK for a white box (the circuit is given as an input) that contains arithmetic circuit. We show a simple black box algorithm that solves the problem with the same time complexity. This gives a simple randomized algorithm for the simple k-path problem for directed graphs of the same time complexityO*(f(k)) is O(poly(n)· f(k)) O*(2ᵏ) as in W and with reusing the same ideas from BHKK with the above gives another algorithm (probably not simpler) for undirected graphs of the same time complexity O*(1.657ᵏ) as in B10,BHKK.