Low-Depth Witnesses are Easy to Find

• Type: Article in International Scientific Journal
• Date: 2012

Authors

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

Journal

Title: Computational Complexity

Vol. 21

Pages: 479-497

ISSN: 1016-3328

Publisher: Springer Nature

Indexing

ISI Web of Knowledge - 1 Citation

Scopus - 1 Citation

Other information

Authenticus ID: P-002-67X

DOI: 10.1007/s00037-011-0025-1

Abstract (EN): Kolmogorov Complexity measures the amount of information in a string by the size of the smallest program that generates that string. Antunes, Fortnow, van Melkebeek, and Vinodchandran captured the notion of useful 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 prove that assuming the existence of good pseudorandom generators one cannot increase the depth of a string efficiently.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 19