Minimizing DNF Formulas and AC^0_d Circuits Given a Truth Table

Prague, Czech Republic July 16-July 20

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/CCC.2006.27

21st Annual IEEE Conference on Compu ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Eric Allender Articles by Lisa Hellerstein Articles by Paul McCabe Articles by Toniann Pitassi Articles by Michael Saks

	ASCII Text	x
	Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael Saks, "Minimizing DNF Formulas and AC^0_d Circuits Given a Truth Table," Computational Complexity, Annual IEEE Conference on, pp. 237-251, 21st Annual IEEE Conference on Computational Complexity (CCC'06), 2006.

	BibTex	x
	@article{ 10.1109/CCC.2006.27, author = {Eric Allender and Lisa Hellerstein and Paul McCabe and Toniann Pitassi and Michael Saks}, title = {Minimizing DNF Formulas and AC^0_d Circuits Given a Truth Table}, journal ={Computational Complexity, Annual IEEE Conference on}, volume = {0}, year = {2006}, issn = {1093-0159}, pages = {237-251}, doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2006.27}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Computational Complexity, Annual IEEE Conference on TI - Minimizing DNF Formulas and AC^0_d Circuits Given a Truth Table SN - 1093-0159 SP237 EP251 A1 - Eric Allender, A1 - Lisa Hellerstein, A1 - Paul McCabe, A1 - Toniann Pitassi, A1 - Michael Saks, PY - 2006 KW - null VL - 0 JA - Computational Complexity, Annual IEEE Conference on ER -

Eric Allender, Rutgers University, USA

Lisa Hellerstein, Polytechnic University, USA

Paul McCabe, University of Toronto, Canada

Toniann Pitassi, University of Toronto, Canada

Michael Saks, Rutgers University, USA

For circuit classes R, the fundamental computational problem Min-R asks for the minimum R-size of a Boolean function presented as a truth table. Prominent examples of this problem include Min-DNF, which asks whether a given Boolean function presented as a truth table has a k-term DNF, and Min-Circuit (also called MCSP), which asks whether a Boolean function presented as a truth table has a size k Boolean circuit. We present a new reduction proving that Min-DNF is NP-complete. It is significantly simpler than the known reduction of Masek [31], which is from Circuit-SAT.

Citation:

Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael Saks, "Minimizing DNF Formulas and AC^0_d Circuits Given a Truth Table," ccc, pp.237-251, 21st Annual IEEE Conference on Computational Complexity (CCC'06), 2006

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.