Low-Depth Witnesses are Easy to Find

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Luis Antunes Articles by Lance Fortnow Articles by Alexandre Pinto Articles by Andre Souto

Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07)

San Diego, California

June 13-March 16

ISBN: 0-7695-2780-9

	ASCII Text	x
	Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto, "Low-Depth Witnesses are Easy to Find," Computational Complexity, Annual IEEE Conference on, pp. 46-51, Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), 2007.

	BibTex	x
	@article{ 10.1109/CCC.2007.13, author = {Luis Antunes and Lance Fortnow and Alexandre Pinto and Andre Souto}, title = {Low-Depth Witnesses are Easy to Find}, journal ={Computational Complexity, Annual IEEE Conference on}, volume = {0}, year = {2007}, issn = {1093-0159}, pages = {46-51}, doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2007.13}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Computational Complexity, Annual IEEE Conference on TI - Low-Depth Witnesses are Easy to Find SN - 1093-0159 SP46 EP51 A1 - Luis Antunes, A1 - Lance Fortnow, A1 - Alexandre Pinto, A1 - Andre Souto, PY - 2007 KW - null VL - 0 JA - Computational Complexity, Annual IEEE Conference on ER -

Luis Antunes, U. Porto

Lance Fortnow, U. Chicago

Alexandre Pinto, U. Porto

Andre Souto, U. Porto

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2007.13

Antunes, Fortnow, van Melkebeek and Vinodchandran captured the notion of non-random information by computational depth, the difference between the polynomial-time- bounded Kolmogorov complexity and traditional Kolmogorov complexity. We show unconditionally how to probabilistically find satisfying assignments for formulas that have at least one assignment of logarithmic depth. The converse holds under a standard hardness assumption though fails if BPP = FewP = EXP.

We also show that assuming good pseudorandom generators one cannot increase the depth of a string efficiently.

Citation:

Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto, "Low-Depth Witnesses are Easy to Find," ccc, pp.46-51, Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), 2007

Peer Review Notice | Give Us Feedback

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