Low-depth witnesses are easy to find

• Type: Article in International Conference Proceedings Book
• Date: 2007

Authors

antunes, l (Author) FCUP; fortnow, l (Author) Other; pinto, a (Author) Other; souto, a (Author) Other

Conference proceedings International

Title: ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY

Pages: 46-51

22nd Annual IEEE Conference on Computational Complexity

San Diego, CA, JUN 13-16, 2007

Indexing

ISI Web of Knowledge - 0 Citations

Scopus - 3 Citations

Other information

Authenticus ID: P-004-ERF

DOI: 10.1109/ccc.2007.13

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 6