Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

Division in logspace-uniform NC 1

Andrew Chiu;  George Davida;  Bruce Litow — 2001

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Beame, Cook and Hoover were the first to exhibit a log-depth, polynomial size circuit family for integer division. However, the family was not logspace-uniform. In this paper we describe log-depth, polynomial size, logspace-uniform, i.e., NC 1 circuit family for integer division. In particular, by a well-known result this shows that division is in logspace. We also refine the method of the paper to show that division is in dlogtime-uniform NC 1 .

Division in logspace-uniform

Andrew Chiu;  George Davida;  Bruce Litow — 2010

RAIRO - Theoretical Informatics and Applications

Beame, Cook and Hoover were the first to exhibit a log-depth, polynomial size circuit family for integer division. However, the family was not logspace-uniform. In this paper we describe log-depth, polynomial size, logspace-uniform, , circuit family for integer division. In particular, by a well-known result this shows that division is in logspace. We also refine the method of the paper to show that division is in dlogtime-uniform .

Page 1

Download Results (CSV)