7 citations · 7 across the 6 of their papers we have counts for
6 papers
An Approach to Circuit Lower Bounds via Bounded Width Circuits
Hiroki Morizumi
In this paper, we investigate an approach to circuit lower bounds via bounded width circuits. The approach consists of two steps: (i) We convert circuits to (deterministic or nonde…
Computation with Large Advice
Hiroki Morizumi
In this paper, we consider a new direction of computation, which we call computation with large advice. We mainly consider constant space computation with large advice in Turing ma…
Some Results on the Circuit Complexity of Bounded Width Circuits and Nondeterministic Circuits
Hiroki Morizumi
In this paper, we consider bounded width circuits and nondeterministic circuits in three somewhat new directions. In the first part of this paper, we mainly consider bounded width…
Zero-Suppressed Computation: A New Computation Inspired by ZDDs
Hiroki Morizumi
Zero-suppressed binary decision diagrams (ZDDs) are a data structure representing Boolean functions, and one of the most successful variants of binary decision diagrams (BDDs). On…
Lower Bounds for the Size of Nondeterministic Circuits
Hiroki Morizumi
Nondeterministic circuits are a nondeterministic computation model in circuit complexity theory. In this paper, we prove a lower bound for the size of nondeterministic $U_…
A Note on the Inversion Complexity of Boolean Functions in Boolean Formulas
Hiroki Morizumi
In this note, we consider the minimum number of NOT operators in a Boolean formula representing a Boolean function. In circuit complexity theory, the minimum number of NOT gates in…