We present a top-down lower-bound method for depth-4 boolean circuits. I...
We prove two results about randomised query complexity R(f).
First, we i...
The Collision problem is to decide whether a given list of numbers
(x_1,...
It is well-known that Resolution proofs can be efficiently simulated by
...
We survey lower-bound results in complexity theory that have been obtain...
We show =∩. Here the class
consists of all total search problems that r...
We use results from communication complexity, both new and old ones, to ...
We exhibit an unambiguous k-DNF formula that requires CNF width
Ω̃(k^2),...
The Stabbing Planes proof system was introduced to model the reasoning
c...
Suppose we have randomized decision trees for an outer function f and an...
We show that Cutting Planes (CP) proofs are hard to find: Given an
unsat...
The randomized query complexity R(f) of a boolean function
f{0,1}^n→{0,1...
We study the search problem class PPA_q defined as a modulo-q
analog of ...
We prove an N^2-o(1) lower bound on the randomized communication
complex...