A property tester with high probability accepts inputs satisfying a given property and rejects
inputs that are far from satisfying it. A tolerant property tester, as defined by Parnas, Ron
and Rubinfeld, must also accept inputs that are close enough to satisfying the property. We
construct properties of binary functions ... more >>>

Effective fractal dimension was defined by Lutz (2003) in order to quantitatively analyze the structure of complexity classes.
Interesting connections of effective dimension with information theory were also found, in fact the cases of polynomial-space and constructive dimension can be precisely characterized in terms of Kolmogorov complexity, while analogous ... more >>>

We prove a new equivalence between the non-uniform and uniform complexity of exponential time. We show that EXP in NP/log if and only if EXP = P^NP|| (polynomial time with non-adaptive queries to SAT). Our equivalence makes use of a recent result due to Shaltiel and Umans showing EXP in ... more >>>