research
∙
04/05/2023
Top-Down Lower Bounds for Depth-Four Circuits
We present a top-down lower-bound method for depth-4 boolean circuits. I...
share
research
∙
08/26/2022
Randomised Composition and Small-Bias Minimax
We prove two results about randomised query complexity R(f). First, we i...
research
∙
07/29/2022
Communication Complexity of Collision
The Collision problem is to decide whether a given list of numbers (x_1,...
research
∙
05/04/2022
Separations in Proof Complexity and TFNP
It is well-known that Resolution proofs can be efficiently simulated by ...
research
∙
02/17/2022
Proofs, Circuits, and Communication
We survey lower-bound results in complexity theory that have been obtain...
research
∙
02/15/2022
Further Collapses in TFNP
We show =∩. Here the class consists of all total search problems that r...
research
∙
09/19/2021
Lower Bounds on Unambiguous Automata Complementation and Separation via Communication Complexity
We use results from communication complexity, both new and old ones, to ...
research
∙
02/16/2021
Unambiguous DNFs and Alon-Saks-Seymour
We exhibit an unambiguous k-DNF formula that requires CNF width Ω̃(k^2),...
research
∙
02/09/2021
On the Power and Limitations of Branch and Cut
The Stabbing Planes proof system was introduced to model the reasoning c...
research
∙
06/19/2020
When Is Amplification Necessary for Composition in Randomized Query Complexity?
Suppose we have randomized decision trees for an outer function f and an...
research
∙
04/17/2020
Automating Cutting Planes is NP-Hard
We show that Cutting Planes (CP) proofs are hard to find: Given an unsat...
research
∙
02/25/2020
The Power of Many Samples in Query Complexity
The randomized query complexity R(f) of a boolean function f{0,1}^n→{0,1...
research
∙
12/10/2019
On the Complexity of Modulo-q Arguments and the Chevalley-Warning Theorem
We study the search problem class PPA_q defined as a modulo-q analog of ...
research
∙
05/16/2018