It is well known that the hardest bit of integer multiplication is the middle bit, i.e. MUL_{n-1,n}.
This paper contains several new results on its complexity.
First, the size s of randomized read-k branching programs, or, equivalently, its space (log s) is investigated.
A randomized algorithm for MUL_{n-1,n} with k=O(log ... more >>>

We prove that every disjoint NP-pair is polynomial-time, many-one equivalent to
the canonical disjoint NP-pair of some propositional proof system. Therefore, the degree structure of the class of disjoint NP-pairs and of all canonical pairs is
identical. Secondly, we show that this degree structure is not superficial: Assuming there exist ... more >>>

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 >>>