Home > Harvy Mudd College Alumnus Buchfuhrer (2006) wins Best Paper at ICALP, Extraordinary Honor

Harvy Mudd College Alumnus Buchfuhrer (2006) wins Best Paper at ICALP, Extraordinary Honor

Date: 
July 2008

HMC Professor Robert Keller reports that David Buchfuhrer (HMC class of 2006, Math-CS Joint Major) has received an extraordinary academic honor. His paper "The Complexity of Boolean Formula Minimization" with his graduate adviser, Prof. Chris Umans, received the Best Paper Award at ICALP (International Colloquium on Automata, Languages, and Programming) last week in Reykjavik, Iceland. ICALP is the very prestigious conference running for 35 years; Buchfuhrer and Umans's paper resolves a famous open problem that has been open for roughly 30 years!

The problem in a nutshell is as follows: Given a boolean circuit (a circuit with AND, OR, and NOT gates); find the smallest boolean circuit (one with the fewest gates) that is logically equivalent (computes the same function). The problem, which has practical applications in logic synthesis, was conjectured to be "even harder" than NP-complete (specifically, $ \Sigma_{2}^{P} $-complete, where $ \Sigma_{2}^{P} $ is the second level in the polynomial hierarchy) and appeared as an important open problem in the famous book of Garey and Johnson in 1979. While the hardness was resolved for a few special cases over the years, the problem remained open until David and Chris' paper proved, in one fell swoop, that the problem is indeed $ \Sigma_{2}^{P} $-complete in general!

David Buchfuhrer is currently a Ph.D. student in computer science at Caltech where he is working under the supervision of Professor Chris Umans.