It is known that several sub-universal quantum computing models, such as the IQP model, the Boson sampling model, the one-clean qubit model, and the random circuit model, cannot be classically simulated in polynomial time under certain conjectures...
The planar Hajos calculus is the Hajos calculus with the restriction that all the graphs that appear in the construction (including a final graph) must be planar. We prove that the planar Hajos calculus is polynomially bounded iff the Hajos calcul...
Recently, [Iwama, Tamaki, SODA04] gave a new worst-case upper bound for 3SAT by modifying the PPSZ-type algorithm in [Paturi et. al., FOCS98] by making use of the local-search-type one in [Schoning, Algorithmica 02]. We propose a different kind of...